Project Euler Problem 368
The harmonic series 1 + frac 1 2 + frac 1 3 + frac 1 4 + cdots is well known to be divergent.
Solution
Answer: 253.6135092068
Let
$$S=\sum_{\substack{n\ge1\ n\text{ has no }aaa\text{ block}}}\frac1n,$$
where “$aaa$” means three consecutive equal digits.
The key observation is that this is a Kempner-type convergent harmonic subseries.
A direct brute-force summation is impossible: to get $10^{-10}$ precision one would need to go far beyond $10^{2000}$.
Instead, we build a digit-DP / automaton recurrence.
Define:
- $S_1(n,d)$: valid $n$-digit numbers ending in digit $d$, but whose last two digits are different.
- $S_2(n,d)$: valid $n$-digit numbers ending in exactly two consecutive $d$'s.
Now define
$$f_1(n,d,j)=\sum_{x\in S_1(n,d)}\frac1{x^j}, \qquad f_2(n,d,j)=\sum_{x\in S_2(n,d)}\frac1{x^j}.$$
The desired sum is
$$\sum_{n\ge1}\sum_{d=0}^9 \left(f_1(n,d,1)+f_2(n,d,1)\right).$$
Using the decomposition
$$x\mapsto 10x+d,$$
and the binomial expansion
$$(1+t)^{-j} = \sum_{k\ge0}\binom{j+k-1}{k}(-t)^k,$$
we obtain recurrences such as
$$f_2(n,d,j) = 10^{-j} \sum_{k\ge0} \binom{j+k-1}{k} \left(-\frac d{10}\right)^k f_1(n-1,d,j+k),$$
with a similar formula for $f_1$.
Truncating the power-series expansion at sufficiently high order (around 30–40 terms is enough for double precision), iterating over digit lengths, and summing the contributions yields
$$S \approx 253.6135092068.$$
Rounded to 10 digits after the decimal point:
Answer: 253.6135092068