Project Euler Problem 417

Solution

Answer: 446572970925740

Let

$$L(n)$$

denote the recurring cycle length of $1/n$.

For any $n$, write

$$n = 2^a 5^b m$$

where $\gcd(m,10)=1$. The terminating part comes entirely from powers of $2$ and $5$, so the recurring cycle length is the multiplicative order of $10$ modulo $m$:

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

(with $L(n)=0$ when $m=1$).

The core number-theoretic fact is:

$$\operatorname{ord}_m(10)\mid \lambda(m)$$

where $\lambda$ is the Carmichael function. Thus, for each $m$, one computes $\lambda(m)$, factors it, and repeatedly removes prime divisors $p$ whenever

$$10^{k/p}\equiv 1 \pmod m$$

to obtain the exact multiplicative order.

To make this feasible for $N=10^8$, an efficient sieve-based approach is required:

Sieve smallest prime factors up to $10^8$.
Compute $\lambda(n)$ multiplicatively.
For each $m$ coprime to $10$, derive $\operatorname{ord}_m(10)$ from $\lambda(m)$ using factor reduction.
Propagate values to all $n=2^a5^b m\le 10^8$, since adding powers of $2$ and $5$ does not change the recurring cycle length.
Sum all $L(n)$.

A correctness check is that the same implementation reproduces the given benchmark:

$$\sum_{3\le n\le 10^6} L(n)=55{,}535{,}191{,}115$$

exactly, matching the problem statement.

After running the full computation for $N=100{,}000{,}000$, the total is:

Answer: 446572970925740