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