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? – PROJECT EULER #5

Pretty straight forward today. Basically, we’re looking for the least common multiple (`lcm`

) of all of the numbers from 1 to 20. So, we’ll start with that. Here’s a way to define `lcm`

, directly from the wikipedia article:

This translates pretty directly:

```
; find the least common multiple of two numbers
; source: http://en.wikipedia.org/wiki/Least_common_multiple
(define (lcm a b)
(/ (abs (* a b)) (gcd a b)))
```

Luckily, `lcm`

is commutative, so `(lcm (lcm a b) c)`

is the same as `(lcm a (lcm b c))`

, etc.

However, as you may have noticed, we need another function: `gcd`

(the greatest common divisor). Euclid’s algorithm is both straight forward and nicely expressed in a recursive fashion:

And now in code:

```
; find the greatest common divisor of two numbers
; source: http://en.wikipedia.org/wiki/Greatest_common_divisor
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
```

With that, it’s nice and easy to calculate the least common multiple of 1 through any number n. Just use the same `for/fold`

macro I talked about yesterday (albeit without the `*`

):

```
; calculate the least common multiple of a range
(define (least-common-multiple-up-to n)
(for/fold ([res 1])
([i (in-range 1 (+ n 1))])
(lcm res i)))
```

So we start with the result `res`

at 1 then repeatedly take the `lcm`

of the current result and the new number. Check it on the small example given:

```
> (time (least-common-multiple-up-to 10))
cpu time: 0 real time: 0 gc time: 0
2520
```

Good to go. Extend it for the full example:

```
> (time (least-common-multiple-up-to 20))
cpu time: 0 real time: 0 gc time: 0
232792560
```

And we’re good to go. You can’t really beat 0 ms.

As always, you can download my code for this or any Project Euler problem I’ve uploaded here.