Problem 92: Square Digit Chains

Step 1: Reduce the state space

If $n<10^7$, then $n$ has at most $7$ digits, so

Thus after one application of $f$, every chain enters the finite set

Therefore the eventual destination of $n$ depends only on the value $f(n)$. In particular, if we know for each $s\in\{1,\dots,567\}$ whether repeated application of $f$ reaches $1$ or $89$, then we only need to count how many numbers below $10^7$ have initial digit-square-sum equal to such an $s$.

Step 2: Count numbers by their digit-square-sum

Every number $0\le n<10^7$ has a unique 7-digit representation with leading zeros allowed. So it is equivalent to count 7-digit strings

by the value

Let $C_k(s)$ be the number of length-$k$ digit strings whose digit-square-sum is $s$. Then

• $C_0(0)=1$,
• $C_0(s)=0$ for $s\ne 0$,
• and for $k\ge 0$,

where terms with negative index are interpreted as $0$.

This recurrence is immediate: to build a $(k+1)$-digit string with total square-sum $s$, choose its last digit $d$, and the first $k$ digits must contribute $s-d^2$.

After computing $C_7(s)$ for all $0\le s\le 567$, the answer is

where $s\leadsto 89$ means the chain starting from $s$ eventually reaches $89$.

The all-zero string contributes only to $s=0$, and $0$ does not reach $89$, so it does not affect the final count.

Why only 1 and 89 matter

Since every chain enters the finite set $\{1,\dots,567\}$, every orbit is eventually periodic. A direct computation on this finite set shows that the only periodic attractors are

and

Hence each starting value below $10^7$ ends at either $1$ or $89$.

Editorial

The crucial reduction is that numbers below $10^7$ collapse after one move into the tiny state space $\{0,\dots,567\}$. So instead of following ten million chains separately, we only need to know which of those 568 sums eventually fall into the $89$-cycle.

Once those destinations are known, the counting part becomes a digit DP. We treat every number below $10^7$ as a 7-digit string with leading zeros and count how many such strings produce each possible digit-square-sum. That explores the search space by digit choices rather than by raw integers. The final answer is obtained by summing the DP counts for exactly those sums whose chains terminate at $89$.

Pseudocode

Compute, for every sum $s$ from 1 to 567, whether repeated digit-square steps end at $89$.

Initialize a DP table for digit strings with $dp[0]=1$.

Repeat for 7 digit positions:
    Create a fresh table of counts
    For each current sum and its number of realizations:
        For each possible next digit from 0 to 9:
            Update the count for the new square-digit-sum
    Replace the old table with the new one

Add the final counts for all sums whose destination is $89$.
Return that total.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

The state space for the DP has

• $7$ digit positions,
• $568$ possible sums,
• $10$ digit choices.

So the running time is

and the memory usage is

In other words, this is a tiny constant-size computation.

Answer

#include <cassert>
#include <iostream>
#include <vector>

int digit_square_sum(int n) {
    int s = 0;
    while (n > 0) {
        int d = n % 10;
        s += d * d;
        n /= 10;
    }
    return s;
    return s;
}

bool ends_at_89(int n) {
    while (n != 1 && n != 89) {
        n = digit_square_sum(n);
    }
    return n == 89;
}

long long solve() {
    const int digits = 7;
    const int max_sum = digits * 81;

    std::vector<bool> destinations(max_sum + 1, false);
    for (int s = 1; s <= max_sum; ++s) {
        destinations[s] = ends_at_89(s);
    }

    std::vector<long long> dp(max_sum + 1, 0);
    dp[0] = 1;

    for (int pos = 0; pos < digits; ++pos) {
        std::vector<long long> next_dp(max_sum + 1, 0);
        for (int sum = 0; sum <= max_sum; ++sum) {
            if (dp[sum] == 0) {
                continue;
            }
            for (int digit = 0; digit <= 9; ++digit) {
                next_dp[sum + digit * digit] += dp[sum];
            }
        }
        dp = next_dp;
    }

    long long answer = 0;
    for (int s = 0; s <= max_sum; ++s) {
        if (destinations[s]) {
            answer += dp[s];
        }
    }
    return answer;
}

int main() {
    const long long answer = solve();
    assert(answer == 8581146);
    std::cout << answer << '\n';
    return 0;
}

"""
Problem 92: Square Digit Chains

Count starting numbers below 10,000,000 that arrive at 89 by grouping
numbers according to their first square-digit-sum.
"""

def digit_square_sum(n):
    s = 0
    while n > 0:
        d = n % 10
        s += d * d
        n //= 10
    return s

def ends_at_89(n):
    while n not in (1, 89):
        n = digit_square_sum(n)
    return n == 89


def solve():
    digits = 7
    max_sum = digits * 81

    destinations = [False] * (max_sum + 1)
    for s in range(1, max_sum + 1):
        destinations[s] = ends_at_89(s)

    dp = [0] * (max_sum + 1)
    dp[0] = 1

    for _ in range(digits):
        next_dp = [0] * (max_sum + 1)
        for total, ways in enumerate(dp):
            if ways == 0:
                continue
            for digit in range(10):
                next_dp[total + digit * digit] += ways
        dp = next_dp

    return sum(dp[s] for s in range(max_sum + 1) if destinations[s])


if __name__ == "__main__":
    answer = solve()
    assert answer == 8581146
    print(answer)