Project Euler | Problem 1 Solution

Multiples of 3 or 5 Solution

24 September 2023

Statement

( The original statement can be found here )

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.

Solution

Project Euler Problem 1 involves finding the sum of all multiples of 3 and 5 below 1000. While you could brute force this problem by looping through numbers and checking the criteria, there's a more elegant mathematical solution. The aim of this blog post is to explore how to tackle this problem efficiently.

To solve this problem, we need to sum two sequences: one comprising multiples of 3 \(\rightarrow\) (3, 6, 9, 12, ...) and another comprising multiples of 5 \(\rightarrow\) (5, 10, 15, 20, ...). It's important to note that sometimes these sequences overlap with common numbers, such as 15, 30, 45, which should be subtracted from the total sum to avoid double counting.

Let's express the sum of multiples of 3 mathematically:

\((1 \times 3) + (2 \times 3) + (3 \times 3) + (4 \times 3) + ... +(n \times 3) = (1 + 2 + 3 + 4 +...+n) \times 3 \) = \(\frac{n(n + 1)}{2} \times 3\)

We can apply the same approach to the sequence of multiples of 5:

\((1 \times 5) + (2 \times 5) + (3 \times 5) + (4 \times 5) + ... +(n \times 5) = (1 + 2 + 3 + 4 +...+n) \times 5 \) = \(\frac{n(n + 1)}{2} \times 5\)

Here, 'n' represents the length of the sequence, which can be calculated as \(\lfloor \frac{999}{3} \rfloor\) and \(\lfloor \frac{999}{5} \rfloor\) where \(floor(x) = \lfloor x \rfloor \).

To account for the overlapping multiples of 3 and 5, we can identify their lowest common multiple (LCM), which is 15. This means that every 15th number will be a multiple of both 3 and 5. We can use the same process to find the sum of all multiples of 15 and subtract it from the final result.

Now, let's take a look at how to implement this solution in C++:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int total = 0;
    int n3 = floor(999.0 / 3);
    int n5 = floor(999.0 / 5);
    int n15 = floor(999.0 / 15);
    total += (n3 * (n3 + 1) / 2) * 3;
    total += (n5 * (n5 + 1) / 2) * 5;
    total -= (n15 * (n15 + 1) / 2) * 15;
    cout << total << endl;
    return 0;
}

This solution operates with a time and space complexity of \(O(1)\).