Detailed mathematical approach

Problem Summary

For each integer \(0 \le n < 10^{20}\), write its 20-digit decimal expansion \(d_{19}d_{18}\dots d_0\), allowing leading zeros. Define

$f(n)=\sum_{i=0}^{19} d_i^2.$

The task is to add all numbers \(n\) for which \(f(n)\) is a perfect square and keep only the last nine digits of that total. Direct enumeration is impossible because there are \(10^{20}\) candidates. The useful observation is that the condition depends only on the accumulated square-digit-sum, while the requested output is itself a sum over the actual decimal values.

Mathematical Approach

Let \(L=20\) and \(M=10^9\). Since each digit contributes at most \(9^2=81\), the largest possible value of \(f(n)\) is \(20\cdot 81=1620\). That means the entire state space for the square-digit-sum has only 1621 possibilities, which is small enough for a complete dynamic program.

Representing the Search Space

For each \(\ell\in\{0,1,\dots,20\}\) and each \(t\in\{0,1,\dots,1620\}\), let \(A_{\ell,t}\) be the set of integers \(x\) with \(0 \le x < 10^\ell\) whose \(\ell\)-digit expansion, padded with leading zeros if necessary, has square-digit-sum \(t\). Thinking in fixed length is exactly what the problem needs: every number below \(10^{20}\) is represented once as a 20-digit string, and the all-zero string contributes value 0 anyway.

The Two DP Tables

The implementations store two pieces of information for every state:

$C_\ell(t)=|A_{\ell,t}|,$

$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$

The first table counts how many \(\ell\)-digit strings reach square-digit-sum \(t\). The second table is more important for the final goal: it already accumulates the sum of their numeric values. The base state is

$C_0(0)=1,\qquad V_0(0)=0,$

with every other state at length 0 equal to 0. Because the final answer is needed only modulo \(10^9\), both tables can be reduced modulo \(M\) throughout; every later use of the tables is linear in these values, so modular reduction preserves correctness.

Recurrence from Adding One More Digit

Build length \(\ell\) from length \(\ell-1\) by choosing a new most significant digit \(d\in\{0,\dots,9\}\). If the old \((\ell-1)\)-digit part had square-digit-sum \(t-d^2\), then the new \(\ell\)-digit number has square-digit-sum \(t\). Therefore

$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2),$

where terms with negative arguments are omitted.

Now take the value sum. If \(x\in A_{\ell-1,t-d^2}\), then after adding digit \(d\) on the left, the new number is

$x+d\cdot 10^{\ell-1}.$

Summing this over all old states gives the second recurrence:

$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}.$

The second term is the key invariant of the whole solution: when the new leading digit is fixed, its place-value contribution must be added once for every shorter string counted by \(C_{\ell-1}(t-d^2)\).

Worked Example: Length 2 and Sum 9

The 2-digit strings whose square-digit-sum is 9 are exactly \(03\) and \(30\). Hence we expect

$C_2(9)=2,\qquad V_2(9)=3+30=33.$

The recurrence reproduces this cleanly. The count is

$C_2(9)=C_1(9)+C_1(0)=1+1=2,$

because the only possibilities are prepending 0 to the 1-digit string \(3\), or prepending 3 to the 1-digit string \(0\). For the value sum,

$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33.$

This small case shows why a count table alone is not enough: the problem asks for the sum of the qualifying numbers, not just their number.

Extracting the Final Answer

A perfect square state can only be \(r^2\) with \(1 \le r \le 40\), because \(40^2=1600 \le 1620\) while \(41^2=1681\) is already too large. So the desired result is

$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}.$

The omitted state \(r=0\) corresponds only to the number 0, whose contribution is 0, so including or excluding it makes no difference.

How the Code Works

The C++, Python, and Java implementations follow the recurrence directly. They first precompute the powers \(10^0,10^1,\dots,10^{19}\) modulo \(10^9\), because each transition needs the place value of the newly added digit. Next they allocate two tables indexed by digit length and square-digit-sum, initialize the empty-string base state, and iterate through all lengths from 1 to 20.

For every length, every digit \(0,\dots,9\), and every reachable square-digit-sum, the implementation updates the count table and the value table together. The count update records how many shorter strings can be extended, and the value update adds both the previous suffix sum and the new decimal-place contribution. After the tables for length 20 are complete, the implementation scans only the square targets \(1,4,9,\dots,1600\) and accumulates their stored value sums. The C++ implementation also includes short brute-force checkpoints for small lengths to verify that the DP matches exhaustive enumeration before solving the full 20-digit case.

Complexity Analysis

The loops run over \(L=20\) digit lengths, 10 possible digits, and at most \(81L+1=1621\) square-digit-sum states. This gives time complexity

$O(L\cdot 10\cdot 81L)=O(L^2).$

The implementations keep the full two-dimensional tables for all lengths, so the memory usage is

$O(L\cdot 81L).$

Even without rolling arrays, this is tiny compared with brute force over \(10^{20}\) numbers.

Footnotes and References

1. Project Euler, Problem 171: projecteuler.net/problem=171
2. Dynamic programming: Wikipedia - Dynamic programming
3. Positional notation: Wikipedia - Positional notation
4. Square number: Wikipedia - Square number