Solution

Answer: 8581146

Let $f(n)$ denote the sum of the squares of the digits of $n$.

For example,

$$f(44)=4^2+4^2=32.$$

Repeatedly applying $f$ produces a chain:

$$44 \to 32 \to 13 \to 10 \to 1,$$

$$85 \to 89 \to 145 \to 42 \to \cdots \to 89.$$

The problem asks:

How many starting numbers $1 \le n < 10^7$ eventually arrive at $89$?

Mathematical analysis

1. Key observation: chains rapidly shrink

Suppose $n < 10^7$. Then $n$ has at most $7$ digits.

The largest possible value of the sum of squared digits occurs for:

$$9,999,999$$

whose digit-square sum is

$$7 \cdot 9^2 = 7 \cdot 81 = 567.$$

Therefore, after one step, every number below ten million maps into the range

$$1 \le f(n) \le 567.$$

This is the crucial insight.

Instead of studying ten million long chains independently, we only need to determine, for each value $1,\dots,567$, whether it eventually reaches:

$1$, or
$89$.

Then every larger number inherits the fate of its first digit-square sum.

2. The terminal cycles

Experimentally (and it can be proven), every chain ends in one of two cycles:

$$1 \to 1$$

$$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$$

So every starting number ultimately lands in either $1$ or $89$.

3. Dynamic programming / memoization

Define:

$$g(x)= \begin{cases} 1 & \text{if the chain reaches }1,\ 89 & \text{if the chain reaches }89. \end{cases}$$

We compute $g(x)$ for all $x \le 567$ using memoization.

Then for each number $n < 10^7$:

Compute $s=f(n)$.
Look up whether $s$ ends at $89$.

This gives an $O(10^7)$ solution, which is perfectly feasible in Python.

Python implementation

def digit_square_sum(n):
    """Return the sum of the squares of the digits of n."""
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total

# Memo table:
# memo[x] = True  if x eventually reaches 89
# memo[x] = False if x eventually reaches 1
memo = {1: False, 89: True}

def arrives_at_89(n):
    """
    Determine whether n eventually reaches 89.
    Uses memoization to avoid recomputation.
    """
    chain = []

    while n not in memo:
        chain.append(n)
        n = digit_square_sum(n)

    result = memo[n]

    # Store results for all numbers seen in the chain
    for x in chain:
        memo[x] = result

    return result

LIMIT = 10_000_000

count = 0

for n in range(1, LIMIT):
    if arrives_at_89(digit_square_sum(n)):
        count += 1

print(count)

Code walkthrough

`digit_square_sum(n)`

def digit_square_sum(n):

Computes:

$$\sum (\text{digits})^2.$$

Example:

$44 \to 4^2+4^2=32$
$85 \to 8^2+5^2=89$

The loop extracts digits using:

digit = n % 10
n //= 10

and accumulates their squares.

Memoization table

memo = {1: False, 89: True}

We encode:

False → ends at $1$
True → ends at $89$

These are the only two terminal outcomes.

`arrives_at_89(n)`

This function follows the chain until reaching a previously known result.

Example for $44$:

$$44 \to 32 \to 13 \to 10 \to 1.$$

Once 1 is found, every earlier value is cached as False.

For $85$:

$$85 \to 89,$$

so it returns True.

Memoization dramatically reduces repeated work because all chains quickly collapse into the small range $1$–$567$.

Main loop

for n in range(1, LIMIT):

Iterates through all starting numbers below ten million.

For each:

arrives_at_89(digit_square_sum(n))

We immediately reduce the number to its first digit-square sum, which is at most $567$.

If the chain ends at $89$, increment the counter.

Small-example verification

From the statement:

Example 1

$$44 \to 32 \to 13 \to 10 \to 1$$

Our function returns False.

Example 2

$$85 \to 89 \to \cdots$$

Our function returns True.

So the logic matches the examples.

Final verification

There are $9,999,999$ starting numbers considered.
Empirically, most chains end at $89$, so the answer should be several million.
The known Project Euler result is:

$$8,581,146$$

which is consistent with the expected magnitude.

Answer: 8581146

Project Euler Problem 92