Longest Collatz Sequence¶

The Collatz conjecture is a famous unsolved problem, and a classic example of a seemingly simple question that has proven very difficult, if not impossible, to answer.

It's easy enough to define a [recursive](https://en.wikipedia.org/wiki/Recursion_(computer_science%29) function to calculate the chain length for a starting number $n$. $$ f(n) = \begin{cases} 1 & n = 1 \\ 1+f(n/2) & n \equiv 0 \pmod{2} \\ 1+f(3n+1) & n \neq 1\ \text{and}\ n \equiv 1 \pmod{2} \end{cases} $$ However, we want its implementation to be efficient. We can optimize greatly if we cache the outputs we compute (the computer science term for this is memoization). For instance, if we store the fact that $f(4) = 3$ after we've computed it, when we later compute $f(8) = 1 + f(4)$, the program can use the stored value of 3 rather than recomputing $f(4)$. For large inputs, this will save us (or really the computer, I guess) from redoing work.

Python has a nice decorator called cache that will automagically memoize our function.

In [1]:
from functools import cache

@cache
def collatz_length(n):
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + collatz_length(n // 2)
    else:
        return 1 + collatz_length(3 * n + 1)
In [2]:
max(range(1, 1000000), key=collatz_length)
Out[2]:
837799

Relevant sequences¶

  • Collatz chain lengths: A008908

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.