diff options
| -rw-r--r-- | src/projecteuler/074.py | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/src/projecteuler/074.py b/src/projecteuler/074.py new file mode 100644 index 0000000..d463358 --- /dev/null +++ b/src/projecteuler/074.py @@ -0,0 +1,59 @@ + +fac = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] +numbers = [0]*10000000 + +for i in xrange(0, 10): + numbers[i] = 1 +numbers[145] = 1 +numbers[40585] = 1 +numbers[169] = 3 +numbers[871] = 2 +numbers[872] = 2 +numbers[45361] = 2 +numbers[45362] = 2 +numbers[1454] = 3 +numbers[363601] = 3 + +def next(n): + x = 0 + while n > 0: + x += fac[n % 10] + n /= 10 + return x + +def count(n): + if numbers[n] != 0: + return + chain = [n] + x = next(n) + while x not in chain: + chain.append(x) + if numbers[x] != 0: + break + #if x == 145: + # break + #elif x == 169: + # chain += [363601, 1454] + # break + #elif x == 871: + # chain += [45361] + # break + #elif x == 872: + # chain += [45362] + # break + x = next(x) + last = numbers[chain[-1]] + l = len(chain) + for j in xrange(0, l-1): + c = chain[j] + numbers[c] = l - j - 1 + last + +for i in xrange(10, 1000000): + count(i) + +#c = 0 +#for j in numbers: +# if j == 60: +# c += 1 +print max(numbers) + |