Project Euler Problem 92 Solution

Project Euler Problem 92 Statement

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$?

Solution

Project Euler Problem 92 overview:

Determine how many starting numbers below $10^K$ (original problem uses $K=7$) will eventually arrive at 89 through the iterative process of replacing a number with the sum of the squares of its digits. Given the potentially large range of $K$ (up to 200), the final count needs to be presented modulo $10^9+7$

Preprocessing with Digit Square Sums:

Maximum Possible Sum Calculation:
For any number with $K$ digits, the maximum possible sum of the squares of its digits is $81 \times K$ (since $9^2 = 81$). The script initializes a range C[] from 0 to $81K + 1$ to cover all possible sums.
Square List Initialization:
The list S contains all possible single-digit squares: $\{0, 1, 4, 9, 16, 25, 36, 49, 64, 81\}$. This set is crucial for efficiently calculating possible sums when adding new digits.

The algorithm works in two main phases. In the first phase, it uses dynamic programming to count how many $K-digit$ numbers produce each possible digit square sum. The array $p$ starts by marking which single-digit square values are possible ($0, 1, 4, 9, 16, 25, 36, 49, 64, 81$). Then, for each additional digit position, it updates $p$ to count how many ways you can form each sum by adding another digit. The line

p = [sum(p[j-s] for s in S if j>=s) % M for j in C]

essentially says: "the number of ways to get sum $j$ with $k$ digits equals the sum of ways to get ($j$ minus each possible digit square) with $k-1$ digits." This builds up the complete distribution of digit square sums for $K-digit$ numbers.

In the second phase, the solution determines which digit square sums eventually lead to $89$. The recursive lambda function $d$ checks whether a given number converges to $89$ by repeatedly computing the sum of its digits' squares. Once the algorithm knows both how many $K-digit$ numbers map to each sum and which sums lead to $89$, it simply adds up the counts for all sums that converge to $89$. The modulo operation with $M=10^9+7$ keeps the numbers manageable.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 92

HackerRank Project Euler Problem 92: Changes the upper limit from $10^7$ to $10^K$, where $1\le K\le 200$.

Python Source Code

K = int(input())
M, C, S = 10**9+7, range(81*K+1), [0,1,4,9,16,25,36,49,64,81]
d = lambda n: n>1 and (n==89 or d(sum(S[int(c)] for c in str(n))))

p = [i in S for i in C]
for _ in range(K-1):
    p = [sum(p[j-s] for s in S if j>=s) % M for j in C]

print(sum(v for i,v in enumerate(p) if i and d(i)) % M)