**The problem:**

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.

**Solutions**:

Solve this problem using the computer way is easy. Just loop through 1000 numbers, find numbers that are either multiples of 3 or multiples of 5 then add them up.

for i in range(0, 1000): if i % 3 == 0 or i % 5 == 0: total += i #result: 233168 print(total) # or much shorter statement total = sum([i for i in range(1000) if (i % 3 == 0 or i % 5 == 0)])

However this isn't a efficient way to do it as the loop runs 1000 times in this case. Although it still runs very fast in any computer, there is a better way to do it: the mathematical way.

Notice the sequence of all numbers divisible by 3 from 1 to 1000 looks like this

total = 3 + 6 + 9 + ... + 999 = 1*3 + 2*3 + 3*3 + ... 333*3 = 3 * (1 + 2 + 3 + ... + 333)

The sequence for 5 is quite similar

total = 5 * (1 + 2 + 3 + ... + 199)

So how the sequence 1 + 2 + 3 + ... + n is calculated. The formula is quite simple:

total = (first_numer + last_number) * length_of_sequence / 2

Here is the solution written in Python:

# Sum of sequence like 1 2 3 4 5 ... n def sum_of_sequence(start=1, end=1000): return int((start + end) * (end - start + 1) / 2) total = 3 * sum_of_sequence(1, 333) + 5 * sum_of_sequence(1, 199) # The reason for this part is when summing up the sequence of numbers divisible by 3 and 5 # the numbers that is divisible by both 3 and 5 is calculated twice total = total - 15 * sum_of_sequence(1, 66)

I'm gonna make this code a bit better. Continued from the above code:

def sum_of_sequence_divisible_by(x, start=1, end=1000): # y is smallest multiply of x # if the start number of the sequence less than x # then the smallest multiply of x in the sequence is x y = x if start > x: # if start number of the sequence greater than x # find the nearest multiply of x for i in range(start, end): if i % x == 0: y = i break return x * sum_of_sequence(y / x, int(end / x)) total = sum_of_sequence_divisible_by(3) + sum_of_sequence_divisible_by(5) total = total - sum_of_sequence_divisible_by(15) print(total)