Detailed mathematical approach

Problem Summary

Start with a positive integer \(n\), replace it by the sum of the squares of its decimal digits, and repeat. This produces a chain $n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$ where $\sigma(n)=\sum (\text{decimal digit})^2.$ For all starting values in this problem, the chain eventually reaches either the fixed point \(1\) or the loop $89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$ The goal is to count how many starting numbers satisfy \(1 \le n \lt 10^7\) and end in the \(89\)-loop.

The important observation is that the chain dynamics collapse very quickly. Even though there are almost ten million starting values, after one digit-square step every chain has already fallen into a tiny finite state space. The whole problem is therefore a classification problem on that reduced space.

Mathematical Approach

The implementations are built around a single reduction: instead of reasoning about all numbers below \(10^7\) separately, classify the possible values of the digit-square map and then reuse those classifications for every starting value.

The digit-square map and its attractors

Define $\sigma(n)=\sum_{r=0}^{k-1} d_r^2,$ where \(d_0,d_1,\dots,d_{k-1}\) are the decimal digits of \(n\). Repeated application of \(\sigma\) gives a deterministic sequence, so each starting value lies on a path in a finite functional graph once the values become small enough.

For this problem, the only two outcomes that matter are: $1 \to 1$ and the \(89\)-cycle shown above. It is convenient to encode the result of a chain by a terminal-label function $E(n)\in\{1,89\},$ meaning that \(E(n)=1\) if the chain starting at \(n\) reaches \(1\), and \(E(n)=89\) if it reaches the \(89\)-cycle.

Why only the states \(1\) through \(567\) matter

Every starting value satisfies \(n \lt 10^7\), so it has at most 7 decimal digits. The largest possible digit-square sum is therefore obtained when every digit is \(9\): $\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$ This means that after a single application of \(\sigma\), every chain has entered the set $S=\{1,2,\dots,567\}.$ That is the decisive compression step in the problem.

The set \(S\) is also closed under further applications of \(\sigma\). Indeed, any \(m\in S\) has at most 3 digits, so $\sigma(m)\le 3\cdot 9^2=243 \lt 567.$ Once a chain enters \(S\), it never leaves. So the infinite-looking process is actually governed by a functional graph on only 567 states.

The recurrence for the terminal label

On the reduced state space, the classification obeys the simple recurrence $E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m))\text{ for }m\notin\{1,89\}.$ This formula is exactly what the implementations evaluate. If the fate of \(\sigma(m)\) is already known, then the fate of \(m\) is identical. Memoization turns that recurrence into an efficient lookup process: once a reduced state has been classified, every future chain that reaches it is resolved immediately.

A second way to justify termination is numerical descent. If \(n\) has \(d\) digits, then \(n\ge 10^{d-1}\) while \(\sigma(n)\le 81d\). For \(d\ge 4\), one has \(81d \lt 10^{d-1}\), so \(\sigma(n)\lt n\). Thus sufficiently large numbers strictly decrease after one step, and in the present problem all starting values drop into \(S\) immediately anyway.

A worked example

The chain for \(44\) is $44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1.$ Hence \(E(44)=1\).

A more informative example uses the largest possible reduced state. Since $\sigma(9{,}999{,}999)=7\cdot 81=567,$ we can continue from there: $567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89.$ So any starting value whose first digit-square sum is \(567\) is automatically counted as a chain ending at \(89\).

Turning the recurrence into the final count

Once \(E(m)\) has been determined for every \(m\in S\), the answer is simply $\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}.$ That is the exact quantity accumulated by the efficient implementations. The key economy is that the reduced states are solved once and then reused millions of times.

How the Code Works

The C++, Python, and Java implementations all compute the same mathematical object, namely the terminal label \(E(n)\), but they package the memoization slightly differently.

Seed the known outcomes

The computation begins with the two known labels \(1\) and \(89\). Reaching \(1\) settles the chain immediately, and reaching \(89\) also settles it for classification purposes because the subsequent values stay on the 8-cycle through \(145,42,20,4,16,37,58\).

Follow an unresolved chain once

When the implementation meets a value whose outcome is not yet known, it keeps applying the digit-square map until it reaches a value that is already classified. At that point, the same label is assigned back through the states just visited. This is the memoization step. The C++ and Java implementations keep the stored table very close to the reduced range bounded by \(567\), while the Python implementation applies the same recurrence recursively with a dictionary cache.

Scan all starting values below \(10^7\)

The main loop checks each starting value from \(1\) up to \(9{,}999{,}999\). For each one, it computes the sum of squared digits and asks whether the resulting reduced state has label \(89\). One implementation also contains small checkpoint verifications that match the standard examples: there are 7 such chains below \(10\) and 80 below \(100\).

Complexity Analysis

Let \(N=10^7-1\). Computing one digit-square sum takes at most 7 digit operations, so the dominant cost is linear in the number of starting values, namely \(O(N)\) with a small constant, or \(O(N\log_{10}N)\) if the digit extraction is written explicitly. The reduced-state resolution is negligible by comparison because only 567 core states need classification.

The mathematical core needs only \(O(567)\) memory for terminal labels. That is essentially what the C++ and Java implementations use, up to small fixed overhead. The Python implementation follows the same recurrence but can retain more cached values because it memoizes recursively in a dictionary as it resolves inputs.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=92
2. Happy number: Wikipedia - Happy number
3. Happy Number: MathWorld - Happy Number
4. Sequence of happy numbers: OEIS A007770