Physx 1: Project Euler, Problem 1

Hello! And welcome to the first in my series of notes on math & physics. Here, I pen down any interesting problem I’m currently looking at, and try to break it down into the basics.

Today, we are looking at Project Euler’s first of many interesting math problems:

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.

If you want to try it out yourself, then pause here as I dive straight into the solution.

From a programming perspective, you would think it’s an easy solution and solve it in O(n) time. But it can be solved in O(1).

The problem first needs to be split into the individial numbers, 3 & 5. Now, what is the formula for solving this? The answer is the summation of the multiples of 3 & 5, until 1000. i.e.

\[ \sum_{i=1}^{333} 3i + \sum_{i=1}^{199} 5i \]

where summation is the sum of a series of numbers of a pre-defined limit, in this case, i is the starting point and n is the limit.

\[ \sum_{i=1}^{n} x_i = x_1 + x_2 + ... + x_n \]

For example:

\[ \sum_{i=1}^{4} 3i = (3\times{1}) + (3\times{2}) + (3\times{3}) + (3\times{4}) \]

Here, you may be wondering, why 333 & 199? We have to divide 1000 over 3 & 5 respectively to get the number of multiples of the 3 & 5 until 1000. However, since the question asks for multiples less than 1000, we cannot use exactly 1000, but the next closest integer, 999. If you spot this, congratulations! The 1000/5 would have felt off somehow.

The other part to this problem is, how to you actually calculate summation? It may not be inherently obvious, but there is a formula to it. Looking at an example, there is a pattern somewhere that can be extracted.

\[1 + 2 + 3 + 4 + 5 + 6\]

You’d first notice that there is a symmetry to the numbers - you can add it up like so:

\[(1 + 6) + (2 + 5) + (3 + 4) = 7 + 7 + 7 = 7 * 3 \]

Now, we must be getting close to cracking it! But how to you generify this? From the result, you can see that 7 is n + 1, and 3 would be n / 2 because you are basically dividing the sequence into 2 parts. And so we have a formula:

\[ \frac{n}{2}(n + 1) \]

But it doesn’t feel right. What if there is an even numbered sequence? e.g. 1 + 2 + 3 + 4 + 5 + 6 + 7 Somehow, this formula still holds up.

\[ \frac{7}{2}(7 + 1) = 28 \text{ - this is correct}\]

Why does this work? Because if we had a single middle number or 2 middle numbers, we only care about the mean. Since the 2 numbers would be summed and divided by 2, having the single number doesn’t make a difference.

Now finally, we have a solution.

\[ \sum_{i=1}^{333} 3i + \sum_{i=1}^{199} 5i = 3\times\frac{333}{2}(333 + 1) + 5\times\frac{199}{2}(199 + 1) \]

Unfortunately, life is not perfect and this is still not yet complete. Since we will have the same multiples of 3 & 5, there will be duplicates. But the good thing is the fix is easy! We just have to remove all the common multiples. But how? If it were a different pair of numbers that were divisible by each other, it would have been a lot harder, but in our case, all the common multiples are just multiples of 3 * 5, i.e. we can just subtract this sum with the summation of 15.

And hence, we have our final solution here:

\begin{gather*} \sum_{i=1}^{333} 3i + \sum_{i=1}^{199} 5i - \sum_{i=1}^{66} 15i\\ = 3\times\frac{333}{2}(333 + 1) + 5\times\frac{199}{2}(199 + 1) - 15\times\frac{66}{2}(66 + 1)\\ = 233168 \end{gather*}