Problem 316: Numbers in Decimal Expansions

Project Euler Problem 316 Solution

EulerSolve provides an optimized solution for Project Euler Problem 316, Numbers in Decimal Expansions, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $$p=p_1p_2p_3\cdots$$ be an infinite random decimal stream, where each digit is chosen independently and uniformly from $\{0,\dots,9\}$. For a positive integer $n$ with decimal representation $$s=s_1s_2\cdots s_d,$$ let $k$ be the first position where the block $s$ appears in the stream. The problem asks for $$\sum_{m=2}^{999999} g\!\left(\left\lfloor\frac{10^{16}}{m}\right\rfloor\right),$$ where $g(n)=\mathbb E[k]$. Mathematical Approach 1) End position is more convenient than start position. If the first occurrence of $s$ starts at position $k$, then it ends at $$T_{\mathrm{end}}=k+d-1.$$ So once we know the expected ending index, we recover the required quantity by $$g(n)=\mathbb E[T_{\mathrm{end}}]-d+1.$$ This is why the code first computes an expected end position and only subtracts $d-1$ at the very end. 2) KMP states give the exact Markov chain. State $i\in\{0,\dots,d\}$ means that the longest suffix of the digits seen so far equals the prefix $s_1\cdots s_i$. State $d$ is absorbing because the pattern has already appeared. If $E_i$ is the expected number of additional digits needed to reach state $d$, then the exact linear system is $$E_d=0,$$ $$E_i=1+\frac1{10}\sum_{x=0}^{9} E_{\delta(i,x)} \qquad (0\le i\lt d),$$ where $\delta(i,x)$ is the usual KMP transition after reading digit $x$....

Detailed mathematical approach

Problem Summary

Let $p=p_1p_2p_3\cdots$ be an infinite sequence of digits drawn independently and uniformly from $\{0,1,\dots,9\}$; equivalently, $0.p_1p_2p_3\cdots$ is a uniform random real in $[0,1)$. For a positive integer $n$ with $d$ decimal digits, let $k$ be the smallest index such that $p_k,p_{k+1},\dots,p_{k+d-1}$ are the digits of $n$ in that order, and let $g(n)$ be the expected value of $k$. The statement remarks that $g(n)$ is always finite and always an integer; for $n=535$ it gives the stream $31415926535897\cdots$, whose first copy of $535$ starts at $k=9$, a second stream starting it at $k=36$, and $g(535)=1008$. We must evaluate

$$\sum_{n=2}^{999999}g\bigl(\lfloor 10^{16}/n\rfloor\bigr),$$

given that the same sum with $10^{6}$ in place of $10^{16}$ and $n$ running only to $999$ equals $27280188$. ^[1]

The whole solution in one sentence: for each quotient add $10^{d}$ and one power $10^{L}$ for every shorter length $L$ at which its leading $L$ digits reappear at its end, subtract $d-1$ to turn the expected finishing position into the expected start, and add the $999998$ results.

Mathematical Approach

Once $g$ can be evaluated in a few operations the outer sum is a plain loop, so all the mathematics goes into $g$, where the key fact is that only the self-overlaps of the digit block matter.

1. The end of the block instead of its start

The two descriptions in the statement are one experiment: the first $d$ digits of a uniform $x\in[0,1)$ are fixed exactly when $x$ lies in one of the $10^{d}$ equally long intervals $[a\cdot10^{-d},(a+1)\cdot10^{-d})$, so each digit string has probability $10^{-d}$.

Write the digits of $n$ as $n_1n_2\cdots n_d$. The index at which the first copy ends is easier to study than the one at which it starts, so put

$$T=\min\{t\ge d: p_{t-d+1}\cdots p_t=n_1\cdots n_d\}.$$

Since an occurrence starting at $k$ ends at $k+d-1$, we have $T=k+d-1$ in every stream, so $g(n)=\mathbb E[T]-d+1$. Everything below computes $\mathbb E[T]$.

2. The waiting time is finite

Cut the stream into consecutive blocks of $d$ digits, positions $1..d$, then $d+1..2d$, and so on. Each equals $n_1\cdots n_d$ with probability $10^{-d}$, independently of the others, so the number of blocks until the first match is geometric with mean $10^{d}$. ^[2] A match inside a block puts $T$ no later than its end, hence

$$\mathbb E[T]\le d\cdot 10^{d}\lt\infty.$$

This crude bound is all we need; the true value is close to $10^{d}$.

3. Two waiting times computed by hand

For a single digit, $T$ is geometric with mean $10$, so $g(n)=10$ for every $n$ from $1$ to $9$.

Now take $n=11$ and track how much of the block the stream matches: state $0$ means the last digit was not $1$, state $1$ means it was. Let $a$ and $b$ be the expected further digits needed from each. From state $0$ the next digit is a $1$ with probability $\tfrac1{10}$; from state $1$ another $1$ finishes the block and the other nine reset us:

$$\begin{aligned}a&=1+\tfrac1{10}b+\tfrac9{10}a,\\ b&=1+\tfrac9{10}a.\end{aligned}$$

The first line gives $a=10+b$; substituting into the second yields $a=110$ and $b=100$. So $\mathbb E[T]=110$ and $g(11)=110-2+1=109$.

For $n=12$ one transition changes: from state $1$ the digit $2$ finishes the block, a $1$ keeps us there, and the other eight digits reset us:

$$\begin{aligned}a&=1+\tfrac1{10}b+\tfrac9{10}a,\\ b&=1+\tfrac1{10}b+\tfrac8{10}a.\end{aligned}$$

Now $a=100$ and $b=90$, so $g(12)=100-2+1=99$.

The answers differ, although each block sits at a fixed pair of positions with probability $\tfrac1{100}$. The block $11$ waits longer, because its copies cluster: a run such as $11111$ contains four copies of $11$, while two copies of $12$ can never overlap. Both occupy the same long-run fraction $10^{-2}$ of positions, so the copies of $11$ come in bunches separated by longer gaps, and a longer first gap means a larger $\mathbb E[T]$.

4. Self-overlap: the borders of a digit block

A border of a string $w$ of length $d$ is a length $L$ with $0\lt L\lt d$ such that the first $L$ characters of $w$ equal its last $L$ characters. Let $\mathcal B(n)$ be the set of borders of the digit string of $n$. Four examples, all checked digit by digit:

$n=12$: $\mathcal B=\varnothing$, because $1\ne2$;
$n=535$: $\mathcal B=\{1\}$, since the string begins and ends with $5$ but $53\ne35$;
$n=111$: $\mathcal B=\{1,2\}$;
$n=90909$: $\mathcal B=\{1,3\}$, since $909$ is both a prefix and a suffix, while $90\ne09$ and $9090\ne0909$.

A border of length $L$ is exactly a way for two copies of the block to overlap in $L$ positions, so $\mathcal B(n)$ records every possible self-overlap.

5. A team of gamblers

A fair-game model turns those overlaps into an expected value. A casino admits one new player at every step $t=1,2,3,\dots$, each bringing one unit of capital. Player $t$ stakes it on $p_t=n_1$; the casino pays ten times the stake if the guess is right and nothing otherwise, which is fair for a uniform digit. A winner at once stakes the whole payout on $p_{t+1}=n_2$, then on $p_{t+2}=n_3$, holding $10^{L}$ after $L$ correct guesses. A wrong guess leaves that player with nothing; guessing all $d$ digits ends the visit with $10^{d}$ carried off.

Let $W_t$ be the total wealth of everyone admitted up to step $t$: the current stake of a player still betting, the payout already carried off by a player who completed the block, and $0$ for a player who lost. Put $M_t=W_t-t$, subtracting the capital each arrival brought. Given the digits read so far, every stake keeps its value in expectation and the newcomer adds one unit, so $\mathbb E[W_{t+1}\mid\mathcal F_t]=W_t+1$ and $\mathbb E[M_{t+1}\mid\mathcal F_t]=M_t$: a martingale with $M_0=0$. ^[3] At each step at most $d$ players bet, the newcomer included, each staking at most $10^{d-1}$, and a bet either wipes out a stake or multiplies it by ten, so

$$|M_{t+1}-M_t|\le 9d\cdot 10^{d-1},$$

a bound depending only on $d$.

6. The players' wealth at time $T$

Stop at the time $T$ of Section 1. By then $T$ players have arrived with $T$ units of capital between them. For $1\le L\le d$, the player admitted at step $T-L+1$ still has wealth exactly when all $L$ of their guesses succeeded, that is when

$$p_{T-L+1}\cdots p_T=n_1\cdots n_L.$$

By the definition of $T$ the last $d$ digits read are $n_1\cdots n_d$, so the left-hand side is the suffix of length $L$ of the block, and it equals the prefix of length $L$ exactly when $L=d$ or $L\in\mathcal B(n)$. Such a player accounts for $10^{L}$: for $L=d$ the payout of the one player who completed the block, for shorter $L$ a stake still on the table.

Everyone admitted at a step $j\le T-d$ has lost: an unbroken run would have completed the block at step $j+d-1\lt T$, contradicting the minimality of $T$. Hence

$$M_T=\sum_{L\in\mathcal B(n)\cup\{d\}}10^{L}-T.$$

7. The waiting-time formula

Whether the block has appeared by step $t$ is decided by the first $t$ digits, so $T$ is a stopping time; Section 2 gives $\mathbb E[T]\lt\infty$ and Section 5 a martingale with bounded increments. These are exactly the hypotheses under which the optional stopping theorem gives $\mathbb E[M_T]=\mathbb E[M_0]=0$. ^[4] Taking expectations in the identity of Section 6 therefore proves

$$\mathbb E[T]=\sum_{L\in\mathcal B(n)\cup\{d\}}10^{L}.$$

This is the classical waiting-time formula for a pattern in an independent letter stream; collecting the exponents into $c(z)=\sum_{L}z^{\,d-L}$, with $L$ over $\mathcal B(n)\cup\{d\}$, gives the autocorrelation polynomial and turns the right-hand side into $10^{d}c(1/10)$, the standard form. ^[5] Section 3 agrees: $n=11$ has borders $\{1\}$, giving $110$, and $n=12$ has none, giving $100$.

8. From the end index back to $g(n)$

Combining the formula with $g(n)=\mathbb E[T]-d+1$ gives the expression the program evaluates:

$$g(n)=\sum_{L\in\mathcal B(n)\cup\{d\}}10^{L}-d+1.$$

Both remarks of the statement follow at once. The value is an integer, being a sum of powers of ten minus an integer. And since the borders are distinct lengths below $d$,

$$10^{d}-d+1\le g(n)\le\frac{10^{d+1}-10}{9}-d+1,$$

the lower bound holding when the block has no self-overlap, the upper when all $d-1$ borders occur, which needs all $d$ digits equal. They differ by a factor of about $1.11$, so even the most overlapping block waits only some $11\%$ longer than a generic one.

9. All borders from one left-to-right pass

Testing each $L$ separately costs $O(d^{2})$ character comparisons; the prefix table of Knuth–Morris–Pratt string matching does it in $O(d)$. ^[6] For $1\le i\le d$ let $\pi_i$ be the length of the longest border of the prefix of length $i$, or $0$ when it has none. To get $\pi_i$ for $i\ge2$, start from $j=\pi_{i-1}$ and compare $n_i$ with $n_{j+1}$: on a match put $\pi_i=j+1$; on a mismatch with $j\gt0$ replace $j$ by $\pi_j$ and retry; if $j=0$ and they still differ put $\pi_i=0$. Deleting the last digit of a border of the prefix of length $i$ leaves a border of the prefix of length $i-1$, so these candidates are exhaustive. For $1211$ the table is $\pi=(0,0,1,1)$: the prefix $121$ has border $1$, extending it would need a $2$, so $j$ drops to $0$ and the final $1$ starts a fresh border. The candidate rises by at most one per digit and every fallback lowers it, so the table costs $O(d)$ comparisons. ^[7]

The borders of the whole block then come from iterating $\pi$. Write $w_{1..i}$ for the prefix of length $i$ and put $b=\pi_d$. We claim that $\mathcal B(w)=\{b\}\cup\mathcal B(w_{1..b})$ whenever $b\ge1$. Let $L$ be a border of $w_{1..b}$: then $w_{1..L}$ is the suffix of length $L$ of $w_{1..b}$, which is itself the suffix of length $b$ of $w$, so $w_{1..L}$ is also a suffix of $w$ and $L$ is a border of $w$. Conversely let $L\lt b$ be a border of $w$: the suffix of length $L$ of $w$ lies inside its suffix of length $b$, namely $w_{1..b}$, and equals $w_{1..L}$, so $L$ is a border of $w_{1..b}$. By the maximality of $b$ no border satisfies $b\lt L\lt d$. Applying the claim repeatedly shows that the chain

$$d,\ \pi_d,\ \pi_{\pi_d},\ \dots$$

lists $d$ and then every border exactly once, in strictly decreasing order, and stops at $0$, a marker that contributes nothing. There are at most $d$ positive entries, so the table and the chain together evaluate $g(n)$ in $O(d)$ time and $O(d)$ memory.

10. Two worked values

For $n=535$ the table is $\pi_1=0$, $\pi_2=0$, $\pi_3=1$: the prefix $5$ is also a suffix, but $53\ne35$. The chain is $3\to1\to0$, so $\mathbb E[T]=10^{3}+10^{1}=1010$ and $g(535)=1010-3+1=1008$, the value in the statement.

For a block with two borders take $n=90909$, which is $\lfloor 10^{6}/11\rfloor$ and so really occurs in the smaller sum. Here $\pi=(0,0,1,2,3)$ and the chain is $5\to3\to1\to0$, so

$$\mathbb E[T]=10^{5}+10^{3}+10^{1}=101010,$$

giving $g(90909)=101006$. The first-step method of Section 3, with the five states for matched prefix lengths $0$ to $4$, returns $101010$ as well.

11. The outer sum has no repetitions

Sums of the shape $\sum_n F(\lfloor X/n\rfloor)$ are often collapsed by grouping equal quotients, but here that gains nothing. If $1\le n\lt m$ and $nm\lt X$, then

$$\frac{X}{n}-\frac{X}{m}=\frac{X(m-n)}{nm}\ge\frac{X}{nm}\gt1,$$

so $\lfloor X/n\rfloor\gt\lfloor X/m\rfloor$. With $X=10^{16}$ and $m\le 999999$ we have $nm\lt 10^{12}\lt X$, so the $999998$ quotients are pairwise distinct, as a direct count confirms; grouping saves nothing here, and the published solutions evaluate each quotient on its own.

A quotient has exactly $d$ digits when $10^{d-1}\le 10^{16}/n\lt 10^{d}$, that is when $10^{16-d}\lt n\le 10^{17-d}$. Intersecting with $2\le n\le 999999$ gives $16$ digits for the $9$ indices $n=2,\dots,10$, then $15$ digits for $90$ indices, $14$ for $900$, $13$ for $9000$, $12$ for $90000$ and $11$ for the remaining $899999$. Each class holds about ten times as many terms as the one before, each about ten times smaller, so the six subtotals are nearly equal. A class of $d$-digit quotients has at most $9\cdot10^{16-d}$ terms and Section 8 bounds every term below $\tfrac{10}{9}10^{d}$, so each class contributes less than $10^{17}$ and the sum less than $6.0\cdot10^{17}$ — about $6.5\%$ of $2^{63}-1$, and since every term is positive this bounds every partial sum too.

Only $110959$ of the $999998$ quotients, about $11\%$, have a border at all, as expected since a random block repeats its first digit at the end with probability $\tfrac1{10}$. Their extra powers shift the total by well under one percent, yet dropping them would give a wrong sum. At the extreme, $n=3$ and $n=9$ give the quotients $3333333333333333$ and $1111111111111111$, with all $15$ possible borders; the first is the largest single term, $g=11111111111111095$.

12. A slice of the smaller sum

The smaller sum in the statement is a complete test of the method. Its first nine terms, with $q=\lfloor 10^{6}/n\rfloor$ and the border chain written out, are

$n=2$, $q=500000$, chain $6$, $g=999995$;
$n=3$, $q=333333$, chain $6,5,4,3,2,1$, $g=1111105$;
$n=4$, $q=250000$, chain $6$, $g=999995$;
$n=5$, $q=200000$, chain $6$, $g=999995$;
$n=6$, $q=166666$, chain $6$, $g=999995$;
$n=7$, $q=142857$, chain $6$, $g=999995$;
$n=8$, $q=125000$, chain $6$, $g=999995$;
$n=9$, $q=111111$, chain $6,5,4,3,2,1$, $g=1111105$;
$n=10$, $q=100000$, chain $6$, $g=999995$.

Their sum is $9222175$. The constant-digit quotients $333333$ and $111111$ are the only two of the nine with borders, each contributing $111110$ more than a block with none. Continuing to $n=999$, where the quotients have $4$, $5$ or $6$ digits and $128$ of the $998$ have a border, reproduces the stated $27280188$.

How the Code Works

The C++ program ^[8] transcribes Sections 8 to 11 directly. build_pow10 fills an std::array of twenty $128$-bit values with $10^{0},\dots,10^{19}$, so the chain sum never multiplies at run time.

g_value converts one block with std::to_string and sets d to the length of that string; working from the decimal text is what makes the border machinery available at all. The first loop builds the prefix table pi by the recurrence of Section 9, its inner while performing the fallback; pi is zero-based, so $\pi_i$ is pi[i - 1]. The second loop walks the chain $d,\pi_d,\pi_{\pi_d},\dots$, adding pow10[len] to expected_end and stopping when len reaches $0$; it returns expected_end - d + 1, which is $g(n)$.

solve_sum(numerator, max_n, pow10) is the outer loop of Section 11: it adds g_value(numerator / n, pow10) for $n=2,\dots,\mathtt{max\_n}$ and nothing else. run_checkpoints checks $g(535)=1008$, then compares solve_sum at $(10^{6},999)$ with $27280188$, reporting a failure on standard error so that main exits with status $2$. The flag --skip-checkpoints suppresses both checks and any other argument is rejected; main then calls solve_sum at $(10^{16},999999)$. Since unsigned __int128 has no stream output, to_string_u128 converts the total digit by digit and reverses it. ^[9]

The Python version runs the same algorithm: g_value builds pi with the identical loop and walks the chain with expected_end += 10 ** k, computing each power on the spot instead of reading a table, while solve takes each quotient as numerator // n and returns str(total). Python's integers have unlimited precision, so no range question arises. ^[10]

In Java, main prints what solve returns; solve calls buildPow10 and adds gValue(numerator / n, pow10) across the loop, integer division of positive values giving the floor. gValue uses String.valueOf, s.charAt and an int[] table for the same two loops, and every value is a long — sound, because the bound of Section 11 keeps the total near $6\%$ of Long.MAX_VALUE and every term is positive, so no partial sum can overflow. ^[10] buildPow10 does fill a long[20] whose last entry $10^{19}$ exceeds the signed $64$-bit range and wraps around; it is never read, since the longest quotient $5000000000000000$ has only $16$ digits, so the result is unaffected.

Complexity and Verification

The decimal conversion, the prefix table and the chain traversal each cost $O(d_n)$ for a quotient of $d_n$ digits, so the running time is $O\bigl(\sum_n d_n\bigr)$, and Section 11 makes $\sum_n d_n=11111083$ — a count of input digits, not of operations, since every fallback in the table loop costs an extra comparison. Storage is $O(d_n)$ for the current string and table plus the twenty fixed powers of ten, and $d_n\le16$, so memory does not grow with the number of terms. On one laptop the C++ build needs $0.04$ s including the checkpoints, Java $0.06$ s and Python $0.75$ s.

All three programs print the same total; only the C++ file carries the two statement checkpoints.

These further checks were run for this article and are not part of the published solutions.

The border formula of Section 8 was compared with exact first-step equations for every $n$ up to $3000$ and for $300$ random $16$-digit blocks: states for the longest prefix currently matching a suffix of the stream, transitions built by direct prefix-against-suffix comparison rather than from the prefix table, and Gaussian elimination in exact rational arithmetic. Every value agreed.
The border chain was compared with a direct test of all $d-1$ possible borders for every $n$ up to $20000$ and for $20000$ random strings of length at most $18$ over $\{0,1\}$, where borders are abundant. The sets were always identical.
Random digit streams were simulated $200000$ times per block, recording the start index $k$. For $7$, $11$, $12$, $123$, $535$ and $111$ the sample means $9.97$, $108.92$, $98.94$, $993.24$, $1010.34$ and $1109.39$ sit beside the exact $10$, $109$, $99$, $998$, $1008$ and $1108$. The same systems extended to second moments give the variances $90$, $11790$, $9700$, $995000$, $1015090$ and $1226790$, hence standard errors $0.0212$, $0.2428$, $0.2202$, $2.2305$, $2.2529$ and $2.4767$; the largest deviation is $2.13$ standard errors, for $123$. Simulation confirms the scale only — the exact comparisons above are the check.
A second implementation that tests every possible border directly, with no prefix table anywhere, reproduced $27280188$ and agreed with all three programs at the full size.

Footnotes and References

The references below supply the background facts used above. The martingale argument, the border-chain claim and the $64$-bit bound are derived explicitly in this article.

Project Euler 316 — Numbers in Decimal Expansions. The official statement defines the stream of uniform random digits and g(n) as the expected index at which the digits of n first appear consecutively, notes that g(n) is always a finite integer, gives g(535) = 1008, and states 27280188 for the sum with numerator 10⁶ over n = 2 … 999 before asking the same with numerator 10¹⁶.
Wikipedia — Geometric distribution. For the version counting trials up to and including the first success the mean is 1/p, used in Section 2 with p = 10⁻ᵈ and in Section 3 with p = 1/10.
Wikipedia — Martingale (probability theory). A martingale's conditional expectation of the next value, given all earlier ones, equals the current value, and the article names a gambler's fortune under fair bets as an example — the quantity of Section 5.
Wikipedia — Optional stopping theorem. It gives E[X_τ] = E[X₀] under any one of three conditions, the second being a stopping time of finite expectation together with conditional absolute increments bounded by a constant — the pair verified in Sections 2 and 5.
Wikipedia — Autocorrelation (words). The autocorrelation of a word records the lengths at which a prefix equals a suffix, and the article gives the expected first occurrence of a word of length n over an alphabet A as |A|ⁿ·c(1/|A|), with c the autocorrelation polynomial: the formula proved in Section 7, for |A| = 10.
Wikipedia — Knuth–Morris–Pratt algorithm. Its partial match table holds, at each position, the length of the longest proper prefix of the pattern that also ends there, built in O(k) for a pattern of length k. Its indexing convention differs from the array used here, which reference 7 defines exactly.
cp-algorithms — Prefix function. It defines π[i] as the length of the longest proper prefix of s[0 … i] that is also a suffix of it, proves the O(n) construction from the fact that π grows by at most one per step, and follows the chain π[i], π[π[i] − 1], … down to zero: the recurrence all three solutions implement.
C++ — Euler316.cpp. The linked immutable revision contains the functions described above and is the implementation record for this article.
GCC manual — 128-bit integers. The manual documents __int128 and unsigned __int128 as extensions available on targets with an integer mode wide enough for 128 bits. The hand-written decimal conversion is a property of the implementation in reference 8, not of the manual.
Java — Long documents Long.MAX_VALUE as 2⁶³ − 1, the limit the bound of Section 11 is compared with, and Python — numeric types states that integers have unlimited precision.

Problem 316 source code

C++

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

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

std::array<u128, 20> build_pow10() {
    std::array<u128, 20> pow10{};
    pow10[0] = 1;
    for (int i = 1; i < static_cast<int>(pow10.size()); ++i) {
        pow10[i] = pow10[i - 1] * static_cast<u128>(10);
    }
    return pow10;
}

u128 g_value(const u64 n, const std::array<u128, 20>& pow10) {
    const std::string s = std::to_string(n);
    const int d = static_cast<int>(s.size());

    std::vector<int> pi(static_cast<std::size_t>(d), 0);
    for (int i = 1; i < d; ++i) {
        int j = pi[static_cast<std::size_t>(i - 1)];
        while (j > 0 && s[static_cast<std::size_t>(i)] != s[static_cast<std::size_t>(j)]) {
            j = pi[static_cast<std::size_t>(j - 1)];
        }
        if (s[static_cast<std::size_t>(i)] == s[static_cast<std::size_t>(j)]) {
            ++j;
        }
        pi[static_cast<std::size_t>(i)] = j;
    }

    u128 expected_end = 0;
    for (int len = d; len > 0; len = pi[static_cast<std::size_t>(len - 1)]) {
        expected_end += pow10[static_cast<std::size_t>(len)];
    }

    return expected_end - static_cast<u128>(d) + 1;
}

u128 solve_sum(const u64 numerator, const u64 max_n, const std::array<u128, 20>& pow10) {
    u128 total = 0;
    for (u64 n = 2; n <= max_n; ++n) {
        total += g_value(numerator / n, pow10);
    }
    return total;
}

bool run_checkpoints() {
    const auto pow10 = build_pow10();

    if (g_value(535ULL, pow10) != static_cast<u128>(1008)) {
        std::cerr << "Checkpoint failed: g(535)\n";
        return false;
    }

    const u128 sample_sum = solve_sum(1000000ULL, 999ULL, pow10);
    if (sample_sum != static_cast<u128>(27280188ULL)) {
        std::cerr << "Checkpoint failed: sample sum\n";
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    bool skip_checkpoints = false;
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            skip_checkpoints = true;
        } else {
            std::cerr << "Unknown argument: " << arg << '\n';
            return 1;
        }
    }

    if (!skip_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const auto pow10 = build_pow10();
    const u128 answer = solve_sum(10000000000000000ULL, 999999ULL, pow10);
    std::cout << to_string_u128(answer) << '\n';
    return 0;
}

Python

def g_value(n):
    s = str(n)
    d = len(s)
    pi = [0] * d
    for i in range(1, d):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
        
    expected_end = 0
    k = d
    while k > 0:
        expected_end += 10 ** k
        k = pi[k - 1]
        
    return expected_end - d + 1

def solve(numerator=10000000000000000, max_n=999999):
    total = 0
    for n in range(2, max_n + 1):
        total += g_value(numerator // n)
    return str(total)

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

Java

public class Euler316 {
    static long[] buildPow10() {
        long[] pow10 = new long[20];
        pow10[0] = 1;
        for (int i = 1; i < 20; ++i) {
            pow10[i] = pow10[i - 1] * 10L;
        }
        return pow10;
    }

    static long gValue(long n, long[] pow10) {
        String s = String.valueOf(n);
        int d = s.length();

        int[] pi = new int[d];
        for (int i = 1; i < d; ++i) {
            int j = pi[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = pi[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }

        long expectedEnd = 0;
        for (int len = d; len > 0; len = pi[len - 1]) {
            expectedEnd += pow10[len];
        }

        return expectedEnd - d + 1;
    }

    public static String solve() {
        long[] pow10 = buildPow10();
        long numerator = 10000000000000000L;
        long maxN = 999999L;

        long total = 0;
        for (long n = 2; n <= maxN; ++n) {
            total += gValue(numerator / n, pow10);
        }

        return String.valueOf(total);
    }

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