Project Euler Solution 1: Multiples of 3 or 5

There are many sources of interesting programming challenges available. One I have enjoyed in the past is Project Euler. In this series of posts I will solve these problems.

As this is the first post in a planned series, I will give a bit more background. Programming challenges are readily available in different styles. There is for instance Code Wars, Advent of Code and likely many others. It depends a bit on the taste of the problems that one wants to solve. I like Project Euler because the solution is always an integer and one can check them on the website. They are always mathematical problems where one has to compute something. In the beginning one can use a brute force approach and always succeed. But when one progresses through the problems, they will become impossible to solve with brute force in a decent amount of time.

In this article I will take a look at Problem 1: Multiples of 3 or 5:

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.

I will solve these problems in Python as it is the programming language that I use daily and also it is quite easy to read.

The fun with these problems is to do them yourself. So all these blog articles are going to be spoilers. I don't want to take the fun away from you, so please have a try at the problems yourself first if you are into this sort of thing. If you are not sure about the whole idea, then you might enjoy these blog posts. And of course you can always read here and do the next problems yourself.

Solution

In a first naive way we can just go ahead and iterate over all numbers between 0 and 1000. Python's range is exclusive at the end, so we need 1000 there. We then use the modulo operator % to check whether the number is divisible by 3 or 5. If so, we add it to the sum. This is the code:

def solution_naive() -> int:
    sum_of_multiples = 0
    for i in range(1000):
        if i % 3 == 0 or i % 5 == 0:
            sum_of_multiples += i
    return sum_of_multiples

This works and yields 233,168 as the result. One iteration takes 65 µs, which seems super fast. I took the timings on an Intel Core i7-8565U CPU which a maximum turbo boost of 4.6 GHz, just for reference.

We can also try a different approach, we can create a set with all the multiples of 3 and another set of all the multiples of 5. Then we merge the set with the set union |. As the final step we sum all these numbers.

def solution_set() -> int:
    multiples_of_3 = {i * 3 for i in range(1, 999 // 3 + 1)}
    multiples_of_5 = {i * 5 for i in range(1, 999 // 5 + 1)}
    all_multiples = multiples_of_3 | multiples_of_5
    return sum(all_multiples)

This yields the same result and takes 28 µs. This is already more than twice as fast as the naive version.

But we can do better than that for this problem. There is a closed form equation for such series. We can use that to directly compute the sum of all multiples up to a given ceiling. The thing that we have to keep in mind is that when we add the sum of all multiples of 3 and also the sum of all multiples of 5, we end up counting the multiples of 15 twice! Therefore we need to subtract them once again.

Combining this equation and the insight with the 15, we get this code:

def sum_of_natural_numbers(end: int, step: int) -> int:
    count = end // step + 1
    return count * (count - 1) * step // 2


def solution_closed_form() -> int:
    return (
        sum_of_natural_numbers(999, 3)
        + sum_of_natural_numbers(999, 5)
        - sum_of_natural_numbers(999, 15)
    )

Here my measurement script gives 460 ns, which is virtually nothing for a Python function call. And it is not surprising. The complexity of the first two solutions is O(N) where N is the ceiling of 1000 that is set in the problem. Depending on the set implementation, it could actually also be O(N log N), which would be worse. The last solution is O(1), so no matter what the ceiling is, it is always done with the same number of steps.