Project Euler Problem 26

Solution

Answer: 983

For a fraction $1/d$, the length of the recurring cycle in its decimal expansion is determined by the multiplicative order of $10 \pmod d$, after removing factors of $2$ and $5$ (since those only contribute to terminating decimals).

For prime $d$ (other than $2,5$), the recurring cycle length divides $d-1$. To maximize the cycle under $1000$, we search for the $d<1000$ with the largest period.

A clean way is to simulate long division: track remainders seen so far. Once a remainder repeats, the decimal begins cycling, and the cycle length is the distance between occurrences.

Python code

def cycle_length(d):
    seen = {}
    remainder = 1 % d
    position = 0

    while remainder != 0 and remainder not in seen:
        seen[remainder] = position
        remainder = (remainder * 10) % d
        position += 1

    if remainder == 0:
        return 0  # terminating decimal
    return position - seen[remainder]

best_d = 0
max_cycle = 0

for d in range(2, 1000):
    length = cycle_length(d)
    if length > max_cycle:
        max_cycle = length
        best_d = d

print(best_d)

Mental trace / correctness check

Small cases:
$1/3 = 0.(3)$ → cycle length $1$
$1/7 = 0.(142857)$ → cycle length $6$
The algorithm correctly detects repeated remainders and measures cycle length.
Checking values near $1000$, the maximum recurring cycle occurs at $d=983$, which has a cycle length of $982$ (full reptend prime).

Answer: 983