Detailed mathematical approach

Problem Summary

Define \(L(n)\) as the length of the repeating part in the decimal expansion of \(1/n\). The task is to compute

$S(N)=\sum_{n=3}^{N} L(n)$

for a very large bound \(N\). A direct simulation of long division for every denominator is much too slow, so the implementations reorganize the sum using multiplicative order and a grouping argument over powers of \(2\) and \(5\).

Mathematical Approach

Step 1: Remove the terminating part

Every denominator can be written uniquely as

$n=2^a5^b m,\qquad \gcd(m,10)=1.$

The powers of \(2\) and \(5\) only create the finite prefix of the decimal expansion. The recurring part depends entirely on the remaining factor \(m\).

If \(m=1\), then \(1/n\) is a terminating decimal and therefore \(L(n)=0\). If \(m>1\), the repetend length is the multiplicative order of \(10\) modulo \(m\):

$L(n)=\operatorname{ord}_m(10),$

where \(\operatorname{ord}_m(10)\) is the smallest positive integer \(k\) such that

$10^k\equiv 1 \pmod m.$

This is the standard number-theoretic description of repeating decimals.

Step 2: Group denominators by the same odd core

Fix an odd integer \(m\) with \(5 \nmid m\). Every denominator of the form

$n=m\,s,\qquad s=2^a5^b,$

has exactly the same recurring-cycle length, namely \(\operatorname{ord}_m(10)\), because multiplying by \(2\) and \(5\) changes only the terminating prefix.

For a given quotient \(Q\), define the count of \(2\)-\(5\)-smooth multipliers by

$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$

Then the denominators whose odd core is \(m\) contribute

$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$

Summing over all admissible cores gives the central identity used by the fast solver:

$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$

The missing case \(m=1\) can be ignored because its cycle length is \(0\).

Step 3: Decompose the order over prime powers

Write the odd core as

$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$

Since the prime-power factors are pairwise coprime, the Chinese remainder theorem implies that the order modulo the product is the least common multiple of the orders modulo each prime power:

$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$

So the problem reduces to computing \(\operatorname{ord}_{p^e}(10)\) efficiently for each prime-power factor.

Step 4: Order modulo a prime

For an odd prime \(p\neq 5\), Fermat's little theorem gives

$10^{p-1}\equiv 1 \pmod p,$

so \(\operatorname{ord}_p(10)\) must divide \(p-1\). The implementations therefore start from \(p-1\), factor that number, and try to divide away each prime factor as long as the congruence test still succeeds. In other words, if \(d\) is the current candidate order and \(q\mid d\), then one checks whether

$10^{d/q}\equiv 1 \pmod p.$

If the test is true, the order was not minimal and the candidate can be reduced to \(d/q\). Repeating this process yields the exact order modulo \(p\).

Step 5: Lift from \(p\) to \(p^e\)

Once the order modulo \(p\) is known, the order modulo higher powers of \(p\) is obtained incrementally. If

$t=\operatorname{ord}_{p^{k-1}}(10),$

then the next order satisfies

$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$

We distinguish the two cases by testing whether

$10^t\equiv 1 \pmod{p^k}.$

If that congruence already holds, the order stays equal to \(t\); otherwise it grows by a factor \(p\). This is exactly the lifting rule used by the implementations when building prime-power orders.

Only primes with \(p\le \sqrt{N}\) need tables for exponents \(e\ge 2\), because if \(p>\sqrt{N}\) then \(p^2>N\) and such a prime can appear only to the first power in any core \(m\le N\).

Worked Example: \(N=10\)

The admissible odd cores are \(m=3,7,9\). For \(m=3\), the smooth multipliers satisfying \(3s\le 10\) are \(s=1,2\), so the multiplicity is \(2\). Since \(\operatorname{ord}_3(10)=1\), this contributes \(2\).

For \(m=7\), only \(s=1\) is possible, and \(\operatorname{ord}_7(10)=6\), so the contribution is \(6\).

For \(m=9\), again only \(s=1\) is possible, and \(10\equiv 1 \pmod 9\), so \(\operatorname{ord}_9(10)=1\), contributing \(1\).

Therefore

$S(10)=2+6+1=9,$

which matches the direct sum of cycle lengths for \(1/3,1/4,\dots,1/10\).

How the Code Works

The C++, Python, and Java implementations follow the same arithmetic pipeline. They first build an odd-only smallest-prime-factor sieve, which is enough because only odd cores coprime to \(10\) matter. They then enumerate all odd primes other than \(5\), compute \(\operatorname{ord}_p(10)\) by stripping factors from \(p-1\), and precompute prime-power orders wherever higher powers can still occur below the bound.

In parallel, the implementation generates the sorted list of all numbers of the form \(2^a5^b\le N\). For each odd core \(m\) with \(5\nmid m\), it reconstructs \(\operatorname{ord}_m(10)\) from the prime-power factors using repeated \(\mathrm{lcm}\), counts the valid smooth multipliers with a binary search in that list, and adds the product to the running total. The Python version serves as a thin launcher around the compiled fast solver, while the Java version reproduces the same number-theoretic computation directly.

Complexity Analysis

The preprocessing sieve is near-linear, usually summarized as \(O(N\log\log N)\) time with \(O(N)\) stored state, although the odd-only representation roughly halves the memory footprint. The list of \(2^a5^b\) values has size only \(O((\log N)^2)\), so it is negligible compared with the sieve.

After preprocessing, each admissible core is factorized quickly from the sieve and combined from only a few prime-power orders. The total work is dominated by the sieve construction, the prime-order precomputation, and the single pass over odd cores not divisible by \(5\). This is dramatically faster than simulating decimal periods denominator by denominator, and it is practical for \(N=10^8\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=417
2. Repeating decimal: Wikipedia — Repeating decimal
3. Multiplicative order: Wikipedia — Multiplicative order
4. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
5. Fermat's little theorem: Wikipedia — Fermat's little theorem