Horridly Inefficient Project Euler #14 in Python - Collatz Sequences

Question

I created this solution a while ago, and have been going back over my problems to try to make them all more efficient. I have been stuck on this one, and have tried a few different ideas. So far, my original code has still been the "quickest" at over 2 minutes.

Here is the problem and original solution I came up with:

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.

MAX_LENGTH = 0
NUM = 0
SEQ = []


def nextTerm(num):
    if num != 1:
        if num % 2 == 0:
            return num / 2
        else:
            return (3 * num) + 1
    if num == 1:
        return 1

current = 2
SEQ.append(current)

for num in range(1000001):
    while current >= 1:
        if current > 1:
            current = nextTerm(current)
            SEQ.append(current)
        if current == 1:
            SEQ.append(current)
            break

    if len(SEQ) > MAX_LENGTH:
        MAX_LENGTH = len(SEQ)
        NUM = num

    current = num + 1
    SEQ = []

print("The number {} produced the max sequence length of {}.".format(NUM,
                                                                     MAX_LENGTH
                                                                     ))

# The number 837799 produced the max sequence length of 525.
# Time: 143.42219 seconds

The thing with this is, I know that for many, many numbers, it will end up creating another seq with the last 95% of the sequence being the same, if that makes sense. So I tried creating a way to check if it will end up being the same as another sequence created, and if so, instead of calculating the rest of the sequence, just copy the other one that's the same. This obviously uses a lot more memory as I'm holding a list of lists now instead of a single list, but I thought the time would still be shorter. After waiting 5 minutes while it was running, I just gave up. I still think this might be a good way to think about and approach the problem, so here is the code for that thought process:

def next_term(num):
    if num != 1:
        if num % 2 == 0:
            return num / 2
        else:
            return (3 * num) + 1
    if num == 1:
        return 1

current = 2
MAIN_SEQ = []
seq = []
MAX_LENGTH = 0
NUM = 0

for num in range(1000001):
    seq = [2]
    while current >= 1:
        for lst in MAIN_SEQ:
            if current in lst:
                seq.append(item for item in lst[lst.index(current):])
                break
        if current > 1:
            seq.append(current)
            current = next_term(current)
        if current == 1:
            seq.append(1)
            MAIN_SEQ.append(seq)
            break

    if len(seq) > MAX_LENGTH:
        MAX_LENGTH = len(seq)
        NUM = num

    current = num + 1

print("The number {} produced the max sequence length of {}.".format(NUM,
                                                                     MAX_LENGTH
                                                                     ))

I would still consider myself a beginner in Python, so clear explanations for what I'm doing inefficiently are very welcome.

Answer 1

You should use memoization. It can be as simple as:

def next(n):
    if n % 2 == 0:
        return n // 2
    else:
        return 3 * n + 1

lengths = {}  # n -> length of sequence starting from n
lengths[1] = 1

def length(n):
    if not n in lengths:
        lengths[n] = 1 + length(next(n))
    return lengths[n]

max = 0
for n in range(1,1000000):
    l = length(n)
    if l>max:
        max = l
        print n, max