Project Euler (problem 1)

I just discovered Project Euler and I thought I'd start going through the problems, in order, to keep up my math and programming knowledge. Here's the text of the first 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.

There seem to be two straightforward ways to solve this problem. You could write a program that goes through every integer below 1000, adding the ones that are a multiple of 3 or 5. You could also come up with an expression for the sum, and then carry out the necessary calculations by hand. I'll try both methods here.

First, the program, since I think it will be faster for this problem. This code was written in an IPython notebook.

sum = 0

for i in range(1000):

    if (i % 3 == 0) or (i % 5 == 0):

        sum += i

print sum

Then, by "hand": The solution can be found using fewer operations by applying some logic. We want to sum every multiple of 3 or 5. We can do this by summing the multiples of 3, adding the sum of the multiples of 5, and then subtracting the sum of the multiples of 15, since multiples of 15 would be counted twice otherwise.

1000/3 is 333 remainder 1. This means that the sum from threes is 3 * (1 + 2 + ... + 332 + 333). Similarly, the sum from the fives is 5 * (1 + 2 + ... + 198 + 199). The sum that needs to be subtracted because of the doubly-counted fifteens is 15 * (1 + 2 + ... + 65 + 66). Adding together the first two expressions and subtracting the third gives:

-7 * (1 + 2 + ... + 65 + 66) + 8 * (67 + 68 + ... + 198 + 199) + 3 * (200 + 201 + ... + 332 + 333)

The first set of parentheses contains 66 terms. It's apparent that they can be simplified: 1 + 66 = 67, 2 + 65 = 67, and so on, until 33 + 34 = 67. Therefore, the value contained is just 33 * 67. A similar approach can be used to simplify the other sums in parentheses, giving:

-7 * (33 * 67) + 8 * (66.5 * 266) + 3 * (67 * 533)

This result matches the brute force method, so everything worked out.

Most of the problems in Project Euler can be easily brute-forced with a fairly simple program, but by coming up with better algorithms, every problem should be solvable in under 1 second on an everyday computer. This encourages the use of elegant solutions that save computer time, and provides a more interesting challenge.