Detailed mathematical approach

Problem Summary

For each integer \(k\) from \(1\) to \(n\), let \(d_n\left(\frac{1}{k}\right)\) be the \(n\)-th digit after the decimal point in the decimal expansion of \(\frac{1}{k}\). The required quantity is

$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right).$

A direct simulation of long division would advance through \(n\) decimal places for every denominator, which is far too expensive when \(n=10^7\). The implementations avoid that by jumping straight to the needed digit through modular arithmetic.

Mathematical Approach

The entire problem rests on one observation: the \(n\)-th decimal digit of a reciprocal can be recovered from the remainder of \(10^{n-1}\) modulo the denominator.

Step 1: Write the \(n\)-th digit as a floor difference

If

$\frac{1}{k}=0.a_1a_2a_3\dots,$

then shifting the decimal point by \(n\) places gives

$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n.$

So the last digit of that integer is exactly the digit we want. Therefore

$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor.$

This is the standard way to isolate one decimal digit after scaling by powers of \(10\).

Step 2: Collapse the formula to one remainder

Write the Euclidean division of \(10^{n-1}\) by \(k\) as

$10^{n-1}=qk+r,\qquad 0\le r<k.$

Then

$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$

and

$\frac{10^n}{k}=10q+\frac{10r}{k}.$

Taking floors yields

$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor.$

Substituting into the previous identity gives the compact formula

$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor,$

where

$r=10^{n-1}\bmod k.$

This is exactly the quantity used by the implementation. It also handles terminating decimals automatically: once the remainder is \(0\), every later digit is \(0\).

Step 3: Compute the remainder with binary exponentiation

For each denominator \(k\), we need only the residue

$r \equiv 10^{n-1}\pmod{k}.$

Computing \(10^{n-1}\) itself would be absurdly large, but repeated squaring evaluates the residue in \(O(\log n)\) modular multiplications. Every intermediate value is reduced modulo \(k\), so the numbers never grow beyond the modulus.

Once \(r\) is known, the digit is recovered immediately by the integer formula \(\left\lfloor 10r/k \right\rfloor\).

Step 4: Sum over all denominators

Applying the digit formula to every \(k\) from \(1\) to \(n\) gives

$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor.$

The problem is therefore not about building decimal expansions; it is about evaluating one modular power for each denominator and adding the resulting digits.

Step 5: Worked Example for \(n=7\)

The small checkpoint \(n=7\) illustrates the method clearly. We need the seventh digit after the decimal point of \(1/k\) for \(1\le k\le 7\).

For \(k=3\),

$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$

For \(k=6\),

$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$

For \(k=7\),

$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$

The complete digit list is

$0,0,3,0,0,6,1,$

so

$S(7)=0+0+3+0+0+6+1=10.$

This matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They iterate through every denominator \(k\) from \(1\) to \(n\), compute the residue \(10^{n-1}\bmod k\) by repeated squaring, convert that residue into the required decimal digit via

$\left\lfloor \frac{10r}{k} \right\rfloor,$

and add the digit to a running total.

No decimal string is ever built, and no long-division table is stored. The implementation keeps only a fixed set of integers for the current modulus, current base, remaining exponent, current residue, and the cumulative sum.

Complexity Analysis

For one denominator \(k\), binary exponentiation for exponent \(n-1\) needs \(O(\log n)\) modular multiplications. Repeating that for every \(k=1,2,\dots,n\) gives total time

$O(n\log n).$

The auxiliary space is \(O(1)\), since only a constant number of integer variables is maintained in addition to the final sum.

Footnotes and References

1. Problem page: Project Euler 820
2. Repeating decimals: Wikipedia — Repeating decimal
3. Modular arithmetic: Wikipedia — Modular arithmetic
4. Modular exponentiation: Wikipedia — Modular exponentiation
5. Euclidean division: Wikipedia — Euclidean division