Problem 14: Which starting number, under one million, produces the longest “Collatz” chain?

I coded  this solution in just a couple of minutes, but ran into trouble with F#’s unchecked Int32 operations.  We can do checked operations using Checked.(+) for + for example.  After changing to Int64, this runs in about 4 and a half seconds.

let problem14a = 
    let collatz n =
        let rec collatz n count =
            let count = count + 1L
            if n = 1L then count
            elif n % 2L = 0L then collatz (n/2L) count
            else collatz ((3L*n)+1L) count
        collatz n 0L
        
    {1L..999999L} |> Seq.map (fun i -> (i, collatz i)) |> Seq.maxBy snd |> fst

Since subsequences are frequently shared between inputs of n, this is a good opportunity to apply a memoization technique.

let problem14b = 
    let mem = new System.Collections.Generic.Dictionary<int64,int64>()
    let collatz m =
        let rec collatz n count =
            let count = count + 1L
            if mem.ContainsKey n then
                let count = mem.[n] + count - 1L
                mem.Add(m, count)
                count
            elif n = 1L then 
                mem.Add(m, count)
                count
            elif n % 2L = 0L then collatz (n/2L) count
            else collatz ((3L*n)+1L) count
        collatz m 0L
        
    {1L..999999L} |> Seq.map (fun i -> (i, collatz i)) |> Seq.maxBy snd |> fst

That ran in about 1 and a half seconds.