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.

Haskell

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