Mihir Yerande

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.

At first glance, we could write some simple code to programmatically solve this by brute-force.
The strategy would be to iterate upwards from 1, and add the relevant numbers along the way.

The code for this would be as follows:
The computational complexity of this code would be:

• Time → Linear, i.e. \(O(N)\)
• Space → Constant, i.e. \(O(1)\)

The previous approach ends up considering many irrelevant numbers.
We're only really concerned with multiples of 3 or 5.
Suppose we alter the code to ignore irrelevant numbers by skipping directly to our desired multiples.

The code would then be as follows:
However, note that we would end up counting certain values twice...

• Multiples of 3 → 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, ...
• Multiples of 5 → 5, 10, 15, 20, 25, 30, 35, ...

• No longer iterating across every number less than \(N\)
• No longer checking for divisibility by 3 or 5

Let's instead directly examine the summation itself, \(S\), which we are looking to compute.

\(\hspace{1em}S = \displaystyle\sum_{x=1\text{ ; }3 \vert x \hspace{0.2em} \vee \hspace{0.2em} 5 \vert x}^{N-1} x\)

Inclusion-Exclusion Principle

Using the overall idea from the PIE (principle of inclusion-exclusion), we can break this down into separate, simpler summations.

\( \begin{align*} \hspace{1em}S &= \displaystyle\sum_{x=1\text{ ; }3 \vert x \hspace{0.2em} \vee \hspace{0.2em} 5 \vert x}^{N-1} x &\text{Original summation} \\ \hspace{1em} &= \displaystyle\sum_{x=1\text{ ; }3 \vert x}^{N-1} x + \displaystyle\sum_{x=1\text{ ; }5 \vert x}^{N-1} x - \displaystyle\sum_{x=1\text{ ; }3 \vert x \hspace{0.2em} \wedge \hspace{0.2em} 5 \vert x}^{N-1} x &\text{Separate using PIE} \\ \hspace{1em} &= \displaystyle\sum_{x=1\text{ ; }3 \vert x}^{N-1} x + \displaystyle\sum_{x=1\text{ ; }5 \vert x}^{N-1} x - \displaystyle\sum_{x=1\text{ ; }15 \vert x}^{N-1} x &\text{Multiples of 3 and 5 }\equiv\text{ Multiples of 15} \end{align*} \)

Notice here that the multiples of 15 are again subtracted, which avoids double-counting.

Gauss's Little Formula

Each of these summands is the sum of a finite arithmetic progression.
Thus we can take advantage of Gauss's Little Formula to convert each to a closed-form expression.
Recall the closed-form expression, as follows:

\( \hspace{1em}\displaystyle\sum_{i=1}^n i = \frac{n \cdot (n+1)}{2} \)

In the following, let \(N_m = \displaystyle\left\lfloor\frac{N-1}{m}\right\rfloor\), that is, the number of positive multiples of \(m\) below \(N\).

\( \begin{align*} \hspace{1em}S &= \displaystyle\sum_{x=1\text{ ; }3 \vert x}^{N-1} x + \displaystyle\sum_{x=1\text{ ; }5 \vert x}^{N-1} x - \displaystyle\sum_{x=1\text{ ; }15 \vert x}^{N-1} x &\text{Expression from above} \\ \hspace{1em} &= \displaystyle\sum_{i=1}^{\lfloor (N-1)/3 \rfloor} 3i + \sum_{i=1}^{\lfloor (N-1)/5 \rfloor} 5i - \sum_{i=1}^{\lfloor (N-1)/15 \rfloor} 15i &\text{Ignore non-multiples} \\ \hspace{1em} &= \displaystyle\sum_{i=1}^{N_3} 3i + \sum_{i=1}^{N_5} 5i - \sum_{i=1}^{N_{15}} 15i &\text{Substitute in }N_m \\ \hspace{1em} &= \displaystyle 3\cdot\sum_{i=1}^{N_3} i + 5\cdot\sum_{i=1}^{N_5} i - 15\cdot\sum_{i=1}^{N_{15}} i &\text{Factor out constants} \\ \hspace{1em} &= \displaystyle 3\cdot\frac{N_3(N_3+1)}{2} + 5\cdot\frac{N_5(N_5+1)}{2} - 15\cdot\frac{N_{15}(N_{15}+1)}{2} &\text{Apply Gauss's Little Formula} \end{align*} \)

Final Code

We've finally arrived at a closed-form expression to directly calculate the desired sum!
This can easily be coded as follows:
The time-complexity has been reduced to \(O(1)\) as we only need to compute a fixed number of arithmetic operations.

The answer can easily be computed manually with a calculator, giving the following:

\( \begin{align*} \hspace{1em}S &= \displaystyle 3\cdot\frac{N_3(N_3+1)}{2} + 5\cdot\frac{N_5(N_5+1)}{2} - 15\cdot\frac{N_{15}(N_{15}+1)}{2} \\ \hspace{1em} &= \displaystyle 3\cdot\frac{333(333+1)}{2} + 5\cdot\frac{199(199+1)}{2} - 15\cdot\frac{66(66+1)}{2} \\ \hspace{1em} &= 166,833 + 99,500 - 33,165 \\ \hspace{1em} &= 233,168 \end{align*} \)

The full Python3 code for my solution implementation can be found here: GitHub Solution