Project Euler #1 - Multiples of 3 or 5

My solution to Project Euler problem #1, "Multiples of 3 or 5."

author: Max Niederman, published: 2022-03-20

The first Project Euler problem reads as follows:

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.

Trivial Solution

The simplest solution is to just iterate over all numbers from 0 to 1000, check if they are multiples of 3 or 5, and sum those that are.

let sum = 0;
for i in 0..1000 {
    if i % 3 == 0 || i % 5 == 0 {
        sum += i;
    }
}

or in a more functional style:

let sum = (0..1000).filter(|i| i % 3 == 0 || i % 5 == 0).sum();

This has a runtime complexity of , where is the upper bound of the range. More than fast enough for small like 1000, but we can do better.

Constant-Time Solution

The crucial insight which allows us to solve the problem in constant time is the fact that the sum is equal to the sum of the multiples of 3 plus the sum of the multiples of 5 minus the sum of multiples of both (i.e. multiples of 15).

We can then use the formula for the sum of the first natural numbers, , to find the sum of all multiples of a number less than :

Now we simply substitute the numbers given by the problem:

This gives us our final answer of without the need for a single line of code. If you were really dedicated, you could even calculate this on paper!