Multiples of 3 or 5

8/11/2025 8/11/2025 Blog 5 min read (866 words)

Project Euler - Problem 1

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$.

Solution

First let’s define varibales for the upper bound as well as for the multiples of $3$ and $5$.

# upper bound
n = 1000
n -= 1

a = 3
b = 5

I subtract $1$ from $n$ because I do not want to handle an exclusive upper bound in the functions later described. So from here on we can handle our upper bound $n$ as an inclusive one.

Solution 1: Simple iteration

We can use a simple iteration to find the multiples of $3$ or $5$ by iterating over the numbers from $1$ to $n$ and checking if the number is divisible by one of the multiples:

def sum_multiples_of(n, *ms):
    running_sum = 0
    for i in range(1, n + 1):
        for m in ms:
            if i % m == 0:
                running_sum += i
                break
    return running_sum

result = sum_multiples_of(n, a, b)

Solution 2

The Gaussian Summation Formula is a very useful tool which is going to help us to calculate the sum of our multiples without the need of iterations.

Gaussian Summation

For the gaussian sum we want to find the sum of the first $n$ natural numbers:

$$\sum_{k=1}^n k$$

First, we write the numbers from $1$ up to $n$ in a row:

$$1 \quad 2 \quad \dots \quad n-1 \quad n$$

Next, right underneath that, we write the same numbers but in reverse order:

$$n \quad n-1 \quad \dots \quad 2 \quad 1$$

Now, if we add the numbers in each column, something interesting happens. Every column adds up to the same total $n+1$. For example, the first column is $1 + n = n+1$, the second is $2 + (n-1) = n+1$, and so on.

Putting that together, it looks like this:

$$\begin{array}{ccccc} 1 & 2 & \ldots & n-1 & n \\ n & n-1 & \ldots & 2 & 1 \\ \hline n+1 & n+1 & \ldots & n+1 & n+1 \end{array}$$

Since there are $n$ columns and each adds up to $n+1$, the total sum of both rows combined is

$$n \times (n+1)$$

Because both rows contain exactly the same numbers, the sum of just one row must be half of that total. So we divide by 2:

$$\frac{n \times (n+1)}{2}$$

And so we arrive at the formula for the sum of the first $n$ natural numbers:

$$\sum_{k=1}^n k = \frac{n(n+1)}{2}$$

Gaussian Summation for multiples of 3 or 5

Now let’s take an example with $n = 20$ and consider the multiples of $m = 3$. The numbers look like this:

$$3 \quad 6 \quad 9 \quad 12 \quad 15 \quad 18$$

If we write these numbers in ascending order in one row, and the same numbers in descending order right below, we get:

$$\begin{array}{cccccc} 3 & 6 & 9 & 12 & 15 & 18 \\ 18 & 15 & 12 & 9 & 6 & 3 \\ \hline 21 & 21 & 21 & 21 & 21 & 21 \end{array}$$

Each column sums to the same number, which is the first multiple plus the last multiple: $m + c \times m$, where $c$ is the number multiples up to $n$:

$$c = \left\lfloor \frac{n}{m} \right\rfloor = 6$$

In this example, the highest multiple is $c \times m = 18$, so each column sums to:

$$m + c \times m = 3 + 18 = 21$$

Since there are $c$ columns, the total sum of both rows combined is:

$$c \times (m + c \times m)$$

And because the two rows are identical sets of numbers, the sum of just one row (the sum of all multiples of $m$ up to $n$) is half of that:

$$\sum_{k \in \mathbb{M}_{n,m}} k = \frac{c \times (m + c \times m)}{2}$$

Here, $\mathbb{M}_{n,m} = \{ k \in [1, n] \mid m \mid k \}$ is the set of multiples of $m$ up to $n$.

To find the sum of all multiples of $a$ or $b$ up to $n$, we use the inclusion-exclusion principle:

$$\sum_{k \in \mathbb{M}_{n,a} \cup \mathbb{M}_{n,b}} k = \sum_{k \in \mathbb{M}_{n,a}} k + \sum_{k \in \mathbb{M}_{n,b}} k - \sum_{k \in \mathbb{M}_{n,\mathrm{lcm}(a,b)}} k$$

Here, $\mathrm{lcm}(a,b)$ is the least common multiple of $a$ and $b$, which by subtracting avoids counting common multiples twice. In other words $\mathbb{M}_{n, \mathrm{lcm}(a,b)} = \mathbb{M}_{n,a} \cap \mathbb{M}_{n,b}$.

Since $a=3$ and $b=5$ are distinct primes, the least common multiple of $a$ and $b$ is $\mathrm{lcm}(a,b) = a \times b$.

Therefore, the sum of all multiples of $a$ or $b$ up to $n=999$ can be computed with:

def sum_multiples_of(n, m):
    c = n // m
    return c * (m + c * m) // 2


result = sum_multiples_of(n, a) + sum_multiples_of(n, b) - sum_multiples_of(n, a * b)
print(result) # 233168

pythonmathproject-euler