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
    answer = 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
            answer = p
    return answer


expected_answer = 983

solutions.problem26.solve()

Compute the answer to Project Euler’s problem #26