Problem Twenty Six

17 Nov

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)]

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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: