Problem Analysis
Every starting number generates a chain: repeatedly replace the current value with the sum of the squares of its decimal digits. The problem tells us (and it can be proved) that every such chain eventually settles into one of exactly two terminal states - the fixed point 1, or the cycle that runs through 89. The task is to count how many starting numbers below ten million land in the 89-cycle. A direct approach would simulate the chain for all 10^7 starting values, which is feasible but wasteful, and scales badly if the bound grows.
The observation that unlocks an efficient solution is that the chain depends only on the digit-square-sum of a number, and that sum depends only on the multiset of digits, not their order. Both 123 and 321 have digit-square-sum 1+4+9=14, so they follow identical chains. This invariance lets me reformulate the problem combinatorially: instead of asking what chain each of 10^7 numbers follows, I ask how many numbers share each possible digit-square-sum, and whether that sum reaches 89. For a d-digit number the largest possible digit-square-sum is 81d (all nines), so there are at most 81d+1 distinct sums - a tiny domain compared with 10^d. I count the numbers contributing to each sum with dynamic programming over digit positions, which is mathematically the convolution of single-digit contribution distributions - equivalently, raising a small generating function to the d-th power. The total work is O(d^2 * 81), which for d=7 is only a few thousand operations: the algorithm runs in microseconds where a brute-force scan would take seconds.
Solution Approach
Digit-Square-Sum Convolution with Incremental DP
Both p0092_s0.py and p0092_s0.c implement the same algorithm and differ
only in language idioms. I describe it for a general power_of_10 = d, which counts the
numbers from 0 to 10^d - 1. I allow leading zeros, so every count is taken over fixed-width
d-digit strings; the all-zeros string is just the number 0, which never reaches 89 and so does not
pollute the answer.
I maintain an array a where a[s] is the number of digit strings built so
far whose digit-square-sum equals s. Before any digit is placed there is exactly one
empty string, with sum 0, so a = [1]. Each iteration appends one digit position. The
distribution of the contribution from a single digit is fixed: digit 0 adds 0, digit 1 adds 1,
digit 2 adds 4, ..., digit 9 adds 81. Extending by one digit is therefore a
convolution
of the current array with this single-digit distribution.
Concretely, each iteration snapshots the current array into b, zero-extends
a by 81 slots (the maximum a new digit can add), and then for every nonzero
b[i] and every nonzero digit-square s in {1,4,9,...,81} adds
b[i] into a[i+s]. I loop over only the nine nonzero squares. Digit 0
contributes 0, so its effect would be a[i] += b[i] at the same index - but because I
do not reset a to zero before the iteration (I only zero the new 81-slot extension),
the original b[i] values are still sitting in a. That correctly accounts
for appending a 0, folding the digit-0 case into the in-place extension.
To classify which sums belong to the 89-cycle I maintain a boolean array is89,
computed lazily: whenever the array grows I evaluate terminates_in_89 for the newly
appeared indices only. That helper simply simulates the chain, and the values are small - after d
digits the maximum sum is 81d (567 for d=7) - so each simulation is short. The answer is the sum of
a[s] over all s with is89[s] true. Since
is89[0] is false, the number 0 is excluded automatically.
The Python version grows the array with list concatenation (a + [0] * 81) and extends
the boolean list with map(terminates_in_89, range(...)); it records the answer for
every intermediate power_of_10 in a dictionary so it can print the full progression
with --show. The C version pre-allocates the maximum size 1 + d * 81 once
with calloc, uses memcpy to snapshot and memset to zero the
extension, and uses long long counts because the totals exceed 32 bits once d reaches
9. Both are structurally identical; the C version is simply more explicit about memory.