Project Euler #1: Multiples of 3 or 5

Project Euler is what I would consider a hidden gem among problem-solving websites. Although it was launched in October 2001, it is not as well-known as other popular websites like LeetCode, HackerRank, or Codeforces. However, there is a good reason for this - Project Euler focuses on a unique set of mathematical challenges rather than algorithms and data structures. Unlike other websites, it does not require you to pass test cases or meet specific time or memory constraints. Additionally, it does not restrict the programming language that you can use to solve problems. In fact, you can even solve the problems using a pen and paper if you prefer.

This is the first of many posts dedicated to solving challenges on Project Euler. According to the website’s guidelines, I’m allowed to share solutions to only the first 100 problems, as long as I don’t simply post the solution. Instead, I will discuss what I learnt while solving each problem. Stay tuned for more posts on this series!

Enough talk! Here we go with the first 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.

The first problem seems simple enough. All we have to do is to calculate the sum of multiples of 3 or 5 that are below 1000. Remember that ‘below 1000’ means < 1000, and not <= 1000. Taking that into consideration, the solution will look like:

sum = 0
for i in range(3, 1000):
    if(i % 3 == 0 or i % 5 == 0):
        sum = sum + i
print(sum)

A simple solution for a simple question (and we get the right answer too!). But can we do better? As engineers, it is incumbent on us to make our solutions more efficient. The time complexity for this solution is O(n), which means the time taken to compute the solution will increase linearly with the input size ‘n’. So if it takes x seconds to compute the solution for n = 1000, it will take 10x seconds for n = 10000. Now what if ‘n’ was a gazillion bazillion?

If we look closely at the problem, all we’re being asked to is calculate the sum of a list of numbers. And this list of numbers has a characteristic - they all need to be multiples of either 3 or 5. The obvious pattern that emerges here is the Arithmetic Progression. Any two consequent multiples of a number will always have an absolute difference that is equal to the number itself. Let’s list down the multiples of 3 and 5 to observe this:

Multiples of 3 - 3, 6, 9, 12, 15... ∞
Multiples of 5 - 5, 10, 15, 20, 25.. ∞

We can utilize this fact to our advantage by using one of the formulas that the mathematical gods have bestowed upon us - the summation of an arithmetic progression:

\[S_n = \sum_{i=1}^{n} a_i = \frac{n}{2} \cdot (a_1 + a_n) \]

Here, \(a_1\) represents the first term in the AP, and \(a_n\) represents the \(n\)th term in the AP, where \(n\) is equal to the number of terms in the progression. In our case, we don’t know how many multiples of 3 or 5 there are below 1000. Lucky for us, there’s a formula for that too:

\[n = \frac{a_n - a_1}{d} + 1\]

Here, \(d\) is the difference between any two consecutive numbers in the progression. For this problem, \(d\) would be the number whose multiples we’ll be summing up.

Plugging this in the summation formula, we get:

\[S_n = \sum_{i=1}^{n} a_i = (\frac{a_n - a_1}{d} + 1) \cdot \frac{1}{2} \cdot (a_1 + a_n) \]

That’s a fairly complex equation and I wouldn’t want the computer to work it out every time. So let’s make its job easier and work it out ourselves. Eventually, we’ll come up with the following equation:

\[\frac{a_n^2 - a_1^2 + a_1 \cdot d + a_n \cdot d}{2 \cdot d} \]

There is however, one more problem - we don’t know what \(a_n\) can be for really large values of \(n\). For trivial numbers like 3 or 5, sure it’s easy. You can probably do the math in your head. But what about those random prime numbers in the millions or billions. That won’t be as easy. Therefore, for a given number, we need a formula to calculate the multiple that is closest to \(n\) while also being \(\leq n\).

We can determine this by performing an integer division of \(n\) by the number (to yield the quotient), followed by multiplying the quotient with the number again. This will give us what we want. Therefore,

\[a_n = (n // d) \cdot d\]

(Here, // represents integer division)

Now, I could plug this value into the equation that we worked out above, but that will make things look a little messy. Since we have the equations we need, let us have dedicated functions to calculate them on the fly.

def calculate_closest_multiple_below_n(n, d):
    return (n // d) * d

def calculate_sum_of_series(a1, an, d):
    return (an**2 - a1**2 + a1*d + an*d) // (2 * d)

a_n3 = calculate_closest_multiple_below_n(999, 3)
a_n5 = calculate_closest_multiple_below_n(999, 5)
a_n15 = calculate_closest_multiple_below_n(999, 15)

sum_3 = calculate_sum_of_series(3, a_n3, 3)
sum_5 = calculate_sum_of_series(5, a_n5, 5)
sum_15 = calculate_sum_of_series(15, a_n15, 15)

# When adding up the multiples of 3 and 5, we count some of the numbers twice because they are common multiples of both 3 and 5.
# These numbers (15, 30, 45...) are the multiples of 15. 
# So we have to subtract the summation of multiples of 15 to get the correct answer.
print(sum_3 + sum_5 - sum_15)

And would you look at that? O(n) reduced to O(1). Don’t you love to see it?