Digit Factorial Chains

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:
\begin{align}
&169 \to 363601 \to 1454 \to 169\\
&871 \to 45361 \to 871\\
&872 \to 45362 \to 872
\end{align}
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
\begin{align}
&69 \to 363600 \to 1454 \to 169 \to 363601 (\to 1454)\\
&78 \to 45360 \to 871 \to 45361 (\to 871)\\
&540 \to 145 (\to 145)
\end{align}
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?

This problem can be solved using dynamic programming and is well suited to be solved by computers due to the recursive nature of the problem. So, I would first need to mention the pseudocode for this problem.

We need a function `factorial_digits` that computes the sum of the factorials of the digits of the input number. This function iterates over the digits of a number, computes the factorial of each digit, and adds it to a sum which is initialized to zero.

Then we define another function `length_chain` that takes in a number and computes the length of the chain starting from that number. This function first checks if the input number is larger than 1 million – if it is, it gets discarded. The function then checks for already computed results in a cache.

If a result exists in the cache, it is directly returned. If not, the function invokes itself recursively with the result from the `factorial_digits` function and increment the count by 1. This result is then stored back in the cache for future reference.

From 0 to 1 million, for each number, `length_chain` is computed. And if it equals to 60, it gets added to the count.

“`
factorials = {each_digit: factorial(each_digit) for each_digit in range(10)}
cache = {169: 3, 363601: 3, 1454: 3, 871: 2, 45361: 2, 872: 2, 45362: 2}

def factorial_digits(num):
result = 0
while num:
num, digit = divmod(num, 10)
result += factorials[digit]
return result

def length_chain(n):
if n >= 1000000 or n in cache:
return cache[n]
count = 1 + length_chain(factorial_digits(n))
cache[n] = count
return count

count = 0
for i in range(1000000):
if length_chain(i) == 60:
count += 1
“`
Please do remember this isn’t exact Python code, but a pseudocode to guide you in the right direction.

The code begins by calling `length_chain` for all numbers below one million and increments a count whenever it hits a chain of 60.

To obtain the exact number of chains with exactly 60 non-repeating terms that start below one million, you’d have to actually run this code.

The nature of this problem reflects a mathematical concept known as a “Recurrence Relation”. This property can be hard to analyze by hand, but computers can easily solve and cache results for us, hence can provide us with the exact count.

Please note that this solution assumes that you’re familiar with basic scripting or programming. If you’re not comfortable with this, I would recommend studying about dynamic programming and recursion to be able to understand the solution fully.

More Answers: