Detailed mathematical approach

Problem Summary

Let \(\mathcal A\) be the set of positive integers whose decimal expansion never contains a block \(ddd\) of three equal consecutive digits. The required value is the convergent Kempner-like series

$S=\sum_{n\in\mathcal A}\frac{1}{n}.$

The local C++, Python, and Java programs all implement the same method and print \(S \approx 253.6135092068\). The real task is therefore not brute force, but how to sum the infinite tail of admissible numbers in a controlled way.

Mathematical Approach

1. Why the Series Converges

The forbidden pattern can be counted with the same state machine used by the code. Let \(a_k\) be the number of length-\(k\) digit strings with no three equal consecutive digits, allowing leading zeroes for counting purposes. Split them into strings ending with run length \(1\) and run length \(2\), say \(u_k\) and \(v_k\). Appending a different digit gives \(u_{k+1}=9(u_k+v_k)\), while appending the same digit is possible only from run length \(1\), so \(v_{k+1}=u_k\). Hence

$a_{k+1}=9a_k+9a_{k-1}.$

The dominant root of \(x^2-9x-9=0\) is

$\rho=\frac{9+\sqrt{117}}{2}\lt 10.$

Therefore the number of admissible \(k\)-digit denominators is \(O(\rho^k)\), so the total contribution of all \(k\)-digit terms is \(O((\rho/10)^k)\). Since \(\rho/10\lt 1\), the series converges exponentially fast by digit length.

2. The 20-State Automaton

To decide whether another digit may be appended, only two pieces of information matter: the last digit \(d\in\{0,\dots,9\}\) and whether the current run length is \(1\) or \(2\). This gives \(20\) states \(s=(d,r)\).

From \((d,1)\), every next digit is legal. If we append \(d\), the next state is \((d,2)\); if we append \(x\ne d\), the next state is \((x,1)\). From \((d,2)\), the digit \(d\) is forbidden, while each \(x\ne d\) leads to \((x,1)\). This is exactly what build_automaton constructs in all three language versions.

3. Tail Moments and the Linear System

Fix a state \(s\), and let \(W_s\) be the set of all finite valid tails that may follow \(s\), including the empty tail \(\epsilon\). For \(m\ge 0\), define

$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}},$

with the convention that the empty tail contributes \(1\) when \(m=0\) and \(0\) otherwise. If a non-empty tail is written as \(w=xu\), where the first appended digit is \(x\) and the remaining tail \(u\) starts from the next state \(t\), then

$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$

Applying the binomial theorem gives the recurrence

$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)},$

where \(T(s)\) is the set of labeled outgoing transitions from state \(s\). The term \(j=m\) involves the unknown moments of the same order, so we move it to the left:

$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$

For each fixed \(m\), this is a \(20\times20\) linear system. Because the right-hand side uses only moments of order \(\lt m\), the code solves the systems in increasing order of \(m\), precomputing binomial coefficients and digit powers and then using Gaussian elimination with partial pivoting.

4. From Moments to the Harmonic Sum

Choose a valid decimal prefix \(p\) and let \(s\) be the state determined by its last digit and current run length. Every admissible integer that begins with \(p\) can be written as

$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s.$

Its entire contribution is therefore

$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}.$

Since \(0\le \operatorname{val}(w) \lt 10^{|w|}\), we have \(\operatorname{val}(w)/(p10^{|w|}) \lt 1/p\). For the actual computation the code uses prefixes with at least two or three digits, so this ratio is comfortably below \(1\). Hence

$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$

Summing over all valid tails gives the key identity

$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$

This is the formula used by estimate_series_value. Small admissible integers are summed directly, and the rest are grouped by prefix; each prefix contributes an alternating series whose coefficients are the precomputed moments.

5. Code-Level Checkpoints

The C++ implementation verifies two facts before printing the final value. First, among \(1\le n\le 1200\), exactly \(20\) numbers contain three equal consecutive digits. Second, splitting the same infinite sum with prefix_digits = 2 and with prefix_digits = 3 gives answers that differ by less than \(10^{-15}\). These checks confirm both the automaton and the prefix-tail decomposition.

How the Code Works

has_three_equal_consecutive tests the forbidden pattern directly. build_automaton creates the 20 labeled states. solve_moments computes \(H_s^{(m)}\) for \(0\le m\le 16\) using high-precision arithmetic: cpp_dec_float_100 in C++, Decimal in Python, and BigDecimal in Java. Finally, estimate_series_value adds exact reciprocals below \(10^{D-1}\), scans the admissible \(D\)-digit prefixes, determines their terminal state, and accumulates the truncated alternating expansion for \(R(p,s)\). The three solutions differ only in syntax, not in mathematics.

Complexity Analysis

Let \(M\) be the largest moment index, with \(M=16\) in the repository. For each \(m\), one dense \(20\times20\) linear system is solved, so the dominant algebraic work is \(O(M\cdot 20^3)\). The prefix phase scans \(9\cdot 10^{D-1}\) candidate \(D\)-digit prefixes, which is tiny for \(D=3\). Memory usage is \(O(M\cdot 20)\) for the table of moments, plus \(O(20^2)\) temporary storage for elimination.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=368
2. Kempner series: https://en.wikipedia.org/wiki/Kempner_series
3. Finite-state machine: https://en.wikipedia.org/wiki/Finite-state_machine
4. Binomial theorem: https://en.wikipedia.org/wiki/Binomial_theorem
5. Gaussian elimination: https://en.wikipedia.org/wiki/Gaussian_elimination