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

(`n` even)

(`n` odd)

Which starting number, under one million, produces the longest chain?

module Problem14 =
let (|Even|Odd|) n =
if n % 2L = 0L then Even
else Odd
let nextCollatz n =
match n with
| 1L -> 1L
| Even -> n/2L
| Odd -> (3L*n) + 1L
let collatz =
let cache = new System.Collections.Generic.Dictionary<_,_>()
let rec cachedCollatz n =
match cache.TryGetValue(n),n with
| (true,v),_ -> v
| (_),1L -> 1
| _ -> let v = 1 + cachedCollatz (nextCollatz n)
cache.Add(n,v)
v
fun n -> cachedCollatz n
let ans = {1L..1000000L} |> Seq.map (fun n -> (n,collatz n)) |> Seq.maxBy snd |> fst

The obvious brute-force solution is actually fast enough, but this problem just screams DP / memoization, and I wanted to see how memoizing something in F# would work, so I played around with memoization for this problem.

Additionally, I (pointlessly) used an active pattern here, because I’d just read about them in Programming F# and wanted to see how they work. I could definitely see how active patterns would be helpful for more complicated problems; it seems weird to me that there’s a limit of seven cases for an active pattern, though.

### Like this:

Like Loading...

*Related*