(17 votes, average: 5.00 out of 5)

## Project Euler 1: Find the sum of all the multiples of 3 or 5

#### Project Euler 1 Problem Description

Project Euler 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.

#### Analysis

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, 15, …) or 5 (5, 10, 15, …) and subtract those divisible 3 and 5 (15, 30, 45, …) as they are counted twice.

This solution is much faster than using brute force which require loops, especially when the limit, L, is large. Also note that we subtract 1 from the limit as the problem wants multiples below L.

#### Project Euler 1 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 1 Solution Python 2.7 source.

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|233168|

#### Afterthoughts

• It’s helpful to know the formula for the sum of the first n natural numbers (positive integers):
$\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) = 10*11 / 2 = 55.

Here’s how this formula works. 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 2 rows and n/2 columns for any even number, n. If n is odd, start with zero instead of one.

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

which is the same formula as above.

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

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


Each column sums to 33 and, using our understanding from above, we calculate 6*33 to find the sum of numbers to 33 that are evenly divisible by 3 (6*33=198). In the Python function sumn this is accomplished by taking the floor of n divided by d to find the number of terms, then, modifying our formula to account for d (3, in this example), we calculate a sum.

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

The formula is the legacy of Carl Friedrich Gauss, the German mathematician. An anecdote of its discovery is retold below:

The sequence of numbers [1, 3, 6, 10, 15,…] are called the triangular numbers. The tenth number on the list is the number of beans required to build a triangle with ten rows, starting with one bean in the first row and ending with ten beans in the last row. The game of bowling or ten-pin sets 10 pins in a triangular form and thus uses the fourth number in this sequence.

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

Indeed, Gauss’s teacher liked to assign these kinds of problems to his class as it would keep them busy and quiet for some time. As each student finished the task they would place their slate tablets with their answer written on it in a pile in front of the teacher. While the other students began laboring away, the ten-year-old Gauss had laid his tablet on the table within seconds. Dubious, the teacher thought the young Gauss was being lazy. But when he looked at Gauss’s slate, there was the answer — 5,050 — with no steps in the calculation. The teacher thought that Gauss must have cheated somehow, but the pupil explained that all you needed to do was put N=100 into the formula 1/2 × (N + 1) × N and you will get the 100th number in the list without having to calculate any other numbers on the list.

Rather than tackling the problem head on, Gauss had thought laterally. He argued that the best way to discover how many beans there were in a triangle with 100 rows was to take a second similar triangle of beans which could be placed upside down on top of the first triangle. Now Gauss had a rectangle with 101 rows each containing 100 beans. Calculating the number of beans in this rectangle built from the two triangles was easy: there are in total 101 × 100 = 10,100 beans. So one triangle must contain half this number, namely 1/2 × 101 × 100 = 5,050.

Example for 5 rows

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


Project Euler 1

Project Euler 1 Solution last updated