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.

Comments

• Anonymous
  November 10, 2007
  Here is a quick write-up on how to solve Project Euler’s Problem 5 in F#....( read more )

• Anonymous
  November 12, 2007
  The comment has been removed

• Anonymous
  November 12, 2007
  The comment has been removed

• Anonymous
  November 12, 2007
  I don't know if it should be integrated in F#. If it's easy to implement there is no need for it, except as a standard. I've got Pickerings book, but not opened it yet :-) Attaching the Haskell definitions of foldl1 and lcm: ==================================   gcd x y        Returns the greatest common denominator of two numbers. eg:        gcd(144, 1024) = 16. In Haskell:            gcd :: Integral a => a -> a -> a            gcd 0 0 = error "gcd 0 0 is undefined"            gcd x y = gcd' (abs x) (abs y)                      where gcd' x 0 = x                      gcd' x y = gcd' y (x rem y)    lcm x y        Returns the lowest common multiple of two numbers. eg:        lcm(144, 1024) = 9216. In Haskell:            lcm            :: (Integral a) => a -> a -> a            lcm _ 0         = 0            lcm 0 _         = 0            lcm x y         = abs ((x quot gcd x y) * y)  foldl f z xs        Applies function f to the pairs (z, xs[0]), (f(z, xs[0],        xs[1]), (f(f(z, xs[0], xs[1])), xs[2]) and so on. ie it        folds from the left and returns the last value. Note that        foldl should not be done to infinite lists. eg: the        following returns the sum of 1..6: foldl(sub { $[0] + $[1]        }, 0, [1..6]) = 21. In Haskell:            foldl            :: (a -> b -> a) -> a -> [b] -> a            foldl f z []      = z            foldl f z (x:xs)  = foldl f (f z x) xs    foldl1 f xs        This is a variant of foldl where the first value of xs is        taken as z. Applies function f to the pairs (xs[0], xs[1]),        (f(xs[0], xs[1], xs[2]), (f(f(xs[0], xs[1], xs[2])), xs[3])        and so on. ie it folds from the left and returns the last        value. Note that foldl should not be done to infinite lists.        eg: the following returns the sum of 1..6: foldl1(sub {        $[0] + $[1] }, [1..6]) = 21. In Haskell:            foldl1           :: (a -> a -> a) -> [a] -> a            foldl1 f (x:xs)   = foldl f x xs

• Anonymous
  November 20, 2007
  I'm please to announce that starting Monday I'll be joining the F# team as (currently) the only full-time tester. I'm super-excited about this for many reasons, but the biggest is knowing what an impact I'll have. Without a doubt F# will change the .Net

• Anonymous
  November 20, 2007
  I'm seeing some common redundancy in your code. Where you've written:  if x % i = 0 then true else false you can actually just write:  x % i = 0