## Project Euler 5: Multiplicity

The fifth problem from Project Euler asks for “the smallest number that is evenly divisible by all of the numbers from 1 to 20”. The key, for me, was to paraphrase that as “the least common multiple of 1 to 20”.

The least common multiple (*lcm*) of two natural numbers is their product divided by their greatest common divisor (*gcd*, a well-known lab rat). So, the stock definitions of *lcm* and *gcd*, along with one quick fold, are all we need.

def divisibleByAll(lo: Int, hi: Int) = {
def gcd(a: Int, b: Int) = gcd1(a max b, a min b)
def gcd1(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
def lcm(a: Int, b: Int) = a * (b / gcd(a, b))
(lo to hi).foldLeft(1)(lcm(_, _))
}

There is one subtlety in this code; `gcd`

is only there to insure that the (natural) arguments to `gcd1`

are correctly ordered (larger first). That is only needed once; if `a >= b`

, then `a % b`

*cannot* be larger than `b`

, so the recursion in `gcd1`

is guaranteed to maintain the larger-first argument ordering.

Finally, this design encounters integer overflow at 1..24, changing the inner functions to work with `Long`

gets us up to 1..42 before long overflow kicks in.

It should be obvious that the answers for 1..21 and 1..22 are the same as for 1..20, but I had to do a double-take while scanning for the limits. Duh.

### Like this:

Like Loading...

*Related*

Trackbacks are closed, but you can .