Detailed mathematical approach

Problem Summary

For each decimal length \(n\), we consider all \(n\)-digit numbers \(x=d_1d_2\dots d_n\) with \(d_1\neq 0\). Every contiguous substring \(d_i d_{i+1}\dots d_j\) is interpreted as a decimal integer. The number is called a one-child number when exactly one of those substrings is divisible by \(n\). Let \(g(n)\) denote the number of such \(n\)-digit numbers. The required total up to \(10^{19}\) is therefore

$F(10^{19})=\sum_{n=1}^{19} g(n).$

Mathematical Approach

Step 1: Organize Substrings by Their Ending Position

Fix a length \(n\). For each position \(k\in\{1,\dots,n\}\), define \(v_{i,k}\) as the decimal value of the substring ending at \(k\):

$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k.$

Now define, for each remainder \(r\in\{0,1,\dots,n-1\}\),

$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}.$

This counts how many substrings ending at position \(k\) fall into each residue class modulo \(n\). Since every substring has a unique ending position, the total number of divisible substrings in the whole number is

$\sum_{k=1}^{n} A_k(0).$

Therefore the one-child condition is exactly

$\sum_{k=1}^{n} A_k(0)=1.$

Step 2: Remainder Transition When a Digit Is Appended

Suppose we already know the remainder of a substring ending at position \(k\). Appending a new digit \(d\) to its right multiplies the old value by 10 and adds \(d\), so the remainder update is

$\phi_d(r)=(10r+d)\bmod n.$

Hence, when we move from position \(k\) to \(k+1\), every old substring ending at \(k\) is extended by the new digit, and there is also one brand-new substring consisting only of that new digit. This gives the recurrence

$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r),$

where \(\mathbf{1}\) is the indicator function. This formula is the heart of the digit DP: it updates all suffix-substring remainders without enumerating substrings explicitly.

Step 3: Why Saturating Counts at 2 Is Enough

The implementation never needs the exact value of \(A_k(r)\) once it exceeds \(1\). For the final decision, every relevant test is of the form “is the number of divisible substrings ending here equal to 0, equal to 1, or at least 2?” Therefore it is safe to replace each exact count by the saturated value

$c_k(r)=\min(2, A_k(r)).$

This loses no information, because future transitions only perform additions, and

$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b))$

for all nonnegative integers \(a,b\). So capping at 2 after every update produces exactly the same future saturated states as carrying the full counts and capping later.

With this convention, the transition becomes

$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right).$

Step 4: Ternary State Compression

For fixed \(n\), the full saturated remainder profile at position \(k\) is the vector

$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n.$

Because each component has three possible values, the vector can be packed into one integer using base 3:

$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$

This gives a compact hash-map key for the DP and avoids storing large nested structures.

Step 5: Enforcing the “Exactly One” Condition

Let \(z_k=c_k(0)\), the saturated number of substrings ending at position \(k\) that are divisible by \(n\). Because every divisible substring is counted at the position where it ends, we only need to remember whether the unique successful event has already happened.

The DP therefore uses two layers:

$L_0:\text{ no divisible substring has appeared yet},\qquad L_1:\text{ exactly one has appeared so far}.$

After appending a digit and computing the new saturated vector, the transitions are:

$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \text{reject},& z_{k+1}=2, \end{cases}$

$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \text{reject},& z_{k+1}\ge 1. \end{cases}$

So the only accepted terminal states after \(n\) digits are those in layer \(L_1\).

Step 6: Initialization

The first digit may be any value in \(\{1,\dots,9\}\). For a one-digit prefix, there is only one substring, namely the digit itself, so the initial saturated vector has a single 1 in residue class \(d\bmod n\) and 0 everywhere else. If that residue is 0, the state starts in layer \(L_1\); otherwise it starts in layer \(L_0\).

Worked Example: \(n=2\)

For a two-digit number \(ab\), the substrings are \(a\), \(b\), and \(ab\). Divisibility by 2 depends only on the last digit, so:

$a \equiv 0 \pmod 2 \iff a \text{ is even},$

$b \equiv 0 \pmod 2 \iff b \text{ is even},$

$ab \equiv 0 \pmod 2 \iff b \text{ is even}.$

If \(b\) is even, then both \(b\) and \(ab\) are divisible by 2, so the number already has at least two valid substrings. Therefore we must have \(b\) odd. Then \(b\) and \(ab\) are both non-divisible, so the unique divisible substring must be \(a\), which forces \(a\) to be even. Thus

$g(2)=4\cdot 5=20,$

because \(a\in\{2,4,6,8\}\) and \(b\in\{1,3,5,7,9\}\). This matches the DP count.

How the Code Works

The C++, Python, and Java implementations all realize this same structure. For each length \(n\), they precompute digit-to-remainder transitions \(r\mapsto (10r+d)\bmod n\), store reachable ternary-encoded states in hash maps for the two layers, and extend those states digit by digit. Every transition updates the saturated remainder profile, checks the new zero-remainder count, and keeps only the states that can still lead to exactly one divisible substring overall. Summing the counts in the second layer after \(n\) digits gives \(g(n)\), and summing \(g(1),g(2),\dots,g(19)\) gives the requested total.

Complexity Analysis

Let \(S_n(k)\) be the number of reachable encoded states after \(k\) digits, and let \(S_n=\max_k S_n(k)\). Updating one state for one appended digit touches an \(n\)-component remainder vector, so the total work for fixed \(n\) is

$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n).$

The memory usage is \(O(S_n)\), since only the current and next DP layers are stored. In practice \(S_n\) is much smaller than the crude upper bound \(3^n\), which is why the method is fast enough for all \(n\le 19\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=413
2. Dynamic programming: Wikipedia — Dynamic programming
3. Finite-state machine: Wikipedia — Finite-state machine
4. Modular arithmetic: Wikipedia — Modular arithmetic