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.
I tried to solve it in Python:
For every d, assume you are solving for
1 / dby hand.
In case the 1 is completely divisible by d, it means the cycle length is 0.
If a value you have already divided appears again, it means you've found the cycle.
The cycle would have length of the number of times you've repeated the first step minus the first time the cycled value appears as we have to remove non-cycling values.
Here's my code following the above steps in Python:
LIMIT = 1000 # The maximum length maxi = 0 # The 'd' that has maximum length maxi_d = 1 for d in range(1, LIMIT): quotient =  # Stores the decimal quotient cur_value = 1 # Variable used to perform division as if by hand len_recur = 0 # Recurring length # Performing division as if by hand. while cur_value not in quotient: if not cur_value: # If the value is not recurring: break # break as the rucurring length must be 0 len_recur += 1 quotient.append(cur_value) cur_value = (cur_value % d) * 10 if not cur_value: continue # Remove number of values that do not recur len_recur -= quotient.index(cur_value) + 1 if len_recur > maxi: maxi = len_recur maxi_d = d print(maxi_d)
I'd like to make this code as fast as possible. This currently takes ~3.5 seconds for
LIMIT = 2000 and grows exponentially larger.
PS: I know
len_recur can be replaced by
len(quotient), but I want the code to be as fast as possible.