Project Euler #1: Multiples of 3 or 5

Problem statement:

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. In the case of HackerRank, we have to find the sum of multiples below N.

Links: Project Euler, HackerRank

#1 Naive Solution:

The straightforward solution will be to iterate through all numbers and add numbers that are divisible by 3 or 5. Please refer to the below code. The code here will take $O(n)$ . This seems okay for the Project Euler constraint where $N$ is $1000$ . However, this code will result in a TLE for the HackerRank problem where $N$ can be up to $10^9$ .

def slow_sum_of_multiples_of_3_or_5(till: int) -> int:
    sum_of_multiples = 0
    for num in range(till):
        if num % 3 == 0 or num % 5 == 0:
            sum_of_multiples += num
    return sum_of_multiples

#2 Pythonic Naive Solution:

We can make the above solution more compact using python's list comprehension. This will not make the code faster.

def pythonic_sum_of_multiples_of_3_or_5(till: int) -> int:
    return sum(x for x in range(till) if x % 3 == 0 or x % 5 == 0)

#3 Using Arithmetic Progression:

Multiples can be considered as Arithmetic Progression where the common difference is the divisor.
We have direct formula to calculate addition of arithmetic progression:

The code for this will look something like this:

def sum_of_arithmetic_progression(first: int, last: int, no_of_elements: int) -> int:
    return (first + last) * no_of_elements // 2

Now we need to add the sum of all multiples of 3 and all multiples of 5.

Multiples of 3: $3, 6, 9, 12, \mathbf{15}, 18, 21, 24, 27, \mathbf{30}, ...$

Multiples of 5: $5, 10, \mathbf{15}, 20, 25, \mathbf{30}, 35, 40, ...$

As you can see above, if we do add the multiples, we will be getting additional multiples of 15. Because some numbers are divisible by both 3 and 5 and we will be adding them twice. So to get the correct addition we need to subtract multiples of 15 (LCM of 3 and 5 i.e. numbers that are divisible by both 3 and 5) from the addition of multiples of 3 and multiples of 5. The formula will look something like this:

Please see the complete code below. This code will take consistent time for any given $N$ . So, the time complexity for this will be $O(1)$ .

def fast_sum_of_multiples_of_3_or_5(till: int) -> int:
    till -= 1  # We don't want to include `till` in our summation.

    def sum_of_multiples(of: int) -> int:
        """ Short hand function to return sum of arithmetic progression. """
        no_of_elements_divisible = till // of
        last_divisible = no_of_elements_divisible * of
        return sum_of_arithmetic_progression(
            first=of, last=last_divisible, no_of_elements=no_of_elements_divisible)

    return sum_of_multiples(of=3) + sum_of_multiples(of=5) - sum_of_multiples(of=15)


def sum_of_arithmetic_progression(first: int, last: int, no_of_elements: int) -> int:
    return (first + last) * no_of_elements // 2

Thank you for reading.