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 1: Mathematical View.

Multiples of 3: 3, 6, 9, 12, 15, ... Multiples of 5: 5, 10, 15, 20, 25, ... Multiples of 15(3 & 5): 15, 30, 45, 60, 75, ...

So we were asked the sum of arithmetic progression - arithmetic series. This can be solved by the equation of arithmetic series. You can read it here. Arithmetic progression.

Using the equation of arithmetic series: The arithmetic series of multiples of 3 below 1000 is 333 * (3 + 999) / 2 = 166833.0. The arithmetic series of multiples of 5 below 1000 is 199 * (5 + 995) / 2 = 99500. The arithmetic series of multiples of 15 below 1000 is 66 * (15 + 990) / 2 = 33165. We are not asked to add multiples of 15 but we need to subtruct multiples of 15 since it was counted on both side.

So the answer is summing the sum of multiples of 3 and 5 and subtructing sum multiples of 15.

The output: 233168

This only takes pencil and paper. May be calculator.

Solution 2: Brute Forcing.

Let's go through all natural numbers below 1000 and add to our variable if it is divisible by 3 or 5.

Here is my code in python:

total = 0

for n in range(1, 1000): if n%3 == 0 or n%5 == 0: total += n
print(total)

The output: 233168

This code run ~0.0. So may be there is not the room for improvement!

Solution 3: Improved Brute Forcing.

We can improve this by making the iteration to the candidates. By iterating through multiples of 15 and adding the pattern of multiples of 3 and 5, we will reduce the iteration from 999 to 66.

Improved code:

total = 0

for n in range(0, 990, 15): total += 30 + 4*n total += 30 + 3*n
total += 993 + 996 + 999 total += 995
print(total)

The output: 233168

This code run ~0.0