Problem 14:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

A solution:
In order to not compute the entire sequence every time, the variable history is used to keep track of sequence lengths as we go. history[i] will be the length of the sequence that starts with i.

def next(n): # computes next term in the sequence
    if n % 2 == 0:
        return n/2
    else:
        return 3*n+1

history = [0,1]
for i in range(2,1000000):
    num_terms = 0
    num = i
    done = False
    while num > 1 and not done:
        num = next(num)
        if num < len(history): # number has been hit previously,
            # so the length of the rest of the path is known.
            num_terms += history[num]
            done = True
        num_terms += 1
    history.append(num_terms)

print history.index(max(history))