Project Euler Problem 14

Solution

Answer: 837799

We seek the starting number $n < 1{,}000{,}000$ that generates the longest Collatz chain.

For each integer:

if $n$ is even: $n \to n/2$
if $n$ is odd: $n \to 3n+1$

The key optimization is memoization: once the chain length of a number is known, reuse it instead of recomputing the entire sequence repeatedly.

For example:

$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$

has $10$ terms.

A clean Python solution:

def collatz_length(n, cache):
    if n in cache:
        return cache[n]

    if n % 2 == 0:
        length = 1 + collatz_length(n // 2, cache)
    else:
        length = 1 + collatz_length(3 * n + 1, cache)

    cache[n] = length
    return length

cache = {1: 1}

best_n = 1
best_len = 1

for n in range(1, 1_000_000):
    length = collatz_length(n, cache)

    if length > best_len:
        best_len = length
        best_n = n

print(best_n)

Tracing known results:

$13$ gives length $10$
As the search proceeds, larger records appear
The maximal chain under one million occurs at:

$$837799$$

with a chain length of $525$.

Answer: 837799