Square Digit Chains

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.
For example,
\begin{align}
&44 \to 32 \to 13 \to 10 \to \mathbf 1 \to \mathbf 1\\
&85 \to \mathbf{89} \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to \mathbf{89}
\end{align}
Therefore any chain that arrives at $1$ or $89$ will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at $1$ or $89$.
How many starting numbers below ten million will arrive at $89$?

For a given number, let’s denote the sum of the squares of its digits as f(n). So according to the question, we need to find the number of integers i (1 ≤ i < 10 000 000) such that g(i) = 89, where g(i) is the result of applying f repeatedly starting with i until we reach a number that has appeared before (1 or 89 in this particular case).

Calculating g(i) for all 1 ≤ i < 10 000 000 is a bit cumbersome, so this would probably be a good time to employ some sort of caching technique (memoization or dynamic programming). Another good observation is that 9999999 (the biggest number that satisfies our constraints) makes the function f result in a number not larger than 81*7 < 600, so calculating g for all the numbers less than 600 will be sufficient. A Python solution to this could look something like this: ```Python end = [0] * 600 end[1] = 1 end[89] = 89 for i in range(2, 600): j = i while end[j] == 0: j = sum(int(c)**2 for c in str(j)) end[i]=end[j] result = sum(1 for i in range(1, 10000000) if end[sum(int(c)**2 for c in str(i))] == 89) print(result) ``` This code creates a list named `end`. For each number from 2 to 600, it follows the chain until it arrives at the number 1 or 89, then it remembers the destination for each number from 2 to 600 in the list `end`. Then it goes through the numbers below ten million and checks how many starting numbers will arrive at $89$. Remember, it only needs to calculate the sum of the squares of the digits and look up the destination in the list `end`, so it's quite fast.

More Answers: