## Project Euler in F# – Problem 5

The exercise we are going to face today is ranked as one of the easiest of **Project Euler**'s, so I don't think you will have any problem in solving it.

However, it allows me to discuss a little bit on **algorithm optimization** and how to refine a working solution to obtain a better one.

The text of the exercise says:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Some programming languages (for instance **Haskell**) provide a native function for evaluating the **least common multiple** (LCM) of two numbers, i.e. the smallest positive integer that is multiple of both numbers.

In F# we don't have this function, hence we have to write our own code to perform this calculation, and we need it to be able to find the **LCM of a set of numbers** and not only two.

Let's see the implementation of my algorithm:

#light open System let nums = 1 |> Seq.unfold (fun i -> Some (i, i + 1)) let divisibleByList list n = Seq.for_all (fun x -> n % x = 0) list let answer = nums |> Seq.first (fun i -> if divisibleByList [1 .. 20] i then Some (i) else None)

My solution will simply take the integers starting from 1 and check if they are evenly divisible by all numbers from 1 to 20.

We don't know when to stop, so at line 4 we have to create an **infinite list** of integers.

To do so, we use the *unfold* function, which allows us to create a **lazy list** by passing another function to be repeatedly evaluated to provide the elements of the list.

In our case we start from 1 and for each iteration we add one to the previous value, without an upper limit.

At line 6 we have the definition of the *divisibleByList* function, which takes a list of numbers and an integer *n* and checks if *n* is evenly divisible by all the elements of the given list.

This is done by using *Seq.for_all*, which tests if all the elements of the sequence satisfy the given predicate.

We have now everything we need to find our solution.

Let's just feed the *divisibleByList* function with the elements of the infinite list of integers and stop when we find the first that satisfy our conditions, thanks to *Seq.first*.

The solution is complete, but it is not very fast, since it takes about **8 minutes** to run in my computer.

We can improve this time by using some very simple math.

First of all, we are sure that the number we are looking for will be a multiple of 2, so we can **skip all odd numbers**, by changing line 4 with:

let nums = 2 |> Seq.unfold (fun i -> Some (i, i + 2))

With this simple change the execution time drops to **4 minutes**, as the amount of integers to check is is actually halved.

I want to go a little further and instead of checking all even numbers we can just test the **multiples of 20**.

To do so, we change again line 4 with this new one:

let nums = 20 |> Seq.unfold (fun i -> Some (i, i + 20))

Now I can be proud of myself as the execution time is reduced to **25 seconds**, twenty times less than the original solution!

Obviously this is not the only solution and there are smarter approaches, maybe we can see them in a future post.

Beetle B.February 7th, 2008 - 17:35

If you know a bit more math, this is even easier:

lcm(a1, a2, …) = (a1*a2*a3*…)/gcd(a1,a2,…)

where gcd is the greatest common divisor and can be calculated using Euclid’s algorithm.

Basically, I calculated the lcm of 2 and 3, and then the lcm of the result and 4, the lcm of the result and 5, etc.

0.1 ms in Python (interpreted!) on a P4 2.53 GHz machine.

Oh, and BTW, since you’re using WordPress, you may want to get the plugin that allows people who post comments to subscribe to the comments via email (yes, I know you have an RSS, but I don’t want to crowd my RSS aggregator for simple things like these). Otherwise, it’ll be hard for commenters to maintain a conversation with you.

claudioFebruary 7th, 2008 - 17:53

Hi, thanks for the suggestion.

I plan to write a new post soon presenting your solution and showing the huge difference between a brute-force approach and a “smart” one.

The goal of this series of articles is to introduce people to functional programming, trying to translate the basic algorithms that come to mind into F# code, and hoping that the readers will try to find their own solution before I show mine.

BTW, I also added the comment subscription plugin that you suggested, thanks!

MattFebruary 7th, 2008 - 18:00

Here’s my solution with no programming required

http://methodoverload.blogspot.com/2008/02/project-euler-5-and-number-theory.html

MichaelFebruary 7th, 2008 - 18:01

claudio

if you think about it the binary gcd(a,b)*lm(a,b) = a*b doesn’t hold in the general case. gcd(1,..,20) should obviously be 1 and lcm(1,..,20) is obviously not 1*2*…*20 which means lcm(1,..,20) \not= 1*…*20/gcd(1,..,20)

But lcm is still easy it’s just the max of each exponent of the unique factorization of each of the number you take lcm over.

MichaelkFebruary 8th, 2008 - 02:16

I noticed that the LCM of 1..18 was a factor of the LCM of 1..19, and the LCM of 1..19 was a factor of 1..20.

So, I just combined that with memoization, and got it working in Python (real 0m0.012s).

Paolo BonziniFebruary 8th, 2008 - 10:54

gcd(a,b)*lcm(a,b) = a*b holds always. gcd(a,b,c)*lcm(a,b,c) = a*b*c does not hold, but you can exploit the associativity of lcm like this:

lcm(a,b,c)=lcm(lcm(a,b),c)

and then use the gcd(a,b)*lcm(a,b) = a*b identity to compute lcm.

in Smalltalk:

st> Time millisecondsToRun: [ (2 to: 20) fold: [ :a :b | a lcm: b ] ]

1

st> Time millisecondsToRun: [ (2 to: 1000) fold: [ :a :b | a lcm: b ] ]

14

and that’s a 433-digit number…