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.