The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
169 → 363601 → 1454 → 169 871 → 45361 → 871 872 → 45362 → 872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 → 363600 → 1454 → 169 → 363601 (→ 1454) 78 → 45360 → 871 → 45361 (→ 871) 540 → 145 (→ 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?
Here's my implementation in Python.
from math import factorial
from time import time
def get_factorial_sequence_length(number, factorials, lengths):
"""Return length of factorial sequence of number."""
if number in lengths:
return lengths[number]
chain = [number]
while len(chain) == len(set(chain)):
if chain[-1] in lengths:
index = chain.index(chain[-1])
return lengths[chain[-1]] + len(chain[:index])
chain_next = sum(factorials[digit] for digit in str(chain[-1]))
chain.append(chain_next)
duplicate_index = chain.index(chain[-1])
for num in chain:
index = chain.index(num)
if index <= duplicate_index:
lengths[num] = len(chain[index:-1])
if index > duplicate_index:
lengths[num] = len(chain[duplicate_index:index]) + len(chain[index:-1])
return lengths[number]
def get_sequence_counts(upper_bound, target_chain_size, lengths={}):
"""Return count of factorial sequences which have length target_chain_size within range upper_bound exclusive."""
factorials = {str(n): factorial(n) for n in range(10)}
for number in range(1, upper_bound):
chain_length = get_factorial_sequence_length(number, factorials, lengths)
lengths[number] = chain_length
if chain_length == target_chain_size:
yield number
if __name__ == '__main__':
start_time = time()
print(len(set(get_sequence_counts(1000000, 60))))
print(f'Time: {time() - start_time} seconds.')