Project Euler #14 solution takes quite a long time Can anybody give me suggestions for making it faster? (Project Euler #14)

import time
start = time.clock()

def collatzChain(n):
    count = 1
    while n != 1:
        if n % 2 != 0:
            count += 1
            n = (n * 3) + 1

        if n % 2 == 0:
            count += 1
            n = n / 2

    return count

chainLengths = []
startNum = 999999
while startNum &gt; 1:
    chainLength = collatzChain(startNum)
    chainLengths.append(chainLength)
    startNum -= 1

print(999999 - chainLengths.index(max(chainLengths)))
elapsed = time.clock() - start
print("This program took " + str(elapsed) + " seconds.")
Consider the chains starting at 13 and 26. When you reach 26, you go over its whole chain. Later, you reach 13, and go over its whole chain too - but 13's chain is the same as 26's, only without the first number (26).

If you implemented collatzChain using recursion, just adding the decorator @functools.lru_cache would create a cache for your function, and thus prevent Python from repeating the same job twice.