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:
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:
- Divisors \(d\) of the form \(2^n \times 5^m\) produce a finite expansion, e.g. \(\ ^1 / _2 = 0.5\) (non-recurring)
- Prime divisors \(d\) that are co-prime with \(2\) and \(5\) produce an infinite expansion
- 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.
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