Project Euler — Problem 1

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.

Solution

The most brute force way to approach this problem is to iterate over every number from 1 through 999, that is, \(n - 1\) and check if it is a multiple of 3 or 5 using the modulo operator. If so add it to the total sum. This is a simple and correct approach and will definitely give correct answers.

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

However, this brute force approach is very slow as it goes through literally \(n\) numbers. Therefore, the runtime of this algorithm is linear or in other words, the complexity of this algorithm is \(O\big(n\big)\).

A smarter approach would be to not go through all the numbers, but instead, add the multiples of 3 and 5. Then reduce, from the total sum, the summation of multiples of 15 as it got added twice.

def sumOfMultiples(x, limit):
    Sum = 0
    for i in range(x, 1000, x):
        Sum += i
    return Sum

print(sumOfMultiples(3, 1000) + sumOfMultiples(5, 1000)
      - sumOfMultiples(15, 1000))

This approach, in practice, is faster than the previous brute force approach as we are churning fewer numbers but theoretically, it’s runtime is still linear.

As it turns out, multiples of any number are always in an Arithmetic Progression. We can utilize this fact to attain constant runtime.

In this problem, we are dealing with a special case where \(a_1\) or initial term and \(d\) or the common difference for the arithmetic progression are same.

\[ \begin{equation} \label{a} \tag{1} a_1 = d \end{equation} \]

The n^th term or \(a_n\) of the arithmetic progression then is as follows.

\[ \begin{equation} \begin{split} a_n & = a_1 + \big( n - 1 \big) \cdot d \\ \end{split} \end{equation} \]

But as mentioned earlier \(\eqref{a}\), the common difference is same as the initial term. So, we can substitute the value to get \(a_n\) as \(n\) times the inital term.

\[ \begin{equation} \begin{split} a_n & = a_1 + \big(n - 1 \big) \cdot a_1 \quad \eqref{a} \\ & = a_1 \cdot n \end{split} \end{equation} \label{b} \tag{2} \]

The summation of \(n\) terms of arithmetic progression is given by the following equation.

\[ \begin{equation} \begin{split} S_n & = \bigg(\frac{n}{2}\bigg) \cdot \big(a_1 + a_n\big) \\ \end{split} \end{equation} \]

We can substitute the value of \(a_n\) from \(\eqref{b}\) in the above equation to get our final formula for the sum of multiples.

\[ \begin{equation} \begin{split} S_n & = \bigg(\frac{n}{2}\bigg) \cdot \big(a_1 + \big(a_1 \cdot n \big) \big) \quad \eqref{b} \\ & = \Bigg(\frac{a_1 \cdot n \cdot \big( n + 1 \big)}{2} \Bigg) \end{split} \end{equation} \]

The above formula can now be used to calculate the sum of multiples in constant time as the execution does not depend upon the size of the number. And this is how we can theoretically achieve the runtime complexity of \(O(1)\).

Problem

Solution

Links