About

Project Euler is a great way to solve some fun maths with the computer. Computers are as fundamental a tool for the modern mathematician, as the square and compass were to the Ancient Greeks. Try out some problems!

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

There are two ways to solve this problem.

Loops

The simpler and more flexible way loops through all numbers below 1000. At each number we check if the number is divisible by any of our multiples, and if we find any match, add that number to an accumulating sum.

multiples = [3, 5]
ubound = 1000

def sum_multiples(multiples: Multiples, ubound: int) -> int:
    sum = 0
    for i in range(ubound):
        for m in multiples:
            if (i % m == 0):
                sum += i
                break
    return sum

This is nice since it is easy to understand and expand. You can add any number multiples to the list and change the upper bound.

Triangular Numbers

While not as flexible or readable as loops, we can optimize away almost all of our calculations with some set theory.

Pick a number, say 4. Multiples of 4 will be 4, 8, 12, 16,... . If we rewrite these multiples as a factor of 4 we will get 4, 8, 12, 16, ... = 4(1, 2, 3, 4, ...). This is true for any number and it's multiples. So, if each multiple forms a set, then the union of these sets will be the collection of all number's we want to sum. To make it even simpler, since addition is a linear operator we can just act on the set's sum for each multiple.

So in maths

A \cup B = A + B - AB \\ M_n^u = n(1 + 2 + ... + q),\ where\ n*q < u \\

Now we have an equation for finding the union of the multiple's sums, and an equation for finding each multiple's sum. Since $q$ is just the last multiple below our upper bound $(999)$ , is is equivalent to the quotient of dividing the upper bound by our modulus.

So our sum can be optimized down to a napkin problem

Ans = M_3^{999} + M_5^{999} -M_{15}^{999}

Or in python

def triangle_sum(ubound: int) -> int:
    return ( ubound * (ubound + 1) ) // 2 # Good conditioning

def get_quotient(ubound: int, modulus: int):
    ubound -= 1 # Our upper bound is exclusive
    return ubound // modulus

def optimized_sum(ubound: int) -> int:
    M3  =  3 * triangle_sum(get_quotient(ubound,  3))
    M5  =  5 * triangle_sum(get_quotient(ubound,  5))
    M15 = 15 * triangle_sum(get_quotient(ubound, 15))
    return M3 + M5 - M15

This format can handle very large upper bounds, limited only by either the type system of the language (u32 vs u64) or the hand computing power of the interested party.

But, due to distributive nature of unions this method will scale poorly for sums of many multiples. Indeed for $m$ multiples, the number of terms $t$ is

t = 2^m - 1 = \sum^n_{i = 1} \begin{pmatrix}m \\ i\end{pmatrix}

I'll leave this as an exercise for the reader. For more details see the binomial theorem and triangle numbers.

Some Code

Checkout my python implementation on github