Project Euler Solution 26: Reciprocal cycles

The next entry in the Project Euler series ist Problem 26: Reciprocal cycles, where we have to use long division to find the cycles in the digits.

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.

These cycles can be found using long division like one has used in elementary school to divide numbers. Let us do a long division of 1/7 and see how it works out there:

We can see how we eventually get the same remainder back. This means that the long division will be the same from there on and repeat. We can use this in a program by tracking the remainders that we have had. When we get the next remainder, we check whether that was already encountered, signalling the begin of a cycle. We can then remove all the remainders before the repeated one and have the cycle.

def get_long_division_cycle_length(denominator: int) -> int:
    numerator = 10
    digits = []
    remainders = []
    cur = numerator
    while True:
        digit = cur // denominator
        cur = cur % denominator
        if cur in remainders:
            break
        digits.append(digit)
        remainders.append(cur)
        cur *= 10
        if cur == 0:
            return 0
        while cur < denominator:
            cur *= 10
            digits.append(0)
    while remainders[0] != cur:
        remainders.pop(0)
    return len(remainders)

We then just compute the cycle length for all numbers between 1 and 999 and take the number with the maximum cycle length.

def solution_long_division() -> int:
    cycle_lengths = {denominator: get_long_division_cycle_length(denominator) for denominator in range(1, 1000)}
    return sorted(cycle_lengths.items(), key=lambda item: item[1])[-1][0]

This produces the answers in 135 ms, so that is sufficiently fast.