sum(x for x in 1:999 if (x % 3 == 0) || (x % 5 == 0))233168Multiples of 3 or 5
Problem 1
Problem definition
If we list all the natural numbers below \(10\) that are multiplies of \(3\) or \(5\), we get \(3, 5, 6, \text{and } 9\). The sum of these multiples is \(23\).
Find the sum of all the multiples of \(3\) or \(5\) below \(1000\).
Solution
Analytical Solution
Let \(A \in \mathbb{N}\) be the set that contains all the natural numbers in the domain \([1, 1000)\) that are multiples of \(3\).
\[\begin{align} A = 3, 6, 9, 12, 15, \cdots, 999 \end{align}\]
Let \(B \in \mathbb{N}\) be the set that contains the numbers in the same domain as \(A\) but that are multiples of \(5\).
\[\begin{align} B = 5, 10, 15, 20, 25, \cdots, 995 \end{align}\]
Essentially what we are looking for here is the sum of all the elements contained in \(A \cup B\).
By the inclusion-exculsion principle, recall that
\[\begin{align} A \cup B = A + B - A \cap B \end{align}\]
so we need to find the sum of the elements contained in \(A\), \(B\), and the set \(C = A \cap B\) which is the set of all the numbers which are multiples of \(15\).
\[\begin{align} C = 15, 30, 45, 60, \cdots, 990 \end{align}\]
For this we can use the formulas for Arithmetic Progression.
\[\begin{align} \sum A = n \left(\frac{a_1 + a_n}{2}\right) \end{align}\]
where \(n\) is the number of terms in the sequence, \(a_1\) is the first term and \(a_n\) is the last term. We don’t know what how many terms there are in the sequence so we can also use the nth term formula
\[\begin{align} a_n = a_1 + \left(n - 1\right)d \end{align}\]
where \(d\) is the value being added to \(a_{n-1}\) to obtain \(a_n\).
Let us compute these sums for \(A, B, C\)
A
the last term in the sequence is \(999\) thus,
\[\begin{align} 999 &= 3 + \left(n - 1\right)3\\ 999 &= 3n\\ n &= 333 \end{align}\]
hence,
\[\begin{align} \sum A &= 333 \left(\frac{3 + 999}{2}\right)\\ &= 333 \cdot \frac{1002}{2} \\ &= 166833 \end{align}\]
B
the last term in the sequence is \(995\) thus,
\[\begin{align} 995 &= 5 + \left(n - 1\right)5\\ 995 &= 5n\\ n &= 199 \end{align}\]
hence,
\[\begin{align} \sum B &= 199 \left(\frac{5 + 995}{2}\right)\\ &= 99500 \end{align}\]
C
the last term in the sequence is \(990\) thus,
\[\begin{align} 990 &= 15 + \left(n - 1\right)15\\ &= 15n\\ n &= 66 \end{align}\]
hence,
\[\begin{align} \sum C &= 66 \left(\frac{15 + 990}{2}\right)\\ &= 66 \cdot \left(\frac{1005}{2}\right)\\ &= 33165 \end{align}\]
Therefore the final solution,
\[\begin{align} \sum A \cup B = 166833 + 99500 - 33165 = 233168 \end{align}\]
Code
We can solve the problem brute force by writing a code that computes the sum of any number in the range \([1, 1000]\) that is a multiple of \(3\) or \(5\).
We use a generator function in the call to sum so that we don’t generate an intermediate array and then sum over the elements of the array. Instead it simply keeps a running total of the elements produced by the generator function.