Project Euler in F# - Problem 5

Here is a quick write-up on how to solve Project Euler’s Problem 5 in F#.

 

Problem 5 is defined as follows:

 

2520 is the smallest number that can be divided by each of the numbers 1 to 10 without any remainder. What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

 

First, let’s double-check that 2520 actually is evenly divisible by numbers [1 .. 10]. This is simple to check in F# using the F# Interactive Console (fsi.exe). Just type the following:

> List.map (fun i -> 2520.0 / i) [1.0 .. 10.0];;

val it : float list

= [2520.0; 1260.0; 840.0; 630.0; 504.0; 420.0; 360.0; 315.0; 280.0; 252.0]

 

Looks good. Now let’s write some F# code.

 

let problem4 =

    let allIntegers = 1 |> Seq.unfold (fun i -> Some (i, i + 1))

    let numNotDivBy numList x = List.map (fun i -> if x % i = 0 then true else false) numList

                                |> List.filter (fun ele -> if ele = false then true else false)

                                |> List.length

    let result = allIntegers |> Seq.first (fun i -> if numNotDivBy [1 .. 20] i = 0 then Some(i) else None)

    match result with

    | Some(x) -> x

    | None -> failwith "Couldn't find number divisible by [1..20] in the range of all integers..."

Rather than going over the code line by line, I’d like to just draw your attention to two things:

 

First, the line “1 |> Seq.unfold (fun i -> Some(i, i + 1))” is simple way of creating an infinite sequence of all integers. For problems like this, an infinite sequence complements Seq.first nicely.

 

Second, I’d like to take a moment to explain just how awesome the pass forward operator (“|>”) is. For a function f which takes two parameters x and y, the following statements are equivalent:

 

f x y
y |> f x

 

So all the pass forward operator does is 'pass something forward' as the last parameter to a function. Though nothing more than delicious piece of syntactic sugar, it makes code far more readable. Consider the somewhat complex set of list transformations in the code. If we were to write the equivalent code without the pass forward operator the code would look something like this:

 

let numNotDivBy numList x = List.length(List.filter (fun ele -> if ele = false then true else false) (List.map (fun i -> if x % i = 0 then true else false) numList))

 

As you can see, the |> operator was a great idea.

 

Anyways, that’s it for now, though I might have some big news on the horizon. For the time being feel free to drop a note and point out any glaring inefficiencies in my F# ;) Also, thanks again to the folks at Project Euler for sharing their wealth of problems.