Longest Collatz Sequence

The following iterative sequence is defined for the set of positive integers:

$n \to n/2$ ($n$ is even)
$n \to 3n + 1$ ($n$ is odd)
Using the rule above and starting with $13$, we generate the following sequence:
$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 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.

The problem described is a famous unsolved problem in number theory known as the Collatz Conjecture or the 3n+1 conjecture.

Unfortunately, there is no known analytical solution for the problem. The most direct solution would be to use brute force: check every starting number up to one million and track which number produces the longest sequence.

Here’s the outline of how you might code this in Python:

“`python
def collatz(n):
“””Implement the logic of the sequence defined by the question”””
# to store the sequence
counter = 1
while n != 1:
if n % 2 == 0:
n = n / 2
else:
n = 3*n + 1
counter += 1
return counter

def longest_chain(limit):
“””Find the starting number under `limit` that produces the longest chain.”””
longest_chain_length = 0
longest_chain_start = 0
for i in range(1, limit):
current_chain_length = collatz(i)
if current_chain_length > longest_chain_length:
longest_chain_length = current_chain_length
longest_chain_start = i
return longest_chain_start, longest_chain_length
“`

Finally, you can call longest_chain(1000000) to perform the computation.

NOTE: This might take quite a long time to run because of the potentially large size of the numbers involved.

For efficiency, we could employ memoization and use a hash map to store previously computed sequence lengths and skip duplicated computations.

“`python
def collatz(n, cache):
counter = 1
sequence = [] # store the sequence to update cache later
while n != 1 and n >= i:
sequence.append(n)
if n%2 == 0:
n = n/2
else:
n = n*3 + 1
counter += 1
else: # cache is found
counter += cache[int(n)] – 1
for idx,num in enumerate(sequence): # update cache
if num <= limit: cache[int(num)] = counter – idx return counter “` The function longest_chain then uses the cache: “`python def longest_chain(limit): longest_chain_length = 0 longest_chain_start = 0 cache = [0]*(limit+1) cache[1] = 1 for i in range(1,limit): current_chain_length = collatz(i, cache) if current_chain_length > longest_chain_length:
longest_chain_length = current_chain_length
longest_chain_start = i
return longest_chain_start, longest_chain_length
“`

So this optimized version will run much faster. But still, finding an analytical solution which doesn’t require exhaustively checking every number under one million would be a significant mathematical breakthrough!

More Answers: