Project Euler — Problem 5 Solution

Problem

2520 is the small­est num­ber that can be divid­ed by each of the num­bers from 1 to 10 with­out any remain­der.

What is the small­est pos­i­tive num­ber that is even­ly divis­i­ble by all of the num­bers from 1 to 20?

Solution

let isEvenlyDivided(n, m) = n % m = 0
let isEvenlyDividedByAll(n, numbers) = numbers |> Seq.forall (fun x -> isEvenlyDivided(n, x))

let findSmallestCommonMultiple(numbers) =
    let max = Array.max(numbers)
    Seq.unfold (fun x -> Some(x, x + 1)) max
    |> Seq.filter (fun x -> isEvenlyDividedByAll(x, numbers))
    |> Seq.head

let commonMultiplier = findSmallestCommonMultiple [|1..20|]

Again, I build two func­tions to han­dle the log­ic of check­ing whether a num­ber can be even­ly divid­ed by all the num­bers in a sup­plied list. I have used anoth­er new func­tion Seq.forall (I can’t find the MSDN doc for this func­tion, but see List.forall instead) which tests each ele­ment in the list with the sup­plied pred­i­cate.

In order to find the small­est com­mon mul­ti­ple for all the num­bers from 1 to 20, I first gen­er­at­ed a sequence of all the nat­ur­al num­bers equal or greater than 20:

Seq.unfold (fun x –> Some(x, x + 1)) max // max is resolved to 20 by Array.max(numbers)

Then for each num­ber I applied the pred­i­cate isEv­en­ly­Di­vid­ed­ByAll to see if it can be even­ly divid­ed by each of the num­bers from 1 to 20, and final­ly, Seq.head returns the first ele­ment that match­es the pred­i­cate and that’s our answer!

One last thing though, when you run this code you’ll see that it takes a rather long time to return. So to improve on the per­for­mance of this log­ic, you can add a small and yet effec­tive step to only test num­bers which are mul­ti­ples of the largest num­ber (20 in our case) in the list:

let findSmallestCommonMultiple(numbers) =
    let max = Array.max(numbers)
    Seq.unfold (fun x -> Some(x, x + 1)) 1
    |> Seq.map (fun x -> x * max)
    |> Seq.filter (fun x -> isEvenlyDividedByAll(x, numbers))
    |> Seq.head

Run the new find­S­mall­est­Com­mon­Mul­ti­ple func­tion again and it now returns much much quick­er :-)