Add all the natural numbers below 1000 that are multiples of 3 or 5

April 15th, 2008

Problem #1 of Project Euler

Add all the natural numbers below 1000 that are multiples of 3 or 5.

Analysis:

Sequence of multiple of 3: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, …, 999

Sequence of multiple of 5: 5, 10, 15, 20, 25, 30, …, 995 So, the sum is 3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 + … + 999.

Take note that we have to remove the duplicate of 15, 30, 45, …, 990

Method # 1: using Python

All the natural numbers below 1000 that are multiples of 3 or 5, are divisible by either 3 or 5. Hence, we need to add the numbers that are only divisible by 3 or 5. That is very easy in Python. Using the % operator will give use the remainder of the division.

For example, 4%2 = 0, 4%3 = 1. Therefore, in order to ad the number that is divisible by 3 or 5, we have to check for the remainder. We will only add the numbers that give zero for the remainder.

total = 0
for i in range(1000):
    if not (i % 3 and i % 5):
        total += i

Method # 2: using Arithmetic sequence

To add all natural numbers from 1 to 10:

Notice that the sum will always gives 11, if we write it this way. 11 occurs 10 times, so, 11 x 10 = 110. However, that is the sum of 1 to 10 twice. So, we divide 110 by 2, we get the answer, which is 55.

The formula: Sum = n (a1 + a2) / 2 where n is the number of occurrence of the sequence from a1 to a2.

Back to our problem, the sum of 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, …, 999. Adding the first and last numbers gives us 3 + 999 = 1002. 1002 occurs 333 times, so 1002 * 333 = 333666. Divide it by 2, we get 166883.

Repeat the same procedure for the second sequence of 5s. Then, add the answers. However, as I mentioned previously, remember that we also have to remove the duplicates of 15, 30, 45, …, 990.

The formula would be like this:

sum of multiple of 3 + sum of multiple of 5 - sum of multiple of 15