Problem 26 : Reciprocal cycles

Problem Statement

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

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

def divide(n,d,p):
    i = 0 
    remainders = set() 
    
    while i < p:
        if n < d:
            n = n * 10 
        
        n = n % d 
        if n in remainders: 
            return(d,i) 
        else:
            remainders.add(n) 
        
        i = i + 1 
    
longest = [0,0]
largest_denominator = 1000
for x in range(2,largest_denominator + 1):
  y = divide(1,x,x) 
  if y[1] > longest[1]:
    longest = y
print(longest[0])

Output

983