# Project Euler Problem 26: Reciprocal Cycles¶

The source code for this problem can be found here.

## Problem Statement¶

A unit fraction contains $$1$$ in the numerator. The decimal representation of the unit fractions with denominators $$2$$ to $$10$$ are given:

$\begin{split}\ ^1 / _2 &= 0.5 \\ \ ^1 / _3 &= 0.(3) \\ \ ^1 / _4 &= 0.25 \\ \ ^1 / _5 &= 0.2 \\ \ ^1 / _6 &= 0.1(6) \\ \ ^1 / _7 &= 0.(142857) \\ \ ^1 / _8 &= 0.125 \\ \ ^1 / _9 &= 0.(1) \\ \ ^1 / _{10} &= 0.1\end{split}$

Where $$0.1(6)$$ means $$0.166666\dots$$, and has a $$1$$-digit recurring cycle. It can be seen that $$\ ^1 / _7$$ has a $$6$$-digit recurring cycle.

Find the value of $$d \lt 1000$$ for which $$\ ^1 / _d$$ contains the longest recurring cycle in its decimal fraction part.

## Solution Discussion¶

The decimal expansion of $$\ ^1 / _d$$ falls into one of three possibilities:

1. Divisors $$d$$ of the form $$2^n \times 5^m$$ produce a finite expansion, e.g. $$\ ^1 / _2 = 0.5$$ (non-recurring)
2. Prime divisors $$d$$ that are co-prime with $$2$$ and $$5$$ produce an infinite expansion
3. Multiples of prime divisors $$d$$ that are divisible by $$2$$ or $$5$$ produce infinite expansion with a non-recurring prefix

Note

the cycle produced by numbers of the third class are actually rotations of the cycles produced by their prime divisor.

$\begin{split}\ ^1 / _7 &= 0.(142857) \\ \ ^1 / _{14} &= 0.0(714285)\end{split}$

Observe that the cycles are rotations of one-another and that $$7$$ is a prime divisor of $$14$$.

Therefore, we must only consider prime divisors that are co-prime with $$2$$ and $$5$$.

Interestingly, the cycle length of such a divisor $$p$$ in the decimal representation of $$\ ^1 / _p$$ is the multiplicative order of $$10 \mod p$$. That is, the cycle length is the minimum $$k$$ s.t. $$10^k = 1 \mod p$$.

## Solution Implementation¶

from lib.grouptheory import multiplicative_order
from lib.sequence import Primes

def solve():
""" Compute the answer to Project Euler's problem #26 """
upper_bound = 1000
max_cycle_length = 0
primes = filter(lambda _p: _p not in [2, 5], Primes(upper_bound=upper_bound))
for p in primes:
cycle_length = multiplicative_order(10, p)
if cycle_length > max_cycle_length:
max_cycle_length = cycle_length

solutions.problem26.solve()