## 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:

Largest Product in a GridHighly Divisible Triangular Number

Large Sum