If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000. – Project Euler #1
We start off relatively simple, just asked to sum up a thousand numbers.
for/sum does exactly what we want, looking over all of the values and adding them up. The
#:when clause does the rest, limiting it to just numbers divisible by 3 or 5.
(define (sum-divisibles limit) (for/sum ([i (in-range 1 limit)] #:when (or (divides? i 3) (divides? i 5))) i)) ; test if n evenly divides m (define (divides? m n) (= 0 (remainder m n)))
> (time (sum-divisibles 1000)) cpu time: 0 real time: 1 gc time: 0 233168
Alternatively, this could be done using a bit of discrete mathematics. We have three arithmetic series of interest:
The sum of numbers divisible by 3:
The sum of numbers divisible by 5:
The sum of numbers divisible by 3 and 5. Since
lcm(3,5) = 15, this is equivalent to the sum of numbers divisible by 15:
All together, we need to add the numbers divisible by 3 and 5. Since the numbers divisible by 15 are counted in both, subtract one copy of those:
And there you have it. The first of (hopefully) many posts on Project Euler.
If you’d like to download my code for this or any Project Euler problem I’ve uploaded it here.