The Collatz Conjecture is a simple mathematical problem that still has no formal proof. So it’s an open problem.

This is how it works:

Choose any positive integer x.
While x > 0, do:
    if x is even, divide it by 2 (x = x/2)
    if x is odd, multiply it by 3 and add 1 (x = 3x + 1)

The Collatz Conjecture states that no matter what value of x you start with, the sequence will always reach x = 1.

Example:

If x = 10, you get the following sequence: [10, 5, 16, 8, 4, 2, 1].

If x = 77, you get the following collatz sequence: [77, 232, 116, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1].

In other words, it doesn’t matter the initial value you pick for x, you always end up going back to x = 1.

A ruby implementation would look like this:

def collatz n
  seq = [n]
  until n == 1
    n = (n.even?) ? (n / 2) : (3 * n + 1)
    seq << n
  end
  seq
end

A Haskell implementation could look like this:

chain :: (Integral a) => a -> [a]
chain 0 = error "Invalid!"
chain 1 = [1]
chain x
  | even x = x:chain (x `div` 2)
  | odd x = x:chain (x*3 + 1)