Another Unreasonably Deep Dive into Project Euler Problem 1
As part of my studies at https://flatironschool.com/, I was asked to solve Project Euler’s first problem, https://projecteuler.net/problem=1, using Ruby.
While simple at first glance, employing a bit of number theory opens up a solution that is drastically more efficient and extensible.
Adam Drake did a fantastic writeup of this problem using Go, from which I borrowed the namesake: https://adamdrake.com/an-unreasonably-deep-dive-into-project-euler-problem-1.html
The Problem
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 naive solution might iterate over every number from 1 to 999, testing each n for a congruence of 0 modulo 3 or 5. We can accomplish this in a single line using reduce with a ternary operation:
Via brute-force, this gives us the correct answer: 233,168.
Down Gauss’ Rabbit Hole
When I first read the problem, I was immediately reminded of a popular Carl Friedrich Gauss anecdote. Via https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss#Anecdotes:
Another story has it that in primary school after the young Gauss misbehaved, his teacher, J.G. Büttner, gave him a task: add a list of integers in arithmetic progression; as the story is most often told, these were the numbers from 1 to 100. The young Gauss reputedly produced the correct answer within seconds, to the astonishment of his teacher and his assistant Martin Bartels.
Gauss was leveraging the power of an arithmetic series; namely, the triangular numbers. This technique was known to the Pythagoreans as early as 5th century BC. https://en.wikipedia.org/wiki/Triangular_number
The key observation is that the sum of all integers (1+2+3+4+…n) is equivalent to:
Obtaining a sum via this algebraic method, rather than iteration, allows us to reduce complexity from O(n) to O(1). However, in the case of the Project Euler problem, we only want the sum of the multiples of 3 and 5. How can we utilize a similar, algebraic shortcut?
The Hidden Series
Let’s analyze a simplified version of the problem: What is the sum of all multiples of 3, up to a limit of 14?
If we step through each integer, we can observe a familiar pattern:
- …
- …
- … / 3 = 1 three
- …
- …
- … / 3 = 2 threes
- …
- …
- … / 3 = 3 threes
- …
- …
- … / 3 = 4 threes
- …
- …
Rephrasing the problem, if we sum the multiples of 3, up to a limit of 14, it could be said that we are summing 1 three, 2 threes, 3 threes and 4 threes. In other words:
(3 + 6 + 9 + 12) = (1*3 + 2*3+ 3*3 + 4*3)
Via the distributive property, we can simplify this by factoring out the threes:
(1*3 + 2*3+ 3*3 + 4*3) = (1 + 2 + 3 + 4) * 3
Within the parenthesis, we now have a clean arithmetic series to work with; we can quickly solve this using our formula for triangular numbers:
Plugging in the solution, the sum of all multiples of 3, up to a limit of 14 is:
(1 + 2 + 3 + 4) * 3 = (10) * 3 = 30
Finding n
To utilize the formula for triangular numbers, we need to know n — the last integer of our arithmetic series. In the previous example, (1 + 2 + 3 + 4), n was 4.
What if we want the sum of all multiples of 3, up to 517?
n is the integer quotient of the limit and your chosen multiplier m. In other words:
n = limit / m = 517 / 3 = 172, discarding a remainder of 1
Condensing it all into a generalized formula, the sum of all multiples of m, up to a limit is:
Solving for the sum of all multiples of 3, up to a limit of 517:
The Problem of Common Multiples
The original problem asked for the sum of all the multiples of 3 or 5 below 1000. If we apply our formula separately for both 3 and 5, adding the results, will we arrive at the correct answer of 233,168?
Recall our brute-force approach gave us a solution of 233,168. We’re close, but not quite there. What happened?
Looking back at the naive solution, each iteration asked “Is this number a multiple of 3 OR 5?” before adding it to the sum. If the number happened to be a multiple of 3 AND 5, it was nevertheless only evaluated and added once.
Our number-theoretic approach did not account for these common multiples; in effect, we have double-counted 15, 30, 45, 60…n.
We can remedy this by calculating the sum of all the multiples of 15, up to 999, and subtracting that from our previous, erroneous result:
Code and Benchmark
And there we have it: a seemingly O(n) problem, reduced to a near-instantaneous O(1) solution. How does that look in code? Concise.
Benchmarking the sum of all the multiples of 3 or 5 below 1 BILLION:
