Project Euler/1

This is problem 1 on Project Euler: https://projecteuler.net/problem=1

Overview of the Problem

Question

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.

Note that, if you've ever seen the fizz-buzz problem in computer science, this is the number-theory version.

Why this problem

Naturally, the very first Project Euler question will raise the question - why this one? Project Euler is a fantastic, complex, and difficult site involving many beautiful aspects of number theory. So why begin the journey at this problem in particular?

This problem shares many similarities, algorithm-wise, with the Sieve of Eratosthenes (at least, that's the idea.) With the Sieve of Eratosthenes, you begin with the smallest primes and work your way up by finding multiples of these primes and crossing them off the list of potential primes. In essence, this is the first question because it is the most fundamental operation of the most fundamental algorithm in number theory.

Solution

We can come up with a simple solution that uses a bit vector to represent integers, or we can toss numbers into a set (which, under the hood, is likely using a similar representation anyway). Given our maximum N, and our two numbers a and b, we can allocate a boolean array with that many integers, set them all to false, then walk through the list in intervals of 3 and 5, flipping the booleans to true as we go.

Going Deeper: An Example

It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,001 - and to do so without explicitly enumerating them with a computer.

To do this, we can express the problem in set notation. We have three sets, A, B, C, containing multiples of 3, 4, and 5, respectively. In set theory language, we wish to find

$(A\bigcup B)\backslash C$

We can start by counting the sets A and B, as well as accounting for $A\bigcap B$ (numbers that are multiples of both a and b).

Next, we can count $A\bigcap C$ and $B\bigcap C$, which are the multiples of a and b that we counted that we should not have because they are multiples of c.

Finally, we cannot forget $A\bigcap B\bigcap C$ - numbers that have a, b, and c as multiples. This case is a bit tricky. Any item that is in $A\bigcap B\bigcap C$ has already been removed - twice. The first time was when it was removed because it was in $A\bigcap C$, and the second time was when it was removed because it was in $B\bigcap C$. Therefore, we must add each of these items back in, to account for the double-removal and ensure these items are only removed once.

So we will add the items in $A\bigcap B\bigcap C$ back into the final set.

Visually representing A, B, and C with a Venn diagram,

To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:

${\mbox{card}}(A)={\mbox{floor}}\left({\frac {2001}{3}}\right)=667$

${\mbox{card}}(B)={\mbox{floor}}\left({\frac {2001}{4}}\right)=500$

Next, we subtract the duplicates (numbers with both A and B as factors):

${\mbox{card}}(A\bigcap B)={\mbox{floor}}\left({\frac {2001}{3\cdot 4}}\right)=166$

Now subtract integers that have both a and c as multiples, or b and c as multiples:

${\mbox{card}}(A\bigcap C)={\mbox{floor}}\left({\frac {2001}{3\cdot 5}}\right)=133$

${\mbox{card}}(B\bigcap C)={\mbox{floor}}\left({\frac {2001}{4\cdot 5}}\right)=100$

And last but not least, those numbers with a, b, and c as factors were just removed twice, so we add them back in once:

${\mbox{card}}(A\bigcap B\bigcap C)={\mbox{floor}}\left({\frac {2001}{3\cdot 4\cdot 5}}\right)=33$

This gives a total number of multiples M below N with a or b as a factor, but not c:

$M={\mbox{floor}}\left({\frac {N}{a}}\right)+{\mbox{floor}}\left({\frac {N}{b}}\right)-{\mbox{floor}}\left({\frac {N}{ab}}\right)-{\mbox{floor}}\left({\frac {N}{ac}}\right)-{\mbox{floor}}\left({\frac {N}{bc}}\right)+{\mbox{floor}}\left({\frac {N}{abc}}\right)$

in our specific case,

${\begin{aligned}M&=&667+500-166-133-100+33\\M&=&801\end{aligned}}$