Project Euler Problem 14 Solution

Question

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

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

$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.350s
user   0m0.342s
sys    0m0.008s

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.686s user 0m3.639s sys 0m0.047s 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.133s
user   0m2.133s
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.018s
user   0m0.018s
sys    0m0.000s