blakeembrey/code-problems — pull request #8 by amitburst (2013-06-09 08:42:01+00:00)
Title: Add optimized multiples-of-3-and-5 in Python

I've always loved this problem, it's what got me hooked on Project Euler. Alright, time to get a little mathematical...

This problem is a prime example of the [Inclusion-exclusion principle](http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) which states that the cardinality (size) of the union of two finite sets is given by the following formula:

>`|A ∪ B| = |A| + |B| - |A ∩ B|` (remember from set theory that ∪ corresponds to logical OR).

In this problem this reads as: the sum of all multiples of 3 + sum of all multiples of 5 - sum of all multiples of 3 and 5 (15). As you can see, this accounts for duplicate multiples, which is the tricky part of this problem! Given this formula, you can actually compute the result of this problem in constant time, which is awesome. To do this, I used the formula `n * (n + 1) / 2`, which gives us the sum of integers from 1 to n. For example, to compute the sum of all multiples of 3 under 1000, we simply do `3 * (333 * 344 / 2)`. This makes sense because there are 333 multiples of 3 below 1000. Now, applying the Inclusion-exclusion principle, we get the final formula:

>`(3 * 333 * 334 / 2) + (5 * 199 * 200 / 2) - (15 * 66 * 67 / 2) = 233168`.

Pretty neat, huh? We didn't even need code!

But of course, code allows us to make this extensible. My code allows for any number of multiples and any upper limit, just as yours does (Inclusion-exclusion principle is beautifully extensible).

Anyway, I thought this was a neat and different approach!