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

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:

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 *lcd*s pair-wise in the following fashion:

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

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

## Leave a Comment