Question

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

$\displaystyle n \rightarrow \begin{cases} \tfrac{n}{2} & \text{if } n \text{ is even} \\ 3n+1 & \text{if } n \text{ is odd} \end{cases}$

Using the rule above and starting with 13, we generate the following sequence:

$\displaystyle 13, 40, 20, 10, 5, 16, 8, 4, 2, 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.

import Data.Word
import Data.Array

memoCollatz :: Array Word Word
memoCollatz = listArray (1, size) $map collatz [1..size] where size = 1000000 collatz :: Word -> Word collatz 1 = 1 collatz n | inRange (bounds memoCollatz) next = 1 + memoCollatz ! next | otherwise = 1 + collatz next where next = case n of 1 -> 1 n | even n -> n div 2 | otherwise -> 3 * n + 1 main = print$ snd $maximum$ map (\n -> (collatz n, n)) [1..1000000]
$ghc -O2 -o longest-chain longest-chain.hs$ time ./longest-chain
real   0m0.998s
user   0m0.932s
sys    0m0.056s

Python

#!/usr/bin/env python
def next_collatz(n):
if n % 2 == 0:
return n / 2
else:
return 3*n + 1

def collatz(start):
if start < 1:
raise ValueError("start must be greater than or equal to 1")
elif start == 1:
return [1]

res = [start]
done = False
while not done:
res += [next_collatz(res[-1])]
if res[-1] == 1: done = True
return res

_collatz_cache = {}
def lencollatz(start):
if start < 1:
raise ValueError("start must be greater than or equal to 1")
elif start == 1:
return 1

n = start
length = 1
done = False
while not done:
n = next_collatz(n)
try:
length += _collatz_cache[n]
done = True
except:
length += 1
if n == 1: done = True
_collatz_cache[start] = length
return length

max_len = 0
max_i = None
for i in range(1, 1000000):
l = lencollatz(i)
if l > max_len:
max_len = l
max_i = i
print(max_i)
$time python3 longest-chain.py real 0m4.700s user 0m4.616s sys 0m0.040s Ruby #!/usr/bin/env ruby max_l = 0 max_i = 0 500001.step(1000000, 2).each do |i| l = 0 j = i while j != 1 do if j.even? j /= 2 else j = 3 * j + 1 end l += 1 end if l > max_l max_l = l max_i = i end end puts max_i $ time ruby longest-chain.rb
real   0m2.171s
user   0m2.148s
sys    0m0.004s