Project Euler Problem 5 in F#

Yet another episode in my attempts to solve Project Euler problems.

Enter problem number 5:

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

I’ll first show you my solution and then explain the bits:

#light

// greatest common divisor (Euclid Algorithm)
let rec gcd (a:int64, b:int64) =
    match b with
       | x when x = 0L -> a
       | _ -> gcd (b, a % b)

// least common divisor
let rec lcm (a:int64, b:int64) =
    (a * b) / gcd (a,b)

// least common divisor for a list of numbers
let rec lcmlist (list: int64 list) =
    match list with
        | [] -> 1L
        | [a] ->  a
        | [a;b] ->  lcm(a,b)
        | h::t  ->  lcm(h, lcmlist t)

// utility to generate a list of all integers
// up to a certain number
let generateListTo top =
    let l = [for i in 1L .. int64 top ->  i]
    l

let resolveProblem5 =
    generateListTo 20 |>  lcmlist

The first thing to realize when reading this problem is that what is really being asked is
the least common multiple (lcm from now on) of a list of numbers (in particular, the numbers from 1 to 20 included).

There’s a straightforward way to compute the lcm, by using the greatest common divisor (gcd), as follows:

Least Common Multiple

As for the gcd itself, it can be easily implemented using the Euclid Algorithm.

The last piece of the puzzle comes when you realize how calculating the lcd of a set of numbers can be reduced to calculating lcds pair-wise in the following fashion:

Lcm on a list of numbers

For example, given the numbers 3, 4, 14, and 18, their lcm would be computed in the following way:

Least Common Multiple=

As you can see, the algorithm lends itself beautifully to recursion and such is the solution that I have provided.

See all Project Euler problems solutions.

kick it on DotNetKicks.com

Shout it

This entry was posted in .NET, F# and tagged , . Bookmark the permalink.
  • Pingback: DotNetShoutout

  • Javaman59

    Thanks for the gcd & lcm algorithm. Nice work, and explanation – this is a very good solution. It is many times faster than the brute force approach I tried.

    Just a minor F# point. “[for i in 1L .. int64 top -> i]” is the same as “[1L..top]“. In fact, the last two functions can be compressed to just “[1L..20L] |> lcmlist”

  • stefanoricciardi

    Yes, you have a good point there. I am trying to get familiar with F# own idioms more and more, even though my C# background creeps in from time to time :)

  • Y4b3rtys

    can you help explain the program flow

  • Anonymous

    Reading from the listing bottom-up should reveal the flow. If you have difficulties in any part let me know.