Project Euler/92

This is problem 92 on Project Euler: https://projecteuler.net/problem=92

Overview of the Problem

Question

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,

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

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 Approach

The key observation for this problem is that the sum of squared digits for any number below ten million is at most $ 7 \times 9^2 = 567 $. This means every chain quickly collapses into the small state space $ 1 \dots 567 $.

We can break the problem into two phases:

Phase 1: Precompute chain destinations for 1 through 567

For each integer $ s $ from $ 1 $ to $ 567 $, follow its digit-square-sum chain until it reaches either $ 1 $ or $ 89 $. Cache the result (a boolean: true if the chain arrives at $ 89 $) in an array. Walking the chain is cheap because these numbers are small, and once a chain hits a previously cached value, we can short-circuit.

Phase 2: Count arrivals at 89 for all numbers below ten million

For each starting number $ n $ from $ 1 $ to $ 9,999,999 $:

1. Compute $ s = \text{sumOfSquaredDigits}(n) $. This value is in the range $ 0 \dots 567 $.
2. Look up the cached result for $ s $.
3. If the cached result is true (i.e., the chain ultimately reaches $ 89 $), increment the count.

The sumOfSquaredDigits helper repeatedly extracts the last digit of $ n $, squares it, adds it to a running sum, and divides $ n $ by $ 10 $.

This approach runs in $ O(N \cdot d) $ time where $ N = 10^7 $ and $ d \approx 7 $ digits, making it fast enough for a single-threaded Java implementation.

Java Solution

The full implementation is available in the Euler Git repository:

https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem092.java

public class Problem092 {

    private static int sumOfSquaredDigits(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;
            sum += d * d;
            n /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        boolean[] cache = new boolean[568];

        for (int i = 1; i <= 567; i++) {
            int n = i;
            while (n != 1 && n != 89) {
                n = sumOfSquaredDigits(n);
            }
            cache[i] = (n == 89);
        }

        int count = 0;
        for (int i = 1; i < 10_000_000; i++) {
            if (cache[sumOfSquaredDigits(i)]) {
                count++;
            }
        }

        System.out.println(count);
    }
}