#Skip to menu

Longest Collatz sequence

First read the problem description.

We’ll use memoization to cache results for odd numbers. We don’t cache even numbers since there’s a separate loop that divides even numbers by 2 until we have an odd number. By storing only half of the numbers we also halve the amount of memory needed.

cache = {}
def total_stopping_time(n):
    t = n
    c = 0
    while True:
        while t % 2 == 0:
            t //= 2
            c += 1
        if t == 1:
            break
        if cache.get(t):
            c += cache.get(t)
            break
        t = (3*t + 1)
        c += 1
        
    if n % 2 != 0:
        cache[n] = c
    return c

max_n = 0
max_length = 0
for n in range(1, 1_000_000):
    length = total_stopping_time(n)
    if length > max_length:
        max_length = length
        max_n = n
max_n
837799

See what people say about this article.


Source code of the solution(s):