Here’s problem twenty six:

*Question: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.*

I had to find a clever solution to this problem, mainly because I didn’t know how to brute force it (maybe I should’ve read this). I learn something new everyday, and by solving this problem I discovered a neat application for Fermat’s Little Theorem.

Take a look:

def lengthDecimal(n): # finds length of recurring cycle of 1/n
while n % 2 == 0:
n //= 2
while n % 5 == 0:
n //= 5
for x in range(1, n):
if (10**x - 1) % n == 0:
return x
return 0
result = [0, 0] # number, length
for n in range(2, 1000):
if lengthDecimal(n) > result[1]:
result = [n, lengthDecimal(n)]
print(result)

Any multiple of 2 or 5 in the denominator will yield the same number of decimal places, so that is the first step of the *lengthDecimal()* function. If a prime number is in the denominator, we can use a trick based on Fermat’s Little Theorem to calculate the length of the recurring decimal cycle. The application is as follows: 1/n has a cycle of x digits if (10x – 1) % n = 0. Given n, it’s a simple matter of guess and check to find x.

This function is used to test numbers up to 1000.

*Answer: 983*

### Like this:

Like Loading...

*Related*

Tags: cycle detection, decimal, length

## Leave a Reply