Project Euler is a math and programming challenge website containing a series of problems of increasing difficulty. The problems are intended to be too large to be solved with pen and paper. When I started working on these problems in 2013, my only experience with programming had been making plots in Mathematica and some introductory C. I found that I enjoyed working on Project Euler way more than studying for midterms. Many hours of "productive" procrastination and lost sleep ensued.

Unlike most university coursework, you are supposed to figure out how to solve Project Euler problems on your own. Problems are solved by laying on a couch with a pad of paper and visualizing the problem, not by frantically flipping through your class notes or textbook to find a worked example. Inventing a solution and then implementing it in code requires creativity as well as analytical and programming skills; it's hard and fun.

Over the years, I've used Project Euler to teach myself C++, Haskell, Python, and Scheme. I've also dabbled with solutions in Ada, Common Lisp, Fortran, Prolog, and bc.

Project Euler problems typically have an obvious (naive, or brute-force) solution and one or more sophisticated solutions that make use of mathematical shortcuts to speed up the search for the correct answer. Seemingly simple problems are often only tractable with the help of some theorem. The first problem illustrates this beautifully.

Problem 1: Multiples of 3 and 5

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 naive solution is simple; loop over numbers from 1 to 999 and check each one for divisibility by 3 or by 5, adding divisible numbers to the sum. In pseudocode:

sum = 0
i = 1

while i < 1000 do
    if 3 dividies i or 5 divides i do
    sum = sum + i
    end if
    i = i + 1
end while

print sum

The above solution is fine for solving the problem as specified, but I like to solve the most general case. We can generalize the problem slightly by summing numbers divisible by $a$ or $b$ below some $n$. Problem 1 as specified becomes a special case where $a = 3$, $b = 5$, $n = 1000$.

a = 3
b = 5
n = 1000

sum = 0
i = 1

while i < n do
    if a dividies i or b divides i do
    sum = sum + i
    end if
    i = i + 1
end while

print sum

This approach works fine for small $n$ on the order of 1000, but if we wanted to try $n = 10^9$, it would take a million times longer. It turns out that with the help of a little number theory, we can calculate the sum of multiples of a number in a fixed amount of time, independent of the value $n$.¹

$$\sum^n_{i = 1} i = \frac{n (n + 1)}{2}$$

We call this the $n^{th}$ triangular number $T_n$. Using this definition, we can show that the sum of all multiples of 3 below $n$ is

$$3 T_{\left\lfloor (n - 1)/3 \right\rfloor}$$

likewise, the sum of multiples of 5 below $n$ is

$$5 T_{\left\lfloor (n - 1)/5 \right\rfloor}$$

We can't just add these sums together because multiples of 15 (which are multiples of 3 and 5) would be double-counted in our sum. To account for double counting, we add the sums of multiples of 3 or 5 and subtract the sum of multiples of 15:

$$3 T_{\left\lfloor (n - 1)/3 \right\rfloor} + 5 T_{\left\lfloor (n - 1)/5 \right\rfloor} - 15 T_{\left\lfloor (n - 1)/15 \right\rfloor}$$

This yields the following pseudocode:

function triangle-number(n) is
    return (n * (n + 1)) / 2
end function

function sum-multiples-below(x, n) is
    return x * triangle-number (floor ((n - 1) / x))
end function

n = 1000
sum = sum-multiples-below(3, n)
    + sum-multiples-below(5, n)
    - sum-multiples-below(15, n)
print sum

Why stop generalizing here? We might be interested in the sum of multiples of $a$ or $b$ or more generally, the sum of numbers divisible by any number in some set $D$.

In the first case, we need to recognize that $a T_{\left\lfloor n/a \right\rfloor} + b T_{\left\lfloor n/b \right\rfloor}$ double counts multiples of the least common multiple of $a$ and $b$, not necessarily their product. The sum of multiples of $a$ or $b$ less than $n$ is then:

$$a T_{\left\lfloor n/a \right\rfloor} + b T_{\left\lfloor n/a \right\rfloor} - LCM(a, b)~ T_{\left\lfloor n/LCM(a, b) \right\rfloor}$$

In the latter more general case, we consider the least common multiples of subsets of the power set of $D$. To account for double counting, the sums of multiples of the LCM of subsets with odd cardinality are added to the sum, and the sums of multiples of the LCM of subsets with even cardinality are subtracted from the sum. In pseudocode:

function sum-set-multiples-below(D, n) is
    sum = 0
    for subset in power-set(D) do
        lcm = least-common-multiple(subset)
        if size(subset) is even do
            sum = sum - sum-multiples-below(lcm, n)
        else do
            sum = sum + sum-multiples-below(lcm, n)
        end if
    end for
    return sum
end function

n = 1000
D = {3, 5}
print sum-set-multiples-below(D, n)

An implementation of this pseudocode in Haskell is available here.

My Other Solutions

I've recently started migrating my Project Euler solutions from various external drives to a Gitlab repostory. I've been accumulating these solutions since I first started learning programming, so they don't all reflect my current best practises. I hope you will enjoy them anyway.