9
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ – SylvainD Apr 11 '14 at 12:09
5
\$\begingroup\$
  • 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
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ – Joshua Apr 11 '14 at 10:00
  • \$\begingroup\$ @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! \$\endgroup\$ – Janne Karila Apr 11 '14 at 10:08
  • \$\begingroup\$ @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. \$\endgroup\$ – Janne Karila Apr 11 '14 at 10:11
9
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your answer; I used [0] because the problem asked for the number, not the length of the period. \$\endgroup\$ – Joshua Apr 11 '14 at 9:53
  • 1
    \$\begingroup\$ You're right, I read the code carelessly. I suggest using a namedtuple instead of a two-element list to avoid such confusion. \$\endgroup\$ – 200_success Apr 11 '14 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.