Project Euler Problem 1 Solution: Multiples of 3 and 5

Project Euler Problem 1 Statement

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

Obvious solution

A solution can be implemented quickly and intuitively by using an iterative approach that loops through a range of integers between $1$ and $999$. Using the mod operator to check for even divisibility (a zero remainder after division) we sum those integers, i, that are divisible by $3$ or $5$.

print(sum(i for i in range(1, 1000) if i%3==0 or i%5==0))

The program runs instantly for upper bounds like $1000$, but does not scale well for larger ones such as $10^9$. So, we need to find a more efficient way of calculating this sum without looping.

Scalable solution

A formula attributed to Carl Friedrich Gauss will calculate the sum of the first $n$ natural numbers.

$$\sum\limits_{i=1}^n i = \frac{n(n+1)}{2}$$

For example, when $n=10$ the sum of all the natural numbers from $1$ through $10$ is: $(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) = \frac{10*11}{2} = 55$. This is an example of a closed–form expression describing a summation.

Here’s how this formula works for $n=10$. Write the numbers in two rows that wrap around as shown below:

 1  2  3  4  5
10  9  8  7  6

The sum of each column is $11$ (i.e., $n+1$). As the top row increases, the bottom row decreases, so the column sum always stays the same, and we’ll always have two rows and $\frac{n}{2}$ columns for any number $n$. If $n$ is odd then start with zero to keep the columns paired.

$$\displaystyle{\text{Columns * Column sum} = (\frac{n}{2})(n+1) = \frac{n(n+1)}{2}}$$

Which is the same formula as Gauss’.

Counting every d^th number

We can adapt this formula to count the numbers only divisible by $d$ to a specific upper bound, such as $n=33$, $d=3$, as shown in the following example. Remember, when there is an odd number of elements we start from zero. Here’s how the adaptation works:

 0  3   6   9  12  15
33 30  27  24  21  18

Each of the $6$ columns sum to $33$ and, using our understanding from above, we calculate $6\times 33=198$ to find the sum of numbers from $0$ to $33$ that are evenly divisible by $3$. In our Python function, sumn() (shown below), this is accomplished by using the floor function on $n$ divided by $d$ to find the number of non–zero terms. Then, calculate the sum using an expanded formula which accounts for the multiplier, $d$.

$$\displaystyle{m=\lfloor\frac{n}{d}\rfloor}$$ $$\displaystyle{\sum\limits_{i=1}^m id = d\hspace{1mm}\frac{m(m+1)}{2}}$$

By applying the above formula to $n=999$ and $d=3$ and $d=5$ we get the sums for every third and fifth natural number. Adding those together is almost our answer; we must first subtract the sum of every $15th$ natural number ($3\times 5$) as it is counted twice: once in the $3$'s summation and once again in the $5$'s summation.

This is a typical application of the inclusion–exclusion principle. In general, sum the numbers less than $1000$ that are divisible by $3 (3, 6, 9, 12, \textbf{15}, \ldots)$ or $5 (5, 10, \textbf{15},\ldots)$ and subtract those divisible by $3$ and $5 (\textbf{15}, 30, 45, \ldots)$.

This solution is much faster than using brute force which requires loops. Also note that we subtract one from the upper bound as to exclude it.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 1

HackerRank Project Euler 1 increases the upper bound from 1,000 to 1 billion and runs 10,000 test cases. The iterative approach simply won’t work fast enough, but the presented closed–form will.

Python Source Code

def sumn(n, d):
    n//= d
    return d*n*(n+1) // 2
a, b = 3, 5

for _ in range(int(input())):
    L = int(input())-1
    print(sumn(L, a) + sumn(L, b) - sumn(L, a*b))

Last Word

The summation formula is the legacy of Carl Friedrich Gauss, the German mathematician. Here’s how he figured it out:

The series ${1, 3, 6, 10, 15, \ldots}$ is called the triangular number sequence and counts objects arranged in an equilateral triangle. The game of bowling, or ten–pin, sets 10 pins in a equilateral triangular form: one pin in the first row through $4$ pins in the last row.

To calculate the Nth triangular number you add the first $N$ numbers: $1 + 2 + 3 +\ldots + N$. If you want to find the 100th triangular number, you begin the long and laborious addition of the first $100$ numbers.

Gauss's teacher, known for assigning laborious problems to keep the class occupied and quiet, gave the students the task of adding the first 100 numbers. While most students diligently worked through the tedious addition, the ten-year-old Gauss stunned everyone by presenting the correct answer, 5050, almost instantly.

Thinking geometrically

Gauss's geometric approach simplifies what appears to be a complicated problem. By pairing the triangular arrangement (shown below) with its inverted counterpart, he transformed the problem into calculating the area of a rectangle—an easy task. This method not only solved the specific problem at hand but also provided a general formula for triangular numbers:

$$\text{Triangular Number} = \frac{N\times (N+1)}{2}$$

Example for 5 rows, shifted left and right:

x                 o      x o o o o o
x x             o o      x x o o o o
x x x         o o o  –>  x x x o o o
x x x x     o o o o      x x x x o o
x x x x x o o o o o      x x x x x o