Project Euler Problem 026

Statement

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

(1)
\begin{align} \begin{flushleft} 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{align}

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.

Solution

Here the problem is how to determinate when the recurrence has started. After thinking deeply it's pretty obvious, when we find
that the tuple formed by the digit that we have to add to the result and the module that we have to continue dividing has
appeared before then we have a chain.

def find_cycle_length(n):
    tmp = 1
    decimal = []
    digit = tmp / n
    module = tmp % n
    while (digit, module) not in decimal:
        decimal.append((digit, module))
        tmp = module * 10
        digit = tmp // n
        module = tmp % n
    while (digit, module) != decimal[0]:
        decimal.pop(0)
    return len(decimal)
 
if __name__ == '__main__':
    result = 0
    max_len = 0
    for d in range(2,1000):
        length = find_cycle_length(d)
        if length > max_len:
            result = d
            max_len = length
    print("The result is:", result)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License