An Unreasonably Deep Dive into Project Euler Problem 1
Introduction
As part of my work in keeping my technical skills sharp, I periodically go back to basics or solve old problems again in order to ensure my foundations are strong. So it was with great fun that I decided to start back at the beginning with Project Euler.
One of the techniques I also use for this sort of thing is not just to solve the problem, but to really explore it. Write additional code, tests, benchmarks, and explore the underlying mathematics where practical.
With that in mind, here is a deep dive into Project Euler - Problem 1.
Overview
The problem is short and easy to understand:
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 simple brute-force approach to this is simply to iterate through all of the numbers from 1 to 999 (since we are only to check numbers below 1000), check if the number is divisible by 3 or 5, and sum the ones which are.
If you want the Python one-liner:
sum([x for x in range(1000) if ((x % 5 == 0) or (x % 3 == 0))])
Of if you are using Go, as I was:
func bruteForce(limit int) int {
total := 0
for i := 0; i <= limit; i++ {
if math.Mod(float64(i), 5) == 0 || math.Mod(float64(i), 3) == 0 {
total += i
}
}
return total
}
Does it work?
This works fine and both produce the required answer of 233168, which we can verify with some tests in Go:
func TestBruteForce(t *testing.T) {
if bruteForce(9) != 23 {
t.Fatal("The sum of values from 1 to 10 which are divisible by 5 and 3 should be 23")
}
if bruteForce(999) != 233168 {
t.Fatal("The sum of values from 1 to 1000 which are divisible by 5 and 3 should be 233168")
}
}
And we can run the tests to ensure that everything passes and is working normally.
go test -v
=== RUN TestBruteForce
--- PASS: TestBruteForce (0.00s)
PASS
ok _path/... 0.008s
How fast is it?
This is enough for a working solution, and it isn’t too slow, but it’s not great as we can see by the built-in benchmark capabilities in Go.
func BenchmarkBruteForce(b *testing.B) {
for i := 0; i < b.N; i++ {
bruteForce(999)
}
}
A benchmark function takes a *testing.B and iterates up to b.N, which is a number defined by the package and dependent on the stability of the timing of your function call, and produces output telling you how many times the function was run in order to perform the benchmark provide the required execution time per call.
go test -bench .
BenchmarkBruteForce-4 10000 227761 ns/op
So our brute force approach took 10000 iterations to settle on a timing of 227,761 nanoseconds per operation.
Now we have not only solved the problem, but added tests and benchmarks. Perhaps a bit more effort than some people put into Project Euler, but not bad. However, this solution is still linear in the number of elements we have to check. In other words, if we wanted to check the numbers up to 1,000,000 instead of only up to 1,000 then the solution would take much longer to run. This solution is O(n) which isn’t bad, but isn’t great either. We check the increase in runtime by simply modifying the argument in our benchmark function.
func BenchmarkBruteForce(b *testing.B) {
for i := 0; i < b.N; i++ {
bruteForce(1000000)
}
}
Now we will have different timing and benchmark information.
go test -bench .
BenchmarkBruteForce-4 3 441286594 ns/op
So by increasing the numbers we have to check by a factor of 1000, we now have a runtime of 441,286,594 ns/op instead of 227,761 ns/op, which is an increase of about 1900x. Not good. For more on asymptotic analysis of runtime, check out the Wikipedia article on Big O Notation.
Performance upgrades
There are some options to improve the performance, like splitting the range of numbers into parts and spawning multiple worker threads to check each part, thereby parallelizing the work. This is a lot of complexity though, especially when you want to make sure that ranges checked don’t overlap, managing potential shared state, and so on. If we think a bit more about the problem, there is a better way.
We want to sum all the multiples of 3 or 5 less than 1000. We can think about the sequence of multiples of 3 as (3, 6, 9, 12, 15, …, 999), which is the same as 3 * (1, 2, 3, 4, 5, …, 333). We can do the same for the case of multiples of 5. The benefit of considering the problem in this way is that the list of numbers has a closed-form solution (i.e., a formula) for calculating the sum.
Such a sequence, where the difference between each number is constant, is called a finite arithmetic progression or finite arithmetic sequence and the sum of a finite arithmetic progression is called a finite arithmetic series. The formula for the sum is 1/2 * n * (a_1 + a_n). where n is the number of terms being added, a_1 is the first element in the sequence, and a_n is the last element in the sequence.
From our example for multiples of 3, we know that a_1 = 1 and we know that a_n = floor(999/3) = 333 and we also know that the total number of elements in the sequence will be n = floor(999/3) = 333 = a_n. So for our purposes, the sum of our sequences is equal to n * (n + 1) * 0.5. We can make a small helper function to calculate this for us.
func arithSum(n float64) float64 {
return (n * (n + 1)) / 2
}
Now we can simply compute the sum of the arithmetic sequence for all the multiples of 3 and 5 without iterating through anything at all. Since we already know the answers to the questions from the brute force case, we can also write the appropriate tests.
func TestArithSeq(t *testing.T) {
if arithSeq(9) != 23 {
t.Fatal("The sum of values from 1 to 10 which are divisible by 5 and 3 should be 23")
}
if arithSeq(999) != 233168 {
t.Fatal("The sum of values from 1 to 1000 which are divisible by 5 and 3 should be 233168")
}
}
For the corresponding function:
func arithSeq(limit float64) int {
threes := 3 * arithSum(math.Floor((limit)/3))
fives := 5 * arithSum(math.Floor((limit)/5))
return int(threes + fives)
}
But there is a problem because not all of our tests pass.
go test -v
=== RUN TestArithSeq
--- FAIL: TestArithSeq (0.00s)
0001_test.go:10: The sum of values from 1 to 1000 which are divisible by 5 and 3 should be 233168
=== RUN TestBruteForce
--- PASS: TestBruteForce (0.00s)
FAIL
exit status 1
What is the problem? Why did the test for n = 9 pass but the test for n = 999 fail? The answer starts at 15, which is divisible by both 5 and 3. Because we summed all the multiple of 5, and all the multiples of 3, we also summed all the multiples of 15. In other words, all the multiples of 15 are double counted because we need them to be summed as a multiple of 5, or as a multiple of 3, but not both. This a common problem in combinatorics, the study of finite or countable discrete structures, and the answer is easily described by the inclusion-exclusion principle.
For some set A, like the set of all multiples of 3, and some set B, like the set of all multiples of 5, then when we add them we have to subtract their interaction because it is counted twice. In our case, this intersection is the set of all multiples of 15. So we can get the correct solution by simply removing the sum of all multiples of 15 from our total.
func arithSeq(limit float64) int {
threes := 3 * arithSum(math.Floor(limit-/3))
fives := 5 * arithSum(math.Floor(limit/5))
fifteens := 15 * arithSum(math.Floor(limit/15))
return int(threes + fives - fifteens)
}
Now all of our tests will pass.
go test -v
=== RUN TestArithSeq
--- PASS: TestArithSeq (0.00s)
=== RUN TestBruteForce
--- PASS: TestBruteForce (0.00s)
PASS
Ok, great. Now we have another way of solving the problem, but what was the actual speed benefit? It’s pretty dramatic. First, we need to add a benchmark function to our _test.go file:
func BenchmarkArithSeq(b *testing.B) {
for i := 0; i < b.N; i++ {
arithSeq(999)
}
}
Now we can see the difference.
go test -bench .
BenchmarkBruteForce-4 10000 227689 ns/op
BenchmarkArithSeq-4 100000000 21.8 ns/op
PASS
Both of those are for the specified Project Euler problem of summing only the multiples below 1000. In this case, the solution using the arithmetic series approach is about 10,000 times faster than the brute-force approach.
Better still, because the arithmetic series approach requires the same number of operations regardless of the input size, it doesn’t matter if we want to do the summation for multiples up to 1000 or 1,000,000 it will always take the same amount of processing time. So the arithmetic series approach is constant time (also denoted O(1)). Much better.
There are probably other interesting ways to solve this problem, like finding the prime factors of all the numbers less than n to see if 3 or 5 is one of the factors, but I think this is enough for now.