web developer

# Euler problem #1: Multiples of 3 and 5

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)```