Back to Project Euler

 Next Problem

Problem 1: Multiples of 3 and 5

Solution

The first thing to note is that the problem specifically asks for the numbers below 1000, so our cap is 999.

Nothing is stopping us from simply checking every natural number up to 999 to see if it's a multiple of 3 or 5. This would take \(O(n)\) time, which, for those unacquainted with algorithmic terminology, means linear time: if \(n\) is the maximum value we need to check, \(O(n)\) means that as \(n\) becomes large, we expect the number of computations performed to converge to some multiple of \(n\). Here \(n\) is only 999, so while it would take forever to write out all the multiples of 3 or 5 by hand, a machine could do it almost instantly.

There's a better way, however. We can find the answer in constant time, also known as \(O(1)\) time. This depends on two tricks: triangular numbers and the inclusion-exclusion principle.

According to legend, a young Carl Friedrich Gauss was once asked by his teacher to sum all the natural numbers between 1 and 100. His teacher expected this to take a long time, but Gauss instantly wrote down the correct answer: 5050. When pressed, Gauss explained his reasoning: because \(1 + 100 = 101\), and \(2 + 99 = 101\), and \(3 + 98 = 101\), and so forth, all the way up to \(50 + 51 = 101\). Hence there were 50 pairs of numbers that summed to 101, so the answer was \(50 \times 101 = 5050\). Upon completion of this proof, Gauss threw down his chalk and pronounced "There it lies."

Whether or not this anecdote is factual — American Scientist is unconvinced — the fact remains that \(1 + 2 + 3 + \ldots + n = \frac{n(n+1)}2\) for any positive integer \(n\). The result of this formula is called the \(n\)-th triangular number.

The inclusion-exclusion principle states that if \(A\) and \(B\) are two finite sets, then the number of elements in their union can be expressed as \(|A \cup B| = |A| + |B| - |A \cap B|\). If \(A\) and \(B\) are sets of real numbers, we can state a similar relation regarding the sums of their elements: \(\sum_{x \in A \cup B} x = \sum_{x \in A} x + \sum_{x \in B} x - \sum_{x \in A \cap B} x\). Let \(A\) be the multiples of 3 up to \(n\), and let \(B\) be the multiples of 5 up to \(n\). Their intersection, \(A \cap B\), is the multiples of 15 up to \(n\). Thus, we can solve the problem by summing the multiples of 3, adding the sum of the multiples of 5, and subtracting the sum of the multiples of 15.

For any \(k\), we can calculate the sum of the multiples of \(k\) up to \(n\) as follows (here \(\lfloor n/k \rfloor\) means we divide \(n\) by \(k\) and discard the remainder):

\[ k + 2k + 3k + \ldots + \lfloor n/k \rfloor k = k (1 + 2 + 3 + \ldots + \lfloor n/k \rfloor) = k \frac{\lfloor n/k \rfloor(\lfloor n/k \rfloor+1)}2 \]

Therefore, the formula to solve this problem for general \(n\) is

\[ 3 \frac{\lfloor n/3 \rfloor(\lfloor n/3 \rfloor+1)}2 + 5 \frac{\lfloor n/5 \rfloor(\lfloor n/5 \rfloor+1)}2 - 15 \frac{\lfloor n/15 \rfloor(\lfloor n/15 \rfloor+1)}2. \]

Now all that's left is to take \(n=999\) and plug it into a calculator.

Could we have done this the naïve way? Sure. Again, our given value of \(n\) is extremely generous — but later problems will take off the guard rails. Taking the longer route, which solves not just this problem but all others like it, is far more in the spirit of Project Euler.

Python Code

def p1(n=999):
	n3, n5, n15 = n // 3, n // 5, n // 15
	term3 = 3 * n3 * (n3 + 1) // 2
	term5 = 5 * n5 * (n5 + 1) // 2
	term15 = 15 * n15 * (n15 + 1) // 2
	return term3 + term5 - term15

 Next Problem

Back to Project Euler