Python Implementation of Problem 26

View source code here on GitHub!

Project Euler Problem 26

Problem:

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

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

Where 0.1(6) means 0.166666..., 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 < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

python.src.p0026.main() → int
 1"""
 2Project Euler Problem 26
 3
 4Problem:
 5
 6A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10
 7are given:
 8
 9.. code-block::
10
11    1/2 = 0.5
12    1/3 = 0.(3)
13    1/4 = 0.25
14    1/5 = 0.2
15    1/6 = 0.1(6)
16    1/7 = 0.(142857)
17    1/8 = 0.125
18    1/9 = 0.(1)
19    1/10 = 0.1
20
21Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring
22cycle. Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
23
24"""
25
26
27def main() -> int:
28    remainders = {d: [1] for d in range(2, 1000)}
29    cycle_lengths = {}
30    while len(remainders):
31        for d in tuple(remainders.keys()):
32            base = 10 * remainders[d][-1]
33            rem = base % d
34            if rem in remainders[d]:
35                cycle_lengths[d] = len(remainders[d]) - remainders[d].index(rem)
36                del remainders[d]
37            else:
38                remainders[d].append(rem)
39    return max(cycle_lengths.items(), key=lambda p: p[1])[0]

Tags: fraction, recurring-decimal, decimal-representation