Detailed mathematical approach

Problem Summary

The problem asks for the denominator \(d \lt 1000\) for which the decimal expansion of \(1/d\) has the longest recurring cycle. Some reciprocals terminate, such as \(1/8 = 0.125\); others have a repeating tail, such as \(1/7 = 0.\overline{142857}\).

The key point is that decimal expansion is controlled entirely by long-division remainders. Once the same remainder appears twice, the subsequent digits must repeat as well. Therefore the real mathematical object is not the digit string itself, but the finite remainder process generated by dividing \(1\) by \(d\).

Mathematical Approach

Fix a denominator \(d \ge 2\). When we perform long division for \(1/d\), each step is determined by the current remainder.

Remainders Are the True State Space

Let \(r_0 = 1 \bmod d\). At step \(k\), write

$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d.$

Here \(q_k\) is the next decimal digit of \(1/d\), and \(r_{k+1}\) is the new remainder. Reducing the same identity modulo \(d\) gives the recurrence

$r_{k+1} \equiv 10r_k \pmod{d}.$

So the decimal digits are produced by a deterministic map on the finite set of remainders \(\{0,1,\dots,d-1\}\). The current remainder completely determines both the next digit and the next remainder.

Why a Repeated Remainder Forces a Repeating Decimal

If some step reaches remainder \(0\), then all later remainders stay \(0\), so the decimal terminates. Otherwise every remainder lies in \(\{1,2,\dots,d-1\}\), which has only \(d-1\) possibilities. By the pigeonhole principle, some remainder must repeat after at most \(d\) steps.

Suppose \(r_i = r_j\) with \(i \lt j\). Because the transition rule is deterministic, the entire future from step \(i\) onward is identical to the future from step \(j\) onward. Therefore the digits from position \(i\) onward repeat with period \(j-i\). This is exactly why storing the first position of each remainder is enough to recover the cycle length.

In particular, for every denominator \(d\), the recurring cycle length is at most \(d-1\).

Separating the Non-Repeating Prefix from the Cycle

Write

$d = 2^a 5^b m,\qquad \gcd(m,10)=1.$

The factors \(2\) and \(5\) are responsible only for a finite prefix, because powers of \(10\) contain exactly those prime factors. The genuinely recurring part comes from the reduced denominator \(m\).

If \(m=1\), then \(1/d\) terminates. If \(m \gt 1\), the recurring cycle length is the smallest positive integer \(t\) such that

$10^t \equiv 1 \pmod{m},$

which is the multiplicative order \(\operatorname{ord}_m(10)\). This gives a clean number-theoretic interpretation of the remainder process, even though the implementations do not compute the order by factoring \(d\).

Worked Example: \(1/7\)

For \(d=7\), the remainder chain is

$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1.$

The corresponding digits are obtained from the equations

$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$

$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$

Thus

$\frac{1}{7} = 0.\overline{142857},$

and the first repeated remainder is \(1\), reappearing after 6 steps, so the cycle length is 6.

Worked Example: \(1/12\)

For \(d=12\), we have

$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4.$

So the digits start as \(0,8,3,3,3,\dots\), which means

$\frac{1}{12} = 0.08\overline{3}.$

The remainder \(4\) repeats immediately, so the recurring cycle has length 1, while the initial \(08\) is a non-repeating prefix caused by the factor \(4 = 2^2\) inside the denominator.

Why the Direct Search Is Enough

The code checks every \(d\) from \(2\) to \(999\), computes its cycle length, and remembers the best one. Mathematically one can prove extra facts, such as the order dividing \(\varphi(m)\), but for this input size none of that is necessary. The direct remainder simulation already mirrors the long-division process exactly and is fast enough.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They parse an optional limit, run a pair of small checkpoints, and then scan all denominators below the limit.

Computing the Cycle Length for One Denominator

For a fixed \(d\), the implementation allocates an array or list of length \(d\) and fills it with \(-1\). Entry \(r\) stores the first digit position at which remainder \(r\) appeared. The process starts from remainder \(1 \bmod d\) and a position counter equal to 0.

While the current remainder is nonzero and has not been seen before, the current position is stored, the remainder is updated to \((10r) \bmod d\), and the position counter is incremented. If the loop ends because the remainder became 0, the decimal terminates and the cycle length is 0. If the loop ends because a remainder was seen earlier, the cycle length is

$\text{current position} - \text{first position of that remainder}.$

Scanning All Candidates

After computing the cycle length for one denominator, the implementation compares it with the best length found so far. If the new cycle is strictly longer, the current denominator becomes the new champion. Because the comparison is strict, ties leave the earlier denominator in place.

Built-In Sanity Checks

Before solving the full problem, the implementations verify two facts: the recurring cycle length of \(1/7\) is 6, and among denominators below 10 the best answer is 7. These checks confirm that both the remainder simulation and the outer scan behave as intended.

Complexity Analysis

For a fixed denominator \(d\), the loop can visit each remainder at most once before either hitting 0 or repeating, so the work is \(O(d)\). Summing over all \(d = 2,3,\dots,L-1\) gives

$\sum_{d=2}^{L-1} O(d) = O(L^2).$

For \(L=1000\), this is only on the order of half a million remainder updates, which is tiny. The peak extra memory is \(O(L)\), because the largest remainder-tracking array has size at most \(L-1\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=26
2. Repeating decimals: Wikipedia - Repeating decimal
3. Multiplicative order: Wikipedia - Multiplicative order
4. Long division: Wikipedia - Long division