notes.html

problem 92 · 75 lines

<article>
<h3>Problem Analysis</h3>
<p>
    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.
  </p>
<p>
    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 <em>multiset</em> 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
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Combinatorics" rel="noopener noreferrer" target="_blank">combinatorially</a>:
    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
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a>
    over digit positions, which is mathematically the
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Convolution" rel="noopener noreferrer" target="_blank">convolution</a>
    of single-digit contribution distributions - equivalently, raising a small
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Generating_function" rel="noopener noreferrer" target="_blank">generating function</a>
    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.
  </p>
<h3>Solution Approach</h3>
<h4>Digit-Square-Sum Convolution with Incremental DP</h4>
<p>
    Both <code>p0092_s0.py</code> and <code>p0092_s0.c</code> implement the same algorithm and differ
    only in language idioms. I describe it for a general <code>power_of_10 = d</code>, 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.
  </p>
<p>
    I maintain an array <code>a</code> where <code>a[s]</code> is the number of digit strings built so
    far whose digit-square-sum equals <code>s</code>. Before any digit is placed there is exactly one
    empty string, with sum 0, so <code>a = [1]</code>. 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
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Convolution" rel="noopener noreferrer" target="_blank">convolution</a>
    of the current array with this single-digit distribution.
  </p>
<p>
    Concretely, each iteration snapshots the current array into <code>b</code>, zero-extends
    <code>a</code> by 81 slots (the maximum a new digit can add), and then for every nonzero
    <code>b[i]</code> and every nonzero digit-square <code>s</code> in {1,4,9,...,81} adds
    <code>b[i]</code> into <code>a[i+s]</code>. I loop over only the nine nonzero squares. Digit 0
    contributes 0, so its effect would be <code>a[i] += b[i]</code> at the same index - but because I
    do not reset <code>a</code> to zero before the iteration (I only zero the new 81-slot extension),
    the original <code>b[i]</code> values are still sitting in <code>a</code>. That correctly accounts
    for appending a 0, folding the digit-0 case into the in-place extension.
  </p>
<p>
    To classify which sums belong to the 89-cycle I maintain a boolean array <code>is89</code>,
    computed lazily: whenever the array grows I evaluate <code>terminates_in_89</code> 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
    <code>a[s]</code> over all <code>s</code> with <code>is89[s]</code> true. Since
    <code>is89[0]</code> is false, the number 0 is excluded automatically.
  </p>
<p>
    The Python version grows the array with list concatenation (<code>a + [0] * 81</code>) and extends
    the boolean list with <code>map(terminates_in_89, range(...))</code>; it records the answer for
    every intermediate <code>power_of_10</code> in a dictionary so it can print the full progression
    with <code>--show</code>. The C version pre-allocates the maximum size <code>1 + d * 81</code> once
    with <code>calloc</code>, uses <code>memcpy</code> to snapshot and <code>memset</code> to zero the
    extension, and uses <code>long long</code> counts because the totals exceed 32 bits once d reaches
    9. Both are structurally identical; the C version is simply more explicit about memory.
  </p>
</article>