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:

The goal is to determine how many starting numbers below $10^K$ 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$

This script breaks down the problem by first understanding the bounds of possible digit square sums, then using dynamic programming to build up the count of valid numbers digit by digit. By incorporating a recursive check for reachability to 89 and optimizing calculations with modular arithmetic.

1. 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.

2. Dynamic Programming Approach:
   • Initial State (p[]):

     The list p[] is initialized to represent the count of numbers with a single digit that result in each possible sum. For sums present in S, the count is set to 1 (since each single-digit number corresponds to one square sum); otherwise, it's 0.

   • Iterative Update:

     For each additional digit (up to \(K\)), the script updates the list p[] to account for all possible new digit additions. This is done by summing the counts of previous sums adjusted by each possible square in S, ensuring that only valid transitions are considered. The modulo operation ensures that counts remain within manageable limits.

3. Determining Reachability to 89:
   • Recursive Function (d):

     The lambda function d recursively determines whether a given sum will eventually reach 89 by repeatedly applying the sum-of-squares transformation. It efficiently caches results to avoid redundant computations.

   • Final Summation:

     After building the complete count of numbers for each possible sum, the script sums the counts where the corresponding sum leads to 89, excluding the trivial case of 0. This final sum is then output modulo \(10^9 + 7\) to handle large numbers.

4. Efficiency Considerations:
   • Space Optimization:

     By limiting the range to $81K + 1$ and only considering valid square sums, the script minimizes memory usage.

   • Modular Arithmetic:

     All operations involving counts are performed modulo \(10^9 + 7\), ensuring that intermediate and final results remain within feasible numerical limits, which is essential given the potentially vast number of combinations for large \(K\).

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 92

HackerRank Project Euler 92: How many starting numbers below $10^K$ will arrive at $89$? As the result can be large, print modulo $(10^9 + 7)$