Reciprocal cycles

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.

Idea

A problem of primary math calculation: 'calculate decimal for fraction'

Record remainder of each division, and check if there is a repeatted pattern.

In [1]:
def get_remainders(d):
    remainders = [1]
    new_remiander = (remainders[-1] * 10) % d
    while new_remiander:
        remainders.append(new_remiander)
        if new_remiander in remainders[:-1]:
            break
        new_remiander = (remainders[-1] * 10) % d
    return remainders
In [2]:
get_remainders(2)
Out[2]:
[1]
In [3]:
get_remainders(3)
Out[3]:
[1, 1]
In [4]:
get_remainders(4)
Out[4]:
[1, 2]
In [5]:
get_remainders(6)
Out[5]:
[1, 4, 4]
In [6]:
get_remainders(7)
Out[6]:
[1, 3, 2, 6, 4, 5, 1]
In [7]:
def get_recurring_interval(remainders):
    r = remainders[-1]
    for i, rr in enumerate(reversed(remainders[:-1]), 1):
        if rr == r:
            return i
    return 0
In [8]:
get_recurring_interval(get_remainders(3))
Out[8]:
1
In [9]:
get_recurring_interval(get_remainders(4))
Out[9]:
0
In [10]:
get_recurring_interval(get_remainders(7))
Out[10]:
6
In [11]:
def solve(bound):
    return max(range(1, bound), key=lambda n: get_recurring_interval(get_remainders(n)))
In [12]:
solve(10)
Out[12]:
7
In [13]:
solve(1000)
Out[13]:
983