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