Problem Statement

Project Euler Problem 1: 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.

Solution

This is straightforward and really doesn't require a computer. The Python implementation I use is just filtering the list 1, 2, ..., 999 if either divisible by 3 or 5 and summing. In general

• since floor(999/3) = 333, there are 333 (3, 6, ..., 999) multiples of 3 below 1000 and the sum of these numbers is 3(1 + ... + 333) = 3(333)(334)/2 = 166833
• since floor(999/5) = 199, there are 199 (5, 10, ..., 995) multiples of 5 below 1000 and the sum of these numbers is 5(1 + ... + 199) = 5(199)(200)/2 = 99500
• since floor(999/15) = 66, there are 66 (15, 30, ..., 990) multiples of 15 below 1000 and the sum of these numbers is 15(1 + ... + 66) = 15(66)(67)/2 = 33165
• in all, we have a sum of 166833 + 99500 = 266333 but all the multiples of 15 are counted twice, so we need to subtract 33165, leaving 233168

Links

• Python Source
• Javascript Source
• Problem List