# Efficient solution to Project Euler 14 (Longest Collatz sequence)

This is an iterative review. I asked for reviews on a Collatz sequence generator here. I tried to address all of the suggestions that were made.

I've added a new function get_longest_collatz(n), which can be used to solve Project Euler problem 14 (the question states: which number under a million has the longest Collatz sequence?)

The solution makes use of memoization.

def collatz(n):
"""
Generator for collatz sequence beginning with n.
n must be 0, 1, 2 ...

>>> list(collatz(1))
[1]

>>> list(collatz(10))
[10, 5, 16, 8, 4, 2, 1]
"""
yield n
while n > 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
yield n

def get_longest_collatz(n):
"""
Returns the number less than n with the longest collatz sequence.

>>> get_longest_collatz(1000)
871
"""
lengths = {} # Keys are natural numbers, values are lengths of collatz sequence
for i in range(n):
for count, x in enumerate(collatz(i)):
if x in lengths:
# The sequence length for x has already been found
lengths[i] = count + lengths[x] # Add onto previously found sequence length
break
else:
lengths[i] = len(list(collatz(i))) # Store full length of collatz sequence
return max(lengths, key=lengths.get) # Key of memo with largest value


At first, I wanted to say that you compute the sequence twice, which is one too many. But looking more carefully, the else part of the loop will only be reached the first time. Every other iteration will at least try to grab lengths[1]. So you could define lengths = {1: 1} and get rid of that special case.

Second, you only compute the length for the first element of the sequence at a time. For collatz(3) you know that the length is one more than collatz(10) which is one more than collatz(5) and so on. Why wait to compute these sequences to store their lengths when you could have done it when computing collatz(3). For that, I propose you replace the body of the for loop with collatz_length(collatz(i), lengths) defined as:

def collatz_length(iterator, cache):
n = next(iterator)
try:
return cache[n]
except KeyError:
cache[n] = value = 1 + collatz_length(iterator, cache)
return value


Optionally, lengths could be a collections.Counter instead of a plain old dictionary. So you could use lengths.most_common(1) to get the longest sequence. But since Counter will return 0 for missing elements instead of raising KeyError, you will need:

def collatz_length(iterator, cache):
n = next(iterator)
if n not in cache:
cache[n] = 1 + collatz_length(iterator, cache)
return cache[n]

n must be 0, 1, 2 ...


Should be:

n must be 1, 2, 3 ...


Or say that:

n must be a positive integer.


Your code doesn't give an infinite loop, but it doesn't make sense really that you return [0] for your function. If you "allowed" 0 the collatz funciton would return an infinite list of 0s. (Why?)

• Just looked up the collatz conjecture, you're right, they specify it has to be a positive integer Oct 21, 2016 at 19:26