Project Euler : Problem 1

I solved problem 1 with the knowledge that the sum of an arithmetic sequence is:

Problem 1 says:
“Add all the natural numbers below one thousand that are multiples of 3 or 5.”

So, the sum of all natural numbers between 0 and 999 (inclusive) that are multiples of 3 and 5 is equal to the sum of the natural numbers that are multiples of 3, plus the sum of the natrual numbers that are multiples of 5, minus the sum of the natural numbers that are multiples of 15.

We subtract the sum of the multiples of 15 because multiples of 15 are double counted when we add the sum of the multiples of 3 to the sum of the multiples of 5.

Here is a quick example that illustrates why we subtract the sum of the multiples of 15:

This is the sum of the multiples of 3 from 0 through 15:
0 + 3 + 6 + 9 + 12 + 15

This is the sum of the multiples of 5 from 0 through 15:
0 + 5 + 10 + 15

Now when we sum those two sums, we double count 15:
(0 + 3 + 6 + 9 + 12 + 15) + (0 + 5 + 10 + 15)

We subtract the sum of the multiples of 15 to ensure that multiples of 3 and 5 (i.e. multiples of 15) are only counted once (instead of twice - double counting them):
(0 + 3 + 6 + 9 + 12 + 15) + (0 + 5 + 10 + 15) - (0 + 15)

So, to solve the problem I computed the sum of the multiples of 3 from 0 to 999:
0 + 3 + 6 + … + 999 = 334 * (0 + 999)/2 = 166833

Where did 334 come from? That’s n in the equation above. According to wikipedia:

If the initial term of an arithmetic progression is a₁ and the common difference of successive members is d, then the nth term of the sequence is given by:

and in general

I computed n as follows:
a_n = a₁ + (n - 1) * d
=> 999 = 0 + (n - 1) * 3
=> 333 = 0 + (n - 1)
=> 333 = n - 1
=> 334 = n
=> n = 334

So, the sum of the multiples of 3 from 0 to 999 is:
0 + 3 + 6 + … + 999 = 334 * (0 + 999) / 2 = 166833

Now to compute the sum of the multiples of 5 from 0 to 995:
0 + 5 + 10 + … + 995 = 200 * (0 + 995) / 2 = 99500

I computed n = 200 as follows:
a_n = a₁ + (n - 1) * d
=> 995 = 0 + (n - 1) * 5
=> 199 = 0 + (n - 1)
=> 199 = n - 1
=> 200 = n
=> n = 200

So, the sum of the multiples of 5 from 0 to 995 is:
0 + 5 + 10 + … + 995 = 200 * (0 + 995) / 2 = 99500

Finally, we compute the sum of the multiples of 15 from 0 to 990:
0 + 15 + 30 + … + 990 = 67 * (0 + 990) / 2 = 33165

I computed n = 67 by:
a_n = a₁ + (n - 1) * d
=> 990 = 0 + (n - 1) * 15
=> 66 = 0 + (n - 1)
=> 66 = n - 1
=> 67 = n
=> n = 67

So, the sum of the multiples of 15 from 0 to 990 is:
0 + 15 + 30 + … + 990 = 67 * (0 + 990) / 2 = 33165

The final sum is:
(sum of multiples of 3) + (sum of multiples of 5) - (sum of multiples of 15)
=> 166833 + 99500 - 33165 = 233168

So, the sum of the natural numbers that are multiples of 3 or 5 and less than 1000 is 233168.