Project Euler Problem 14 Solution

Question

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

n{n2if n is even3n+1if n is odd\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:

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

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.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

Questions? Comments? Send me an email: [email protected]