If you watched the video of Randall Munroe at Google you might have heard him mention a site called Project Euler. It’s a cool collection of short but interesting mathematical problems that are intended to be solved with a computer. That said, there’s nothing stopping you from using good old practical mathematics.
The most solved puzzle on the site is this one:
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.
Now, this didn’t look to me like a computer was required to solve it, so I nibbled the end of my pencil for a second and came up with the following solution:
There will be 333 numbers in that range which are divisible by three (every third number, so a third of the total). There will be 199 numbers in that range that are divisible by five (every fifth number, and a fifth of the total—it’s 199 rather than 200 because the top number, 1000, is excluded).
Now I don’t know offhand a way to calculate the sum of the first 333 numbers divisible by three. But I do know offhand a way to calculate the sum of the first 333 numbers. It’s 333 × 334 ÷ 2. Is that any help? It turns out it is. Consider the first five multiples of three: 3, 6, 9, 12, 15. The sum is 3 + 6 + 9 + 12 + 15 = (3 × 1) + (3 × 2) + (3 × 3) + (3 × 4) + (3 × 5) = 3 × (1 + 2 + 3 + 4 + 5). That is, it’s three times the sum of the first five numbers. By the same reasoning, the sum of the first 333 multiples of three is equal to three times the sum of the numbers from one to 333, or 3 × 333 × 334 ÷ 2.
Applying the same reasoning again, the sum of the first 199 multiples of five is five times the sum of the first 199 numbers, or 5 × 199 × 200 ÷ 2.
There’s one more piece: in adding up all the multiples of three, and all the multiples of five, I’ve included some numbers twice. There are some numbers that are divisible by both three and five, i.e., those numbers divisible by fifteen. There are 66 of these, from 15 to 990 (again, by taking 1000 ÷ 15 and rounding down you get 66). So the total has to be reduced by 15 × 66 × 67 ÷ 2.
The final answer is: (3 × 333 × 334 ÷ 2) + (5 × 199 × 200 ÷ 2) – (15 × 66 × 67 ÷ 2) = 233168.
The easy way, of course, is:
$> python
>>> sum([i for i in range(1,1000) if i % 5 == 0 or i % 3 == 0])
233168