Detailed mathematical approach

Problem Summary

The number in this problem is the Stoneham number

$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$

We need the 10 consecutive decimal digits that start at position \(n=10^{16}\). If we define

$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$

then \(A(n)\) is exactly that 10-digit block, with leading zeros allowed. The whole task is therefore a digit-extraction problem: compute \(A(10^{16})\) without expanding the decimal expansion out to the \(10^{16}\)-th place.

Mathematical Approach

The implementations turn the infinite Stoneham series into a short exact computation. The key facts are that only finitely many terms can affect the integer part after shifting by \(10^{n+9}\), and that each surviving term can be recovered from one modular exponentiation.

Step 1: Shift the desired block into the integer part

Multiplying by \(10^{n+9}\) moves the digits at positions \(n\) through \(n+9\) into the last 10 digits of an integer:

$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$

Taking the floor removes everything strictly after the \((n+9)\)-th decimal place, and reducing modulo \(10^{10}\) keeps exactly the block we want.

Step 2: Show that the infinite tail cannot change the floor

Let \(L\) be the largest integer satisfying

$3^L\le n+9.$

For every \(k>L\), we have \(3^k\ge n+10\), hence

$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$

Therefore the omitted tail obeys

$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1.$

Since the discarded part is strictly less than \(1\), it cannot affect the floor. So

$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$

For the actual input \(n=10^{16}\), this means only \(L=33\) terms survive.

Step 3: Split each surviving term into quotient and remainder

For each \(1\le k\le L\), write

$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k.$

Then

$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k},$

and summing over all \(k\) gives

$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor.$

The quotient part contributes directly to the answer modulo \(10^{10}\). The remainder part produces a carry, because several fractional pieces can add up to at least \(1\).

Step 4: Compute the carry exactly with a common denominator

All denominators are powers of \(3\), so they merge naturally:

$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$

If we define

$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor,$

then

$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}.$

This is exact: the implementations store every remainder, build the numerator \(\sum r_k 3^{L-k}\), and divide once by \(3^L\).

Step 5: Recover \(q_k \bmod 10^{10}\) and \(r_k\) from one modular power

Computing \(10^{n+9-3^k}\) itself would be impossible, but we do not need the full integer. Define the residue

$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$

Because

$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k$

for some integer \(t_k\), dividing by \(3^k\) yields

$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$

So the only data we actually need are obtained from \(s_k\):

$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$

That is why one modular exponentiation per term is enough.

Worked Example: \(n=100\)

Here \(n+9=109\), so \(L=4\) because \(3^4=81\le 109\lt 243=3^5\). Therefore

$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$

For these four denominators, the residue modulo \(3^k 10^{10}\) is \(10^{10}\), so the quotient contributions are

$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$

$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790.$

The corresponding remainders are

$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$

Hence the carry numerator is

$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76,$

so \(c=\lfloor 76/81\rfloor=0\). Summing the quotient parts gives

$3333333333+1111111111+370370370+123456790=4938271604.$

Thus the 10-digit block beginning at position \(100\) is \(4938271604\), which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations follow the same structure. First they generate the powers \(3,9,27,\dots\) up to \(n+9\), which determines the last relevant index \(L\). Then, for each surviving term, they compute \(10^{n+9-3^k}\bmod(3^k 10^{10})\) with fast modular exponentiation.

From that residue they extract two values: the last 10 digits of the quotient contribution \(\left\lfloor s_k/3^k\right\rfloor\), and the exact remainder \(s_k\bmod 3^k\). The quotient pieces are accumulated modulo \(10^{10}\), while the remainders are stored. After the loop, the implementation forms the single numerator \(\sum r_k 3^{L-k}\), divides by \(3^L\) to obtain the exact carry \(c\), adds that carry to the accumulated quotient sum, and formats the result as a zero-padded 10-digit block.

Complexity Analysis

Let \(L=\lfloor\log_3(n+9)\rfloor\). There are exactly \(L\) relevant terms, and each one requires one modular exponentiation by repeated squaring. That costs \(O(\log n)\) modular multiplications on integers of bit length \(O(\log n)\), so the total running time is \(O(L\log n\,M(\log n))\), where \(M\) is the cost of big-integer multiplication. The memory usage is \(O(L)\), coming from the stored powers of \(3\) and the remainder list.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=731
2. Stoneham number: Wikipedia — Stoneham number
3. Modular exponentiation: Wikipedia — Modular exponentiation
4. Repeating decimal: Wikipedia — Repeating decimal
5. Geometric series: Wikipedia — Geometric series