# Rendition of Project Euler 26 - reciprocal cycles

This is my solution for problem 26 from Project Euler:

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

from timeit import default_timer as timer
import math
from decimal import *

start = timer()

def longestPeriod(n): # define function
longest = [0, 0] # length, num

def isPrime(k): # checks if a # is prime
for x in range(2, int(math.ceil(math.sqrt(k)))):
if k % x == 0:
return False
return True

def primeFact(k): # returns prime factorization of # in list
if k <= 1: return []
prime = next((x for x in range(2,
int(math.ceil(math.sqrt(k))+1)) if k%x == 0), k)

return [prime] + primeFact(k//prime)

def periodIfPrime(k):
period = 1
while (10**period - 1) % k != 0:
period += 1

return period # returns period of 1/d if d is prime

def lcm(numbers): # finds lcm of list of #s
def __gcd(a, b):
a = int(a)
b = int(b)
while b:
a,b = b,a%b
return a
def __lcm(a, b):
return ( a * b ) / __gcd(a, b)

return reduce(__lcm, numbers)

for x in range(3, n): # check all up to d for 1/d

if all(p == 2 or p == 5 for p in primeFact(x)) == True: # doesn't repeat
pass

elif isPrime(x) is True: # run prime function
if longest[0] < periodIfPrime(x):
longest = [periodIfPrime(x), x]

elif len(primeFact(x)) == 2 and primeFact(x)[0] == primeFact(x)[1]:
if x == 3 or x == 487 or x == 56598313: # exceptions
period = int(math.sqrt(x))
else: # square of prime
period = periodIfPrime(primeFact(x)[0]) * x
if period > longest:
longest = [period, x]

else:
fact = primeFact(x)
periods = []
for k in fact:
if k != 2 and k != 5:
if fact.count(k) == 1:
periods.append(periodIfPrime(k))
else:
periods.append((periodIfPrime(k)) * k**(fact.count(k) - 1))

if lcm(periods) > longest[0]:
longest = [lcm(periods), x]

return longest

elapsed_time = timer() - start
elapsed_time /= 100 # milliseconds

print "Found %d in %r ms." % (longestPeriod(1000)[1], elapsed_time)


Can it be written in a better way?

• You shouldn't update the code you've written as it makes the answers irrelevant. Please rollback your change and if you really want to, add the new code precising explicitely that you've taken answers into account. – SylvainD Apr 11 '14 at 12:09

## 3 Answers

• Don't compute the same thing more than once. You call primeFact(x) up to 5 times for each x. Keep the result in a variable instead.
• You check if x is prime after you have already computed its prime factorization. Now think for a minute: how does the prime factorization of a prime turn out?
• Your program would greatly benefit from a precomputed list of primes. Look up sieve of Eratosthenes.
• The answer according to this program is 3, which cannot be right, as eg. 7 has a longer period already.
• Bug: if period > longest compares an int to a list, which is not an error in Python 2.x, but does not do what you want.
• To allow testing of individual functions, it is better to define them at module level.
• A quick test of isPrime shows it returns True for 4,9,25 etc. That's because eg. ceil(2.0) == 2.0
• When you say the answer according to the program is 3, do you mean that it returns 3? I get 983 (the correct answer) when I run it. – Joshua Apr 11 '14 at 10:00
• @jshuaf Yes. I had another look, and I see return longest must be at the wrong indentation level. Oh I see you just fixed it! – Janne Karila Apr 11 '14 at 10:08
• @jshuaf But now I see you have incorporated my suggestions in the code, which invalidates my answer. Please don't do that; you can post both versions in the question if you like. – Janne Karila Apr 11 '14 at 10:11

You don't have to define your own gcd function: it already exists in the fractions module of the standard library. And actually, it works with any integer type. Therefore, you can rewrite lcm as:

def lcm(numbers):
"""finds lcm of list of #s"""
from fractions import gcd
return reduce(lambda a,b: (a*b)/gcd(a, b), numbers)


Also, you shouldn't write == True in a conditional, a code like

if eggs == True:
# do something


should be replaced by:

if eggs:
# do something


I realized that youare actually using Python 2 (for some reason, I thought that you were using Python 3). Therefore, You can probably improve the function isPrime. You are currently using range in the function. range creates and returns a list. You should use xrange instead: xrange is a generator; it will generate and yield a new int at each iteration. Since you occasionally return early from your loop, you don"t always need to compute the whole list of integers, and xrange should be a best fit for this job.

def isPrime(k):
for x in xrange(2, int(math.ceil(math.sqrt(k)))):
if k % x == 0:
return False
return True


You're not measuring the elapsed time in a meaningful way. The bulk of the work is in calling the longestPeriod() function, not in defining it. You've stopped the timer before you even call the function.

To convert seconds to milliseconds, multiply by 1000, don't divide by 100.

start = timer()
answer = longestPeriod(1000)[1]          # Don't you want [0] instead?
elapsed_time = (timer() - start) * 1000  # seconds → milliseconds

print "Found %d in %r ms." % (answer, elapsed_time)

• Thanks for your answer; I used [0] because the problem asked for the number, not the length of the period. – Joshua Apr 11 '14 at 9:53
• You're right, I read the code carelessly. I suggest using a namedtuple instead of a two-element list to avoid such confusion. – 200_success Apr 11 '14 at 10:11