Collatz Sequence in Python

Question

I'm trying to use Python to solve the Project Euler problem regarding the Collatz sequence. With some research online, I have come up with the code below. However, it still takes a long time to find the maximum length of the Collatz sequence of the numbers from one to a million after the following improvements.

• Using a list in order to keep track of numbers that are in the Collatz sequence of preceding numbers so that they won't be tested

• Not testing any of the numbers in the lower half of interval and not testing any numbers that would make this expression true:

  ((f%9==2)or(f%9==4)or(f%9==5)or(f%9==8)or(f%8==5))
  

Any criticism is appreciated.

"""
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=[]
def collatz(n):
    if n%2==0:
        return int(n/2)
    else:
        return int(3*n+1)
def collatz_length(n):
    b=n
    c=0
    while collatz(b)!=1:
        a.append(b)
        b=collatz(b)
        c=c+1
        if collatz(b)==1:
            break
    return c
d=0
e=0
for g in range(500000,1000000,1):
    f=g+2
    if (f in a) == False and ((f%9==2)or(f%9==4)or(f%9==5)or(f%9==8)or(f%8==5)):
        print(len(a))
        print(f)
        if collatz_length(f)>e:
            d=f
            e=collatz_length(f)
print(d)
print(e)

Answer 1

Variable Names

You use a, b, c, d, e, f, and g to refer to important things. I started trying to keep track of what each one meant and then gave up. I have no idea. Give things meaningful names. Apparently d is the number with the longest sequence, whose length is e - which is certainly not obvious from the names!

Chaining

To find the length of the collatz chain for some number, n, involves also finding the length of the collatz chain for every other number in that chain. However, you don't store that information anywhere, so it's lost.

Furthermore, you calculate it TWICE:

if collatz_length(f)>e:
    d=f
    e=collatz_length(f)

So you're recalculating every chain every time twice. That's an enormous amount of extra work. Lastly, you're assuming that the largest starts halfway through. That isn't necessarily true, given that collatz(n) > n for odd n...

Saving State

You save some state in a, but that ends up with you having to do a linear search through a list... which will fail most of the time, but it'll take a long time to fail. At the very least, you could store things in a set(), which is O(1), but even then, you're storing the wrong state. You're storing numbers you've seen before, but what you should store is the chain lengths of the numbers you've seen before. That is...

Memoize

This is a problem that lends itself extremely naturally to memoization, so we can just do that:

@memoize
def collatz_length(n):
    if n == 1:
        return 1
    else:
        return 1 + collatz_length(collatz(n))

And then just stick that into max:

longest_num = max(range(1, 1000001), key=collatz_length)
print(longest_num)
print(collatz_length(longest_num))