Post a Comment On: Scattered Thoughts

Time for another Project Euler post. Problem fourteen asks you to:

Find the longest sequence using a starting number under one million.

Given a start number xn the next entry in the sequence is given by:

[Image]
You can find a nice discussion of this sequence in Wikipedia as the Collatz Problem. In F# this code will generate the sequence from a given starting value:


let rec sequence n =     seq {        yield n;        match n with        | 1ul -> ()        | _ when n%2ul = 0ul -> yield! sequence (n/2ul)        | _ when n%2ul = 1ul -> yield! sequence (3ul*n + 1ul)    }

Then I can create a tuple containing the sequence starting value and the sequence length as follows:


let length n =    (sequence n |> Seq.length, n)

So when I want to find the longest sequence I can write:


seq { 1ul..999999ul} |> Seq.map length |> Seq.max |> printfn "longest = %A"

Interestingly, the Seq.max function will just use the first entry in the tuple for its comparison. This means I don't have to clutter my code with special handling to extract the length information from the sequence of tuples. Obviously I got lucky when I put together the tuple and had the length come before the seed value.