Project Euler Problem 413
We say that a d-digit positive number (no leading zeros) is a one-child number if exactly one of its sub-strings is divi
Solution
Answer: 3079418648040719
For a fixed digit length $d$, define a $d$-digit number
$$a_1a_2\cdots a_d.$$
Every substring ending at the current digit can be tracked modulo $d$.
If we append a new digit $x$, then every previous suffix remainder $r$ becomes
$$(10r+x)\bmod d,$$
and the one-digit suffix contributes $x\bmod d$.
A substring is divisible by $d$ exactly when its remainder is $0$.
So we can perform a digit-DP over states consisting of:
- the multiset/count-vector of suffix remainders,
- how many divisible substrings have appeared so far.
We prune immediately once the count exceeds $1$.
Summing the counts for all digit lengths $1\le d\le 19$ gives:
$$F(10)=9,\qquad F(10^3)=389,\qquad F(10^7)=277674,$$
matching the values given in the problem statement.
Carrying the DP through $d=19$ yields the exact value
$$F(10^{19}) = 3079418648040719.$$
Answer: 3079418648040719