Problem 413: One-child Numbers

Project Euler Problem 413 Solution

EulerSolve provides an optimized solution for Project Euler Problem 413, One-child Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

Detailed mathematical approach

Problem Summary

A positive integer with $d$ decimal digits and no leading zero is a one-child number when exactly one of its substrings — any block of consecutive digits, read as a decimal number — is divisible by $d$. The statement lists all $10$ substrings of $5671$, of which only $56$ is divisible by $4$; $104$ qualifies because its only substring divisible by $3$ is the digit $0$; and $1132451$ because only $245$ is divisible by $7$. Writing $F(N)$ for the count of one-child numbers below $N$, we are given $F(10)=9$, $F(10^3)=389$ and $F(10^7)=277674$, and must find $F(10^{19})$. ^[1]

The divisor is the length itself, so each length needs its own count. Every positive integer below $10^{19}$ has $1$ to $19$ digits, so with $g(n)$ the number of one-child numbers of exactly $n$ digits,

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

The whole solution in one sentence: for each length $n$ we grow the number digit by digit from the left and carry only a short list saying, for every remainder modulo $n$, how many substrings ending at the current digit leave that remainder, with "two or more" lumped together, plus whether a divisible substring has already been found — little enough bookkeeping to count all $n$-digit numbers at once.

Mathematical Approach

1. Substrings, and the special role of the digit zero

A substring is fixed by its first and last position, so a number of length $n$ has $n(n+1)/2$ substrings: ten for $5671$ and $190$ for nineteen digits. One may begin with a zero and is then read as the smaller number it denotes: $04$ inside $104$ has the value $4$.

Since $0$ is divisible by every modulus, each digit zero is a divisible substring on its own. A one-child number therefore has at most one digit zero, and if it has one, that zero is its unique divisible substring — which is why $104$ qualifies.

2. Sorting the substrings by where they end

Every substring has exactly one last position, so grouping by it splits them with no overlap and no omission. Write the digits as $d_1,\dots,d_n$ with $d_1\ne0$; then for $1\le k\le n$ and $0\le r\lt n$ put

$$\begin{aligned}A_k(r)=\#\{\,&1\le i\le k:\\ &d_i\dots d_k\equiv r \pmod n\,\}.\end{aligned}$$

Then $A_k(0)$ counts the divisible substrings ending at $k$, and the one-child condition becomes one equation:

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

For $5671$ with $n=4$ the substrings ending at the four positions have residues $1$; $0,2$; $3,3,3$; and $3,3,3,1$, so $A_k(0)$ is $0,1,0,0$ and the sum is $1$.

3. One new digit at a time

Appending a digit $d$ multiplies a substring's value by $10$ and adds $d$, and congruences survive both operations, ^[3] so the extended substring has residue

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

From position $k$ to $k+1$, every substring ending at $k$ is extended, and one brand-new substring appears, the digit alone. With $\varepsilon_d(t)=1$ when $t\equiv d \pmod n$ and $0$ otherwise,

$$A_{k+1}(t)=\varepsilon_d(t)+\sum_{\varphi_d(r)=t}A_k(r).$$

The old substrings now enter only through their remainder counts, and the new digit only through $\varphi_d$ and $\varepsilon_d$. For $5671$ the vectors $\bigl(A_k(0),\dots,A_k(3)\bigr)$ are $(0,1,0,0)$, $(1,0,1,0)$, $(0,0,0,3)$, $(0,1,0,3)$, whose first entries are the numbers $0,1,0,0$ above.

4. Why counts above one may be forgotten

Those counts can grow, but a number dies as soon as two divisible substrings exist, so every test asks only whether a count is $0$, $1$, or at least $2$. Capping at $2$ is compatible with the additions of Section 3: with $b_i=\min(2,a_i)$ for non-negative integers $a_i$,

$$\min\Bigl(2,\sum_i b_i\Bigr)=\min\Bigl(2,\sum_i a_i\Bigr).$$

If $\sum_i a_i\le 1$ then every $a_i\le1$, so $b_i=a_i$ and both sides agree. If $\sum_i a_i\ge 2$, then either some $a_i\ge2$, giving $b_i=2$, or at least two $a_i$ equal $1$, giving $\sum_i b_i\ge2$; either way both sides are $2$. Capping after every step therefore gives what capping at the very end would give, and we may work with the profile

$$c_k(r)=\min\bigl(2,A_k(r)\bigr)\in\{0,1,2\}.$$

The last profile of $5671$ becomes $(0,1,0,2)$ instead of $(0,1,0,3)$.

5. The state and the two layers

This is where dynamic programming enters: prefixes carrying the same information about their continuations are merged, and only their number is kept. ^[9] That information is the current profile, which by Section 3 determines all later profiles, together with the total number of divisible substrings already in the prefix, which must be $0$ or $1$ since $2$ is a failure. By Sections 3 and 4 two prefixes agreeing in both react identically to every next digit, so they admit the same continuations and their counts may be stored together. The two layers are $L_0$ for "none so far" and $L_1$ for "exactly one so far", the count running over all substrings of the prefix, not only those ending at its last digit: $567$ already lies in $L_1$ for $n=4$, because of $56$.

Appending a digit gives a new profile whose entry $z=c_{k+1}(0)$ is the number of divisible substrings ending at the new position. A string in $L_0$ moves to $L_0$ if $z=0$, to $L_1$ if $z=1$, and dies if $z=2$; one in $L_1$ survives only when $z=0$. After all $n$ digits the strings in $L_1$ are exactly the one-child numbers, so $g(n)$ is the total stored there. The first digit, restricted to $1,\dots,9$, gives a profile with a single $1$ in class $d\bmod n$, in $L_1$ when $n\mid d$ and in $L_0$ otherwise.

6. Packing a profile into one integer

A profile is a vector in $\{0,1,2\}^n$, that is, a base-$3$ numeral with $n$ digits, so

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

is a bijection onto $\{0,1,\dots,3^n-1\}$ and serves as a hash-map key. At the largest length the bound is $3^{19}-1=1162261466$, below $2^{31}-1=2147483647$, so even a signed $32$-bit integer holds every key.

7. Worked example: the whole of $n=3$

Here $10\equiv1\pmod 3$, so $\varphi_d(r)=(r+d)\bmod 3$: a digit shifts the profile and adds one entry. Of the digits $0,\dots,9$, four are $\equiv0$ and three each are $\equiv1$ and $\equiv2$; among the leading digits it is three of each. The first digit gives three states, as profile with count:

$L_0$: $(0,1,0)$ with $3$ and $(0,0,1)$ with $3$;
$L_1$: $(1,0,0)$ with $3$, the digits $3,6,9$.

Appending a digit $\equiv0$ to $(1,0,0)$ leaves the $1$ in class $0$ and adds another there, so $z=2$ and those $3\cdot4=12$ numbers die. Everything else survives, leaving $90-12=78$ of the $90$ two-digit numbers in five states:

$L_0$: $(0,1,1)$ with $18$;
$L_1$: $(1,1,0)$ with $21$, $(1,0,1)$ with $21$, $(0,2,0)$ with $9$, $(0,0,2)$ with $9$.

Here $(1,1,0)$ collects $3\cdot4=12$ strings from $(0,1,0)$ plus a digit $\equiv0$ and $3\cdot3=9$ from $(0,0,1)$ plus a digit $\equiv1$. The third digit must bring the total to one, so it needs $z=1$ from $L_0$ and $z=0$ from $L_1$. All ten digits turn $(0,1,1)$ into $(1,1,1)$, contributing $18\cdot10=180$; each of the four $L_1$ states admits exactly one digit class, and $(1,1,0)$ with digits $\equiv1$ together with $(0,0,2)$ with digits $\equiv2$ give $(0,2,1)$, that is $21\cdot3+9\cdot3=90$, while $(1,0,1)$ and $(0,2,0)$ give $(0,1,2)$ with the same $90$. Hence

$$g(3)=180+90+90=360,$$

and with $g(1)=9$, $g(2)=20$ this reproduces $F(10^3)=9+20+360=389$.

8. A sharper picture when $n$ is coprime to $10$

For such $n$ the condition turns into a collision count, which proves several facts and gives an independent way to compute $g(n)$. Let $u_k$ be the value of the last $k$ digits, with $u_0=0$, so $u_n$ is the number itself. For $104$ with $n=3$ these values are $0,4,4,104$ with residues $0,1,1,2$: one equal pair, matching its one divisible substring $0$. Splitting off the tail behind position $j$ gives

$$u_{n-i+1}-u_{n-j}=v\cdot 10^{\,n-j},$$

with $v$ the value of $d_i\dots d_j$. As $\gcd(n,10)=1$, the factor $10^{\,n-j}$ is invertible modulo $n$, ^[3] so $n\mid v$ holds exactly when $u_{n-i+1}\equiv u_{n-j}$. The map $(i,j)\mapsto(n-i+1,\,n-j)$ is a bijection from the pairs with $1\le i\le j\le n$ onto the pairs $0\le b\lt a\le n$, so with $M_c$ the number of indices $k\in\{0,\dots,n\}$ having $u_k\equiv c$, the number $D$ of divisible substrings is

$$D=\sum_{c=0}^{n-1}\binom{M_c}{2}.$$

Three things follow. With $n+1$ indices in $n$ classes the pigeonhole principle ^[4] forces a collision, so when $\gcd(n,10)=1$ every $n$-digit number has a divisible substring. Next, $D=1$ means one class is hit twice and each other once, so the $u_k$ cover all $n$ classes. Finally $u_0=0$ lies in class $0$, so the end profile is all ones when the doubled class is $0$, and otherwise has an empty class $0$ and a $2$ elsewhere: exactly $n$ possibilities, and the program does end with $n$ profiles for every $n$ coprime to $10$.

For $n=3$ and $n=9$, where $10\equiv1$, the number $u_k$ is congruent to the sum of the last $k$ digits — the familiar digit-sum rule. ^[2] For $n=3$ the classes must then have sizes $2,1,1$, which $12$ of the $27$ digit residue patterns achieve, with weights summing to $8\cdot27+4\cdot36=360$ as in Section 7.

9. When divisibility only looks at the tail

Seven lengths divide a power of ten. For $n\in\{1,2,4,5,8,10,16\}$ the least positive $m$ with $n\mid 10^m$ is $1,1,2,1,3,1,4$, and a substring of length $L\ge m$ is then congruent modulo $n$ to its own last $m$ digits, because the part in front is a multiple of $10^m$. ^[2] So for $k\ge m$ the $k-m+1$ substrings of length at least $m$ ending at $k$ share one residue, while shorter ones are still checked individually; at $m=1$ closed forms drop out. The mixed lengths $6,12,14,15,18$ combine both pictures, splitting into a tail factor and a factor coprime to $10$.

$g(10)=0$. With $m=1$, divisibility by $10$ means a last digit $0$. If $d_k=0$ then all $k$ substrings ending at $k$ are divisible, so having exactly one forces $k=1$, a leading zero, which is forbidden; and if no digit is $0$ there is no divisible substring at all. No $10$-digit one-child number exists.
$g(2)=20$ and $g(5)=4096$. The same argument with "even", respectively "in $\{0,5\}$", in place of "zero": only $d_1$ may be such a digit, and it cannot be $0$. So $d_1\in\{2,4,6,8\}$ with $d_2$ odd, giving $4\cdot5=20$; and $d_1=5$ with $d_2,\dots,d_5\notin\{0,5\}$, giving $8^4=4096$.

10. How large the bookkeeping really gets

A state of $L_0$ has $c(0)=0$ and one of $L_1$ has $c(0)\le1$, so the two layers together admit at most $3^{n-1}+2\cdot3^{n-1}=3^n$ states, hopeless at $1162261467$ for $n=19$. Few are reachable, and the pruning of Section 5 removes most of the rest: measured, curr0 and curr1 hold together at most $9$ states for $n=10$, $139$ for $n=15$, $127270$ for $n=17$ and $529949$ for $n=19$, the last after ten of the nineteen digits and about $2200$ times below that bound; it splits into $43758$ states of $L_0$ and $486191$ of $L_1$.

The spread reflects the arithmetic of $n$: when $\gcd(n,10)\gt1$ multiplication by $10$ is not injective, so long substrings collapse into few residues and profiles merge. The measured counts show that $n=17$ and $n=19$ dominate the work.

How the Code Works

The C++ program ^[8] handles one length at a time in count_for_length(n). It tabulates digit_mod[d]${}=d\bmod n$ in ten entries and next_rem[d][r]${}=(10r+d)\bmod n$ of Section 3 in a ten-by-nineteen array using its first $n$ columns; encode_state and decode_state convert a profile to its base-$3$ key of Section 6 and back, and add_ways adds a count to a key.

The two layers of Section 5 are the hash maps curr0 and curr1 from key to string count, ^[6] seeded with the nine first digits. The loop over pos from $2$ to $n$ clears next0 and next1 and calls reserve on each with expected_states, the larger of $1024$ and twice the combined current size plus $16$; reserve asks for elements, not buckets. For every stored state and every digit the inner loop walks the $n$ entries of the decoded profile, sends a non-zero entry $c$ at residue $r$ to next_counts[next_rem[d][r]] under std::min(2, …), and adds the new single-digit substring at digit_mod[d]. The curr0 block files the result under $z=0$ or $z=1$ and drops it at $z=2$, the curr1 block keeps only $z=0$, and the values of curr1 are then summed. In main the nineteen results become a prefix array, so prefix[k] is $F(10^k)$, the numbers below $10^k$ being exactly those with at most $k$ digits, and run_checkpoints compares prefix[1], prefix[3] and prefix[7] with $9$, $389$ and $277674$, exiting with an error on any disagreement.

The Java version mirrors this with Map<Integer, Long> and merge(key, ways, Long::sum), which inserts a count or adds it to the stored one. ^[7] Its keys are int rather than the 64-bit keys of C++, which Section 6 shows to be safe, and its counts are long, which also suffices: by Section 1 a surviving prefix has at most one zero, so at most $9^k+(k-1)9^{k-1}$ prefixes of length $k$ survive, and summing over $k\le19$ bounds every stored count and the total by $4538017489057707798$, below $2^{63}-1$. Java allocates a fresh int[n] per decode and per digit trial where C++ reuses fixed nineteen-byte arrays, encodes the key before testing $z$ so that rejects are encoded too, computes an unused pow3n${}=3^n$, and runs no checkpoint comparison. The Python file is not a third implementation: it compiles solutionsCpp/Euler413.cpp with clang++ or g++ at -std=c++17 -O2 when the cached binary is missing or stale, runs it from the repository root, retries from the source directory on failure, and reads the result with parse_output: the last line matching answer:, else the text after the first = of the last line containing one, else the last non-empty line.

Complexity and Verification

Let $S_n(k)$ be the combined size of the two maps after $k$ digits and $S_n$ the largest of these. Building the tables costs $O(n)$. Each stored state is decoded once in $O(n)$ and tried with ten digits, and each trial clears, refills and encodes an $n$-entry profile. Assuming average constant-time hash-map operations, ^[6] one length costs

$$O\Bigl(n+n\sum_{k=1}^{n-1}S_n(k)\Bigr)\subseteq O\bigl(n^2S_n\bigr)$$

time. Four maps coexist during a transition, the two current and the two next ones, so the memory is $O(S_n+n)$, the $O(n)$ covering the tables and the temporary profiles. Over all nineteen lengths the digit loops perform $41460940$ state-and-digit expansions and $764017700$ residue steps; initialising, decoding, encoding, hashing and the final summation are not counted in those figures. Measured with Homebrew clang++ 22 at -O2 and OpenJDK $17$, the C++ program needs about $2.6$ seconds and $100$ MiB of resident memory, the Java version about $6$ seconds and the Python bridge $3.3$ seconds including compilation.

Besides the C++ checkpoints, these checks were run for this article; they are not part of the published sources.

A direct scan of all $n$-digit numbers, testing every substring, gives $9$, $20$, $360$, $2701$, $4096$, $109466$, $161022$ and $13068583$ for $n=1,\dots,8$; these match the recurrence and the three checkpoints.
The same recurrence with exact counts, without the cap of Section 4, agrees for every $n\le17$; this tests the capping lemma instead of assuming it.
The closed forms of Section 9 agree, and a program deciding divisibility only from the last $m$ digits reproduces $g(n)$ for $n\in\{1,2,4,5,8,10,16\}$.
The digit-sum criterion reproduces $g(3)$ and $g(9)$, and splitting the mixed lengths by the Chinese remainder theorem ^[5] reproduces $g(n)$ for $n\in\{6,12,14,15,18\}$.
The collision count of Section 8, evaluated by a right-to-left search over the values $u_k$, reproduces $g(n)$ for $n\in\{1,3,7,9,11,13,17,19\}$, the longest length included.

Together these cover every length from $1$ to $19$ by at least one structurally different computation, and the three published runs print the same value.

Footnotes and References

The references supply the background facts used above. The suffix profiles, the capping lemma, the collision count for $n$ coprime to $10$ and the closed forms for $n\in\{2,5,10\}$ are derived explicitly here.

Project Euler 413 — One-child Numbers. The official statement defines a one-child number as a d-digit number with no leading zeros exactly one of whose sub-strings is divisible by d, gives 5671, 104 and 1132451 as examples, and states F(10) = 9, F(10³) = 389 and F(10⁷) = 277674 before asking for F(10¹⁹).
Wikipedia — Divisibility rule. It gives the digit-sum tests for 3 and 9 and the trailing-digit tests for 2, 4, 5, 8, 10 and 16, with the rule that divisibility by 2ᵐ, 5ᵐ or 10ᵐ is decided by the last m digits.
Wikipedia — Modular arithmetic. Congruences survive addition and multiplication, which justifies Section 3, and a is invertible modulo m exactly when a and m are coprime, which Section 8 needs.
Wikipedia — Pigeonhole principle. If n items go into m containers with n greater than m, some container holds more than one; the article notes that this only shows an overlap exists, and Section 8 counts the overlaps separately.
Wikipedia — Chinese remainder theorem. Integers with equal remainders modulo pairwise coprime moduli differ by a multiple of the product, so divisibility by a product of coprime factors means divisibility by each, as the cross-checks use.
cppreference — std::unordered_map. Elements sit in buckets chosen by the hash of the key, search and insertion cost average constant time, and reserve makes room for a number of elements, not of buckets.
Java — java.util.Map. Its merge associates an absent key with the given value and otherwise replaces the stored value by the result of the remapping function, which is how the Java port accumulates counts.
C++ — Euler413.cpp. The linked immutable revision contains encode_state, decode_state, add_ways, count_for_length and run_checkpoints; it is the implementation record for this article, and the extra comparisons above are not tests in that file.
Wikipedia — Dynamic programming. It describes breaking a problem into recurring subproblems, solving each once and reusing the stored result; here a subproblem is a digit position with a state.

Problem 413 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

namespace {

using u64 = std::uint64_t;

using StateMap = std::unordered_map<u64, u64>;

u64 encode_state(const std::array<std::uint8_t, 19>& counts, int n) {
    u64 key = 0;
    u64 mul = 1;
    for (int i = 0; i < n; ++i) {
        key += static_cast<u64>(counts[i]) * mul;
        mul *= 3ULL;
    }
    return key;
}

void decode_state(u64 key, int n, std::array<std::uint8_t, 19>& counts) {
    for (int i = 0; i < n; ++i) {
        counts[i] = static_cast<std::uint8_t>(key % 3ULL);
        key /= 3ULL;
    }
}

inline void add_ways(StateMap& map, u64 key, u64 ways) {
    const auto it = map.find(key);
    if (it == map.end()) {
        map.emplace(key, ways);
    } else {
        it->second += ways;
    }
}

u64 count_for_length(int n) {
    std::array<std::array<int, 19>, 10> next_rem{};
    std::array<int, 10> digit_mod{};
    for (int d = 0; d <= 9; ++d) {
        digit_mod[d] = d % n;
        for (int r = 0; r < n; ++r) {
            next_rem[d][r] = (10 * r + digit_mod[d]) % n;
        }
    }

    StateMap curr0;
    StateMap curr1;
    curr0.reserve(1024);
    curr1.reserve(1024);

    std::array<std::uint8_t, 19> counts{};
    for (int d = 1; d <= 9; ++d) {
        std::fill(counts.begin(), counts.begin() + n, 0);
        counts[digit_mod[d]] = 1;
        const u64 key = encode_state(counts, n);
        if (counts[0] == 0) {
            add_ways(curr0, key, 1);
        } else if (counts[0] == 1) {
            add_ways(curr1, key, 1);
        }
    }

    StateMap next0;
    StateMap next1;

    std::array<std::uint8_t, 19> next_counts{};

    for (int pos = 2; pos <= n; ++pos) {
        const std::size_t expected_states =
            std::max<std::size_t>(1024, (curr0.size() + curr1.size()) * 2 + 16);
        next0.clear();
        next1.clear();
        next0.reserve(expected_states);
        next1.reserve(expected_states);

        for (const auto& entry : curr0) {
            const u64 key = entry.first;
            const u64 ways = entry.second;
            decode_state(key, n, counts);

            for (int d = 0; d <= 9; ++d) {
                std::fill(next_counts.begin(), next_counts.begin() + n, 0);
                for (int r = 0; r < n; ++r) {
                    const std::uint8_t c = counts[r];
                    if (!c) continue;
                    const int nr = next_rem[d][r];
                    const std::uint8_t sum = static_cast<std::uint8_t>(
                        std::min<int>(2, next_counts[nr] + c));
                    next_counts[nr] = sum;
                }
                const int dr = digit_mod[d];
                next_counts[dr] = static_cast<std::uint8_t>(std::min<int>(2, next_counts[dr] + 1));

                const int zeros = next_counts[0];
                if (zeros == 0) {
                    add_ways(next0, encode_state(next_counts, n), ways);
                } else if (zeros == 1) {
                    add_ways(next1, encode_state(next_counts, n), ways);
                }
            }
        }

        for (const auto& entry : curr1) {
            const u64 key = entry.first;
            const u64 ways = entry.second;
            decode_state(key, n, counts);

            for (int d = 0; d <= 9; ++d) {
                std::fill(next_counts.begin(), next_counts.begin() + n, 0);
                for (int r = 0; r < n; ++r) {
                    const std::uint8_t c = counts[r];
                    if (!c) continue;
                    const int nr = next_rem[d][r];
                    const std::uint8_t sum = static_cast<std::uint8_t>(
                        std::min<int>(2, next_counts[nr] + c));
                    next_counts[nr] = sum;
                }
                const int dr = digit_mod[d];
                next_counts[dr] = static_cast<std::uint8_t>(std::min<int>(2, next_counts[dr] + 1));

                if (next_counts[0] == 0) {
                    add_ways(next1, encode_state(next_counts, n), ways);
                }
            }
        }

        curr0.swap(next0);
        curr1.swap(next1);
    }

    u64 total = 0;
    for (const auto& entry : curr1) {
        total += entry.second;
    }
    return total;
}

bool run_checkpoints(const std::vector<u64>& prefix) {
    struct Checkpoint {
        int digits;
        u64 expected;
    };
    const Checkpoint checks[] = {
        {1, 9},
        {3, 389},
        {7, 277674},
    };
    for (const auto& checkpoint : checks) {
        if (prefix[checkpoint.digits] != checkpoint.expected) {
            return false;
        }
    }
    return true;
}

}  // namespace

int main() {
    std::vector<u64> counts(20, 0);
    for (int n = 1; n <= 19; ++n) {
        counts[n] = count_for_length(n);
    }

    std::vector<u64> prefix(20, 0);
    for (int n = 1; n <= 19; ++n) {
        prefix[n] = prefix[n - 1] + counts[n];
    }

    if (!run_checkpoints(prefix)) {
        std::cerr << "Checkpoint failed\n";
        return 1;
    }

    std::cout << "F(10^19) = " << prefix[19] << '\n';
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""
    answers = []
    equals = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answers.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equals.append(m2.group(1).strip())
    if answers:
        return answers[-1]
    if equals:
        return equals[-1]
    return lines[-1]


def should_skip_cpp_checkpoints(src: Path) -> bool:
    try:
        text = src.read_text(encoding="utf-8", errors="ignore")
    except OSError:
        return False
    return "--skip-checkpoints" in text


def run_cpp(binary: Path, src: Path, root: Path) -> str:
    cmd = [str(binary)]
    if should_skip_cpp_checkpoints(src):
        cmd.append("--skip-checkpoints")

    try:
        return subprocess.check_output(cmd, text=True, cwd=root)
    except subprocess.CalledProcessError:
        return subprocess.check_output(cmd, text=True, cwd=src.parent)


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = run_cpp(binary=binary, src=src, root=root)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


if __name__ == "__main__":
    print(solve())

Java

import java.util.*;

public class Euler413 {
    public static String solve() {
        long total = 0;
        for (int n = 1; n <= 19; n++)
            total += countForLength(n);
        return String.valueOf(total);
    }

    static long countForLength(int n) {
        int[] digitMod = new int[10];
        for (int d = 0; d < 10; d++)
            digitMod[d] = d % n;
        int[][] nextRem = new int[10][n];
        for (int d = 0; d < 10; d++)
            for (int r = 0; r < n; r++)
                nextRem[d][r] = (10 * r + digitMod[d]) % n;

        int pow3n = 1;
        for (int i = 0; i < n; i++)
            pow3n *= 3;

        Map<Integer, Long> curr0 = new HashMap<>(), curr1 = new HashMap<>();
        for (int d = 1; d <= 9; d++) {
            int[] counts = new int[n];
            counts[digitMod[d]] = 1;
            int key = encode(counts, n);
            if (counts[0] == 0)
                curr0.merge(key, 1L, Long::sum);
            else if (counts[0] == 1)
                curr1.merge(key, 1L, Long::sum);
        }

        for (int pos = 2; pos <= n; pos++) {
            Map<Integer, Long> next0 = new HashMap<>(), next1 = new HashMap<>();
            for (var entry : curr0.entrySet()) {
                int[] counts = decode(entry.getKey(), n);
                long ways = entry.getValue();
                for (int d = 0; d < 10; d++) {
                    int[] nc = new int[n];
                    for (int r = 0; r < n; r++) {
                        int c = counts[r];
                        if (c == 0)
                            continue;
                        int nr = nextRem[d][r];
                        nc[nr] = Math.min(2, nc[nr] + c);
                    }
                    int dr = digitMod[d];
                    nc[dr] = Math.min(2, nc[dr] + 1);
                    int nk = encode(nc, n);
                    if (nc[0] == 0)
                        next0.merge(nk, ways, Long::sum);
                    else if (nc[0] == 1)
                        next1.merge(nk, ways, Long::sum);
                }
            }
            for (var entry : curr1.entrySet()) {
                int[] counts = decode(entry.getKey(), n);
                long ways = entry.getValue();
                for (int d = 0; d < 10; d++) {
                    int[] nc = new int[n];
                    for (int r = 0; r < n; r++) {
                        int c = counts[r];
                        if (c == 0)
                            continue;
                        int nr = nextRem[d][r];
                        nc[nr] = Math.min(2, nc[nr] + c);
                    }
                    int dr = digitMod[d];
                    nc[dr] = Math.min(2, nc[dr] + 1);
                    if (nc[0] == 0) {
                        int nk = encode(nc, n);
                        next1.merge(nk, ways, Long::sum);
                    }
                }
            }
            curr0 = next0;
            curr1 = next1;
        }
        long sum = 0;
        for (long v : curr1.values())
            sum += v;
        return sum;
    }

    static int encode(int[] counts, int n) {
        int key = 0, mul = 1;
        for (int i = 0; i < n; i++) {
            key += counts[i] * mul;
            mul *= 3;
        }
        return key;
    }

    static int[] decode(int key, int n) {
        int[] counts = new int[n];
        for (int i = 0; i < n; i++) {
            counts[i] = key % 3;
            key /= 3;
        }
        return counts;
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}