Detailed mathematical approach

Problem Summary

A decimal number is valid here when one of its digits equals the sum of all the remaining digits. If that distinguished digit is \(s\), then the total digit sum must be \(2s\). The C++, Python, and Java implementations therefore loop over \(s\in\{0,\dots,9\}\), sum every number of length \(1\) through \(n\) whose digit sum is \(2s\) and that contains at least one digit \(s\), and return the grand total modulo \(10^{16}\).

This reformulation is the key simplification. Because \(s\le 9\), every valid number has total digit sum at most \(18\), so the dynamic program only needs a tiny sum dimension instead of a huge search over all \(n\)-digit numbers.

Mathematical Approach

The solution does not enumerate candidate numbers directly. Instead, for each possible witness digit \(s\), it keeps aggregated information about all prefixes with a given length, a given digit sum, and a flag telling us whether the digit \(s\) has appeared yet.

Step 1: Reformulate the defining property

Let the digits of an \(\ell\)-digit number be \(d_1,\dots,d_\ell\). Suppose one digit equals the sum of all the others, and let that digit be \(s\). Then

$d_1+\cdots+d_\ell=s+s=2s.$

Conversely, if the total digit sum is \(2s\) and at least one digit is exactly \(s\), then removing one such digit leaves the remaining digits summing to \(s\), so the original condition is satisfied.

Therefore, for a fixed \(s\), the problem becomes: sum all \(\ell\)-digit numbers whose digit sum is \(2s\) and that contain at least one \(s\). There is no double counting, because the witness digit is determined uniquely by half of the total digit sum.

Step 2: Define the DP states for a fixed witness digit

Fix \(s\in\{0,\dots,9\}\) and write \(T=2s\). For each length \(\ell\), digit sum \(u\), and flag \(h\in\{0,1\}\), let \(\mathcal{N}_{\ell,s}(u,h)\) be the set of \(\ell\)-digit decimal numbers with no leading zero, digit sum \(u\), and where \(h=1\) means that digit \(s\) has already appeared.

Define

$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x.$

The first quantity is a count. The second is the sum of the actual numeric values in that state. For the fixed witness digit \(s\), the valid numbers of length \(\ell\) contribute exactly

$B_{\ell,s}(T,1).$

Since all digits are nonnegative, any state with \(u>T\) can never come back down to \(T\), so such states can be ignored immediately.

Step 3: Initialize the one-digit states

The first digit cannot be zero, so only \(d\in\{1,\dots,9\}\) are allowed initially. A one-digit state exists only when \(d\le T\), and then

$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$

All other states start at zero. In particular, when \(s=0\) we have \(T=0\), so there is no legal one-digit initialization. That entire case contributes nothing, which is consistent with the fact that a positive decimal number cannot have digit sum \(0\).

Step 4: Append one more digit

Take any state at length \(\ell\) with digit sum \(u\), witness flag \(h\), count \(A_{\ell,s}(u,h)\), and value sum \(B_{\ell,s}(u,h)\). Appending a new digit \(d\in\{0,\dots,9\}\) creates a number of length \(\ell+1\) with new digit sum

$u'=u+d,$

and the new witness flag becomes

$h'=\begin{cases} 1,& \text{if } h=1 \text{ or } d=s,\\ 0,& \text{otherwise.} \end{cases}$

The count update is therefore

$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h).$

For the value sum, every old number \(x\) turns into \(10x+d\). Summing over the whole state gives

$\sum(10x+d)=10\sum x+d\cdot \#\{\text{numbers in the state}\}.$

Hence the second recurrence is

$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h).$

All arithmetic is reduced modulo \(10^{16}\), exactly as in the implementations.

Step 5: Accumulate all lengths and all witness digits

For the fixed digit \(s\), the contribution of lengths \(1\) through \(n\) is

$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1).$

The final answer is then

$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}.$

The important structural fact is that \(2s\le 18\), so the DP only needs sums \(0,1,\dots,18\). That is why the whole computation stays tiny even when \(n\) is as large as \(2020\).

Step 6: Worked example with \(s=2\)

Now \(T=4\). For length \(1\), the possible starting digits are \(1,2,3,4\). They produce the states

$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$

with matching value sums \(1,2,3,4\).

At length \(2\), the only valid number with total digit sum \(4\) and containing a \(2\) is \(22\), so

$B_{2,2}(4,1)=22.$

At length \(3\), the valid numbers are

$112,\ 121,\ 202,\ 211,\ 220,$

whose sum is

$112+121+202+211+220=866.$

Therefore the total contribution of the witness digit \(2\) up to length \(3\) is

$22+866=888.$

This is exactly the kind of subtotal the DP computes automatically: it never lists long numbers explicitly, but the recurrence reproduces the same result through aggregated counts and aggregated value sums.

How the Code Works

The C++, Python, and Java implementations iterate through the ten possible witness digits. For each one, they maintain two \(19\times 2\) tables for the current length: one table stores how many prefixes belong to each state, and the other stores the sum of the numeric values of those prefixes.

The first layer is seeded with the legal one-digit numbers. Each later layer is built by appending one digit \(0\) through \(9\), updating both tables with the recurrences above. After every length, the implementation adds the state with digit sum \(2s\) and witness flag \(1\) to the global total, then rolls the tables forward to the next length.

No backtracking or large-number enumeration is needed. The only bookkeeping trick is to reduce every update modulo \(10^{16}\), so the running totals remain bounded throughout the computation.

Complexity Analysis

There are only \(10\) witness digits, at most \(19\) possible digit sums, \(2\) flag values, and \(10\) appended digits per transition. For each length, the work is therefore bounded by a small constant, so the overall running time is

$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n).$

Only the current layer and the next layer are stored, so the extra memory usage is

$O(19\cdot 2)=O(1)$

with respect to \(n\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=725
2. Digital sum: Wikipedia — Digital sum
3. Dynamic programming: Wikipedia — Dynamic programming
4. Positional notation: Wikipedia — Positional notation
5. Modular arithmetic: Wikipedia — Modular arithmetic