Project Euler #14 - Longest Collatz sequence

Question

I'm attempting some Project Euler problems in an attempt to learn Python. While I can get the correct answer quite easily, my programs are quite slow. Project Euler, if doing it correctly, specifies that each program should run in <1 minute. Some of mine take 5-10 mins.

Here is one example.

x=1;
terms=0;
maxTerms=0;
maxTermsNum=0;
for x in range(1,1000000):
    i=x;
    while (i!=1):
        terms+=1;
        if (i%2==0):
            i/=2
        else:
            i=3*i+1
    if (terms>maxTerms):
        maxTerms=terms;
        maxTermsNum=x;
        print(x);
    terms=0;
print("Biggest one: is %s." %maxTermsNum)

It produces the correct answer, but it takes a long long time. How can I speed this up? This is also in 32-bit Windows.

Answer 1

While many of the Project Euler problems can be solved by brute force, this often isn't the fastest way to do them. Usually there is some kind of algorithmic insight that you can apply that will make your solution faster. This kind of insight is independent of programming language - simply running your code through a hypothetical "go-fast compiler" still won't match the speed of the correct algorithm.

In your case, here's a hint. Many of the sequences you calculate look the same as ones you've previously done. How could you use that information to speed up your algorithm?

Answer 2

If you are under Python 2.x use xrange instead of range for loops.[XRange Doc][Xrange vs range]

A good optimization for big cases of this problem is to start mapping them to avoid recalculating every step. So only if it hits an unknown number it will either multiply or divide and continue. Have a look at the Collatz conjecture and its properties: http://en.wikipedia.org/wiki/Collatz_conjecture

Answer 3

Maybe instead of a modulus use a binary shift and a subtraction to determine if i is even or odd. Also doing a binary shift once and assigning the value to i if it is even would be better than calculating the division twice.

Also use a lookup table for previously traversed solutions to x:

x=1;
terms=0;
maxTerms=0;
maxTermsNum=0;
prevTerms = dict()
for x in range(1,1000000):
    i=int(x)
    while (i!=1):
        if i in prevTerms:
            terms += prevTerms[i]
            break
        terms+=1
        a = i >> 1
        b = i - (a << 1)
        if (b==0):
            i = a
        else:
            i=3*i+1
    if x not in prevTerms:
        prevTerms[x] = terms
    if (terms>maxTerms):
        maxTerms=terms
        maxTermsNum=x
        print(x)
    terms=0;
print("Biggest one: is %s." %maxTermsNum)

This runs in under 10 seconds. Tested in 2.7 on a 2.8 Ghz Windows 7 with 6 cores (not that cores matter here) machine.

Answer 4

There are many ways to speed up a program. I've found it really helps to profile it (see: http://docs.python.org/library/profile.html for more information) so you can see which functions are using up the most time. From there, you can work on optimizing the steps that take up the most time. Another awesome resource is the MIT open courseware course on algorithms, which starts you off with a simple text-file comparison exercise which you modify in steps to increase its speed (see: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/).