Collatz Conjecture

In today's xkcd comic, the topic was Collatz Conjecture. This is the first I have ever heard of this so of course I looked it up on Wikipedia. Turns out it was proposed by Lothar Collatz in 1937.

 

 Simply put, given any natural number n. If n is even, we halve it (n / 2), otherwise we multiply by 3 and add 1 to obtain 3n + 1. Rinse, repeat. The conjecture is that for all numbers this process converges to 1.

The Wikipedia article gives several implementations of this algorithm so I opened up my editor and tried out an SML implementation. Without exhaustive testing, it seems to be working so far.

Here is the code:

(*

  Implements Collatz Conjecture.

  Accepts: an integer n.

  Returns: The list of integers produced by following collatz sequence until the sequence converges to 1.

  Pre: n >= 1

*)

fun collatz(1) = [1] |
    collatz(n) =
        let
            val even = n mod 2 = 0
        in
           if even then
              n::collatz(n div 2)
           else
              n::collatz(3*n + 1)
        end;