# Project Euler Problem 14 Solution

## 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.780s
user   0m0.716s
sys    0m0.060s

## 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 0m3.849s user 0m3.812s sys 0m0.036s ## 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.218s
user   0m2.216s
sys    0m0.000s

## Rust

fn main() {
let mut collatz: Vec<usize> = vec![0; 1000000];
collatz[1] = 1;
let max = (2..collatz.len())
.max_by_key(|&i| {
let mut j: usize = i;
let mut len = 0;
loop {
if j < collatz.len() && collatz[j] != 0 {
break;
}
len += 1;
if j % 2 == 0 {
j /= 2;
} else {
j = 3 * j + 1;
}
}
len += collatz[j];
collatz[i] = len;
len
})
.unwrap();
println!("{}", max);
}
$rustc -C target-cpu=native -C opt-level=3 -o collatz collatz.rs$ time ./collatz
real   0m0.028s
user   0m0.024s
sys    0m0.004s