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.
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.
# Single line using list comprehensions in Python print (sum(i for i in range(1, 1000) if i%3==0 or i%5==0)) # A classical way in Python s = 0 for i in range(1, 1000): if i%3==0 or i%5==0: s+= i print (s)
The program runs instantly for upper bounds like 1000, but does not scale well for larger ones such as 109. So, we need to find a more efficient way of calculating this sum without looping.
A formula attributed to Carl Friedrich Gauss will calculate the sum of the first n natural numbers.
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. 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 n/2 columns for any number n. If n is odd, simply start with zero instead of one.
Which is the same formula as Gauss’s.
Counting every dth 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 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=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 taking the floor of 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.
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 but we must first subtract the sum of every 15th natural number (3 × 5) as it is counted twice: once in the 3 summation and once again in the 5 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, 15, …) or 5 (5, 10, 15, …) and subtract those divisible 3 and 5 (15, 30, 45, …).
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 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
The summation formula is the legacy of Carl Friedrich Gauss, the German mathematician. Here’s how he figured it out:
The sequence [1, 3, 6, 10, 15, …] is called the triangular numbers and count 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 + … + 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 meddlesome problems to keep his class busy and quiet. While the other students labored away, the ten–year–old Gauss handed his teacher the tablet with his answer within seconds.
The teacher was surprised when he looked at the tablet to find the correct answer — 5,050 — with no steps in the calculation. The teacher thought that Gauss must have cheated somehow. But Gauss explained that all one needed to do was put N=100 into the formula 1/2 × (N + 1) × N resulting in the 100th number in the list without further additions.
Rather than tackling the problem head on, Gauss had thought geometrically. 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 and adjacent to the first triangle. Now Gauss had a rectangle with 100 rows containing 101 beans each. Calculating the number of beans in this rectangle built from the two triangles was easy. There are in total 100 × 101 = 10,100 beans, so each triangle must contain half this number, namely 1/2 × 10,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
See also, Project Euler 6: Sum square difference