# 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.

Tags

Comments (6)
1. Here is a quick write-up on how to solve Project Euler’s Problem 5 in F#….( read more )

2. Christer Nilsson says:

Three reactions:

1) Why do you use floats in an integer problem?

2) What is the execution time?

3) In Haskell:

foldl1 lcm [1..20]

3. ChrSmith says:

Hey Christer,

I used floats in the beginning to demonstrate that all the numbers divide evenly; with the integers rounding it isn’t sufficient to prove – at a glance – that the number is evenly divisible by the list.

As for the execution time, I must admit, the way I wrote it up it is pretty much intractable.  It works for lists of divisors [1 .. 10] but for [1 .. 20] things get a tad out of hand. I was hoping nobody would notice so I could use this program as a good example for a future blog post "Writing Efficient F#". Good eye!

As for the ‘lcm’ function in Haskell, that looks pretty cool. Is that something you think we should integrate into F#? Maybe in a Microsoft.FSharp.MathLibrary or something like that?

Anyways, thanks for the feedback.

4. Christer Nilsson says:

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

5. 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

6. Jon Harrop says:

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

Skip to main content