Problem

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.

Answer

837799

---

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)

---

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

---

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]

---

Clojure

#!/usr/bin/env clojure
(defn collatz [start]
  (defn next-collatz [n]
    (if (even? n)
      (/ n 2)
      (+ (* 3 n) 1)))
  (def memo-collatz
    (memoize next-collatz))
  (defn not-one? [n]
    (not (= n 1)))
  (concat (take-while not-one? (iterate next-collatz start)) [1]))

(defn collatz-seqs [limit]
  (map collatz (range 1 limit)))

(println (apply max-key count (collatz-seqs 100000)))

---

C

#include <stdio.h>

long next_collatz(long n) {
    if (n % 2 == 0) {
        return n / 2;
    } else {
        return 3 * n + 1;
    }
}

long lencollatz(long start) {
    if (start < 1) {
        return 0;
    } else if (start == 1) {
        return 1;
    } 
    long n = start;
    long length = 1;
    while (n != 1) {
        n = next_collatz(n);
        length++;
    }
    return length;
}

long main() {
    long max_l = 0;
    long max_i = 0;
    long i;
    for (i=1; i < 1000000; i++) {
        long l = lencollatz(i);
        if (l > max_l) {
            max_l = l;
            max_i = i;
        }
    }
    printf("%ld\n", max_i);
    return 0;
}

---

Java

import java.math.BigInteger;


public final class p014 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p014().run());
	}
	
	
	/* 
	 * We compute the Collatz chain length for every integer in the range according to the iteration rule.
	 * Also, we cache the Collatz value for small integer arguments to speed up the computation.
	 */
	private static final int LIMIT = Library.pow(10, 6);
	
	public String run() {
		int maxArg = -1;
		int maxChain = 0;
		for (int i = 1; i < LIMIT; i++) {
			int chainLen = collatzChainLength(BigInteger.valueOf(i));
			if (chainLen > maxChain) {
				maxArg = i;
				maxChain = chainLen;
			}
		}
		return Integer.toString(maxArg);
	}
	
	
	// Can be set to any non-negative number, but there are diminishing returns as you go larger
	private static final BigInteger CACHE_SIZE = BigInteger.valueOf(LIMIT);
	
	// Memoization
	private int[] collatzChainLength = new int[CACHE_SIZE.intValue()];
	
	// Returns the Collatz chain length of the given integer with automatic caching.
	private int collatzChainLength(BigInteger n) {
		if (n.signum() < 0)
			throw new IllegalArgumentException();
		
		if (n.compareTo(CACHE_SIZE) >= 0)  // Caching not available
			return collatzChainLengthDirect(n);
		
		int index = n.intValue();  // Index in the cache
		if (collatzChainLength[index] == 0)
			collatzChainLength[index] = collatzChainLengthDirect(n);
		return collatzChainLength[index];
	}
	
	
	// Returns the Collatz chain length of the given integer, with the
	// first step uncached but the remaining steps using automatic caching.
	private int collatzChainLengthDirect(BigInteger n) {
		if (n.equals(BigInteger.ONE))  // Base case
			return 1;
		else if (!n.testBit(0))  // If n is even
			return collatzChainLength(n.shiftRight(1)) + 1;
		else  // Else n is odd
			return collatzChainLength(n.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE)) + 1;
	}
	
}

---

Mathematica

Collatz[0] := 0
Collatz[1] := 1
Collatz[n_] := Block[{res = Collatz[If[EvenQ[n], n / 2, n * 3 + 1]] + 1},
  If[n < 10^5, Collatz[n] = res, res]]  (* Selective memoization *)

$RecursionLimit = 1000;
maxArg = -1;
maxVal = -1;
For[i = 0, i <= 10^6, i++,
  If[Collatz[i] > maxVal,
    maxVal = Collatz[i];
    maxArg = i]]
maxArg