Claudio Cherubino's blog Life of a Googler

7Feb/086

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.

Comments (6) Trackbacks (1)
  1. 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.

  2. 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!

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

  4. 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).

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


Leave a comment

(required)