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:
Roman Numerals
Cube Digit Pairs
Right Triangles with Integer Coordinates

Error 403 The request cannot be completed because you have exceeded your quota. : quotaExceeded

Share:

Recent Posts

Mathematics in Cancer Treatment

How Mathematics is Transforming Cancer Treatment Mathematics plays an increasingly vital role in the fight against cancer mesothelioma. From optimizing drug delivery systems to personalizing

Read More »