theburningmonk.com

Prob­lem

The fol­low­ing iter­a­tive sequence is defined for the set of pos­i­tive integers:

n –> n/2 (n is even)

n –> 3n + 1 (n is odd)

Using the rule above and start­ing with 13, we gen­er­ate the fol­low­ing sequence:

13 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1

It can be seen that this sequence (start­ing at 13 and fin­ish­ing at 1) con­tains 10 terms. Although it has not been proved yet (Col­latz Prob­lem), it is thought that all start­ing num­bers fin­ish at 1.

Which start­ing num­ber, under one mil­lion, pro­duces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Solu­tion

let nextNumber n = if n%2L = 0L then n/2L else 3L*n+1L

let findSequenceLength n =
    let mutable count = 1L
    let mutable current = n

    while current > 1L do
        current <- nextNumber current
        count <- count + 1L
    count

let longestSeq = [1L..999999L] |> Seq.maxBy findSequenceLength

Hav­ing played around with sev­eral other approaches, I finally set­tled down on this solu­tion though I had to use muta­ble vari­ables in a while loop which is some­what dis­sat­is­fy­ing but it per­forms quite a bit bet­ter than the more func­tional approach.

As you prob­a­bly know already, in F# every­thing is immutable by default and to make a muta­ble vari­able you have to mark the vari­able with the muta­ble key­word. To assign a value to a muta­ble vari­able you need to use the <- oper­a­tor.

Any­ways, the above code is fairly sim­ple, with the find­Se­quence­Length func­tion doing the bulk of the work and returns the num­ber of ele­ments in a sequence using a while loop. It can be equally be writ­ten using a more func­tional (but slower) approach but build­ing the sequence with Seq.unfold and count­ing the length of the sequence

// the sequence returned by Seq.unfold does not include 1, so for completeness sake, add 1 to the length
let findSequenceLength n = Seq.length(Seq.unfold (fun x -> if x = 1L then None else Some(x, nextNumber x)) n) + 1