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

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.

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:

$ \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{array} M &=& 667 + 500 - 166 - 133 - 100 - 33 \\ M &=& 735 $