Project Euler Problem 5 in F#

1 minute read

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:

// 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:

$$ lcm(a,b) = \frac{|a \cdot b|}{gcd(a,b)} $$

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(a,b,c,d) = lcm(a, lcm(b,c,d) = lcm(a, lcm(b, lcm(c,d))) $$

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

$$\begin{align*} lcm (3,4,14, 18) &= lcm(3, lcm(4,14,18)) \\ &= lcm(3, lcm(4, lcm(14, 18))) \\ &= lcm(3, lcm(4, 126)) \\ &= lcm(3, 252) \\ &= 252 \end{align*}$$

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

Updated:

Leave a Comment