A Python mystery

Back after a long time…saw something strange today and think it deserves a post. I was cranking through Problem 47 on Project Euler. As I was optimizing the solution, the optimization actually increased run time – and I’m at a loss to explain it. So here goes:

def problem_47(maxlen = 4):
    found = False
    i = 2*3*5*7 + 1
    while not found:
        # facs = [len([j for j in uniq(prime_fac(i+k))]) for k in xrange(0,maxlen)]
        d = 4
        for t in range(i+3, i-1 , -1):
            k = len(list(uniq(prime_fac(t))))
            if k  < 4:
                i = t + 1
                d -= 1
        if d ==0:
            found = True
            print list(xrange(i, i + maxlen))
        # if i % 1000 == 0:
        #     print i

The run time is about 1m2s.

Now, if I try to optimize it such that I break (line 10) when I find the first number from the end that has less than 4 prime factors, the run time should be lesser (or at least the same). Right?

Turns out Wrong… now the thing takes more than 3m to run. What is going wrong?

If any of you have a clue, drop me a comment.


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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