Multiples of 3 or 5

This article investigates arithmetic sequences and series from a few different perspectives, and ends by touching on the inclusion-exclusion principle.

This article includes code snippets, however, they reveal no information that is not already discussed in prose. If you have no interest in the code, the snippets can be skipped without any loss of continuity.

The contents should be accessible (and hopefully interesting as well) to those ranging from late high-school to early undergraduate. There is nothing super complicated here—just a little arithmetic and a little logic.

Multiples of 3 or 5

From #1 Multiples of 3 or 5 - Project Euler

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\).

One of the first things that comes to mind is to check every natural number in \([3,1000)\) for divisibility by \(3\) or \(5\). We are checking \(n\) numbers for divisibility by \(m\) divisors, so the time complexity of this algorithm is \(O(n\,m)\).

  // Check-Every-Number Algorithm
  int sum{};
  for (int i = 3; i < 1000; ++i) {
    if (i % 3 == 0 || i % 5 == 0) {
      sum += i;
    }
  }
  std::cout << sum << '\n'; // 233168

That works! But, there is another way to think about the problem…

Arithmetic series

Enumerating the multiples of \(3\) in \([3,1000)\) gives the finite arithmetic sequence

\[ 3,6,9,\dots,999. \]

An arithmetic sequence is an ordered list of numbers where every next number is generated by adding a constant to the previous number. This constant, say d, is known as the common difference. In the case of our sequence of multiples of three, our first element is \(3\) and we generate every next element by adding \(d=3\) to the previous element.

There is a well-known closed-form^\(\text{*}\) expression to calculate the sum of a finite arithmetic sequence:

^\(\text{*}\) “Closed-form” meaning an expression of a constant number of arithmetic operations, as opposed to the \(n-1\) arithmetic operations when summing any old collection of n numbers: \(x_1+x_2+\dots+x_{n-1}+x_n\).

\[ \sum_{i=1}^{n}a_i = \left(\frac{a_1+a_n}{2}\right)n\,. \tag{1}\]

So, the sum of all multiples of \(3\) below \(1000\) is

\[ \left(\frac{3+999}{2}\right)333 = 166833. \]

We know that there are \(333\) elements in the sequence because \((1000-1)//3=333\).

\(//\) means integer division. Divide then discard the fractional part. \(3/2=1.5,\,3//2=1\).

We can verify the result with our check-every-number algorithm:

  // Check-Every-Number Algorithm
  int sum{};
  for (int i = 3; i < 1000; ++i) {
    if (i % 3 == 0) {
      sum += i;
    }
  }
  std::cout << sum << '\n'; // 166833

Cool! But, why does this work? Let’s examine each of the terms in the expression \(\left(\dfrac{a_1+a_n}{2}\right)n\).

Building intuition

Arithmetic mean

You may have noticed that the term \(\dfrac{a_1+a_n}{2}\) resembles the form of an average—or more precisely—an arithmetic mean. It is the average of \(a_1\) and \(a_n\), and is also—perhaps surprisingly—the average of any arithmetic sequence starting with \(a_1\) and ending with \(a_n\). In other words, the average of a collection of numbers \(a_1\) through \(a_n\)

Here, average is used to mean arithmetic mean.

\[ \overline{a} = \frac{1}{n} \sum_{i=1}^{n} a_i = \frac{a_1+a_2+a_3+\dots+a_{n-1}+a_{n-1}+a_n}{n} \] can be shortened to \[ \overline{a}= \frac{a_1+a_n}{2} \] in the special case that \(a_1\) through \(a_n\) form an arithmetic sequence. Why?

We can think of an average as a sort of center; a point of balance; a center of mass. Imagine the numbers in a sequence to be objects of uniform mass, fixed to a rigid pole at positions corresponding to their positions on the number line. For the sequence \(\{-1,1\}\), our point of balance would be \(0\).

We can fix as many of these objects as we like to this pole and keep the center of balance at \(0\); so long as we place objects in pairs equidistant and on opposite sides from \(0\), or place the objects directly at the center of balance. For example, extending the sequence \(\{-1,1\}\) with the numbers \(\{-\frac{3}{5},\frac{3}{5}\},\{-\frac{1}{2},\frac{1}{2}\},\{-\frac{1}{3},\frac{1}{3}\},\{-\frac{1}{5},\frac{1}{5}\}\), and \(\{0\}\) maintains balance at \(0\): \[ \frac{-1-\frac{3}{5}-\frac{1}{2}-\frac{1}{3}-\frac{1}{5}+0+\frac{1}{5}+\frac{1}{3}+\frac{1}{2}+\frac{3}{5}+1}{11} = \frac{0}{11} = 0. \]

These numbers are the Farey sequence of order five transformed to fit the number line example: \(\left(\mathcal{F}_5-\frac{1}{2}\right)\cdot 2\).

Farey sequences have the property that we are exploring with the number line example: no matter how many elements there are in the sequence, they are constructed in such a way that the arithmetic mean of any Farey Sequence is \(\frac{1}{2}\).

This is exactly the type of balance we see in arithmetic sequences. Because every element in an arithmetic sequence is equidistant from its neighbors—leaning back on our analogy of center of mass—it’s not too far fetched to imagine that, where ever the center of the sequence is, there will be an equal number of elements on either side of that center, and the elements will be “balanced” in their distance from the center.

If we know the bounds of a sequence—the first and last elements—and know that all other elements of the sequence come in pairs balanced around the center, or at the center, then we do not need to know how many other elements there are, or what their exact values are, in order to find the center of the sequence. We may make an educated guess that the center will be exactly halfway between the first and last elements.

And so, we have made some sense of the term \(\dfrac{a_1+a_n}{2}\).

Looking back on Equation 1 and having made some sense of the term representing the average of an arithmetic sequence, we now ask: why do we multiply the average of the sequence by the number of terms in the sequence to arrive at the sum?

Join me, again, in an exercise in imagination.

If you aren’t familiar with SpongeBob please excuse my misplaced humor.

Arithmetic mean times \(n\)

Imagine the numbers in a sequence \(a_1, a_2,\dots,a_n\) to be rectangles of a height \(a_i\) and of width 1. The sequence \(\{1,2,3\}\) could then be visualized as in the left most of the two figures below.

What is the total area of the rectangles in the collection on the left? The area of a rectangle is, of course, width \(w\) by height \(h\), and all widths here are \(1\), so the area of the \(i^{th}\) rectangle is equal to its height \(A_i = h_i = a_i\). The total area of the rectangles in the sequence \(\{1,2,3\}\) is \(1+2+3=6\).

Now, imagine that we want to “flatten” our collection of rectangles so that they are all of equal height, but whenever we push down on one rectangle, another rectangle of our choosing must rise an equal distance, so that total area of the collection is preserved. Easy enough: we can push down the third rectangle a distance of \(1\) and allow the first rectangle to rise by a distance of \(1\). Our collection now looks like the rightmost of the two figures above, and—as we know from the rules of the game—the total area of the rectangles is still \(6\).

The uniform height of the rectangles after the flattening game is equal to the average height of the original rectangles \((1+2+3)/3=2\). The area of the collection, before and after flattening, is equal to that average height times the number of rectangles \(2*3=6\). And so it is for any collection of rectangles we play this game with.

Stepping away from the rectangle analogy, the previous paragraph becomes: the sum of a collection of numbers is equal to the average of that collection times the number of elements in the collection. This claim is simple to prove:

\[ a_1+a_2+\dots+a_n = \left(\frac{a_1+a_2+\dots+a_n}{n}\right) n . \]

And so, we have an idea why we multiply the average \(\dfrac{a_1+a_n}{2}\) by the count \(n\) to arrive at the sum.

Intuitive justification

Combining our conclusions from the previous two sections, our justification for Equation 1 becomes something like:

The sum of a collection of numbers is equal to the average of the collection times the number of elements in the collection (as shown in \(\S\) Arithmetic mean times \(n\))

\[ \sum_{i=1}^{n}a_i = a_1+a_2+\dots+a_n = \left(\frac{a_1+a_2+\dots+a_n}{n}\right) n, \]

and in the special case that \(a_1\) through \(a_n\) form an arithmetic sequence, we can simplify the expression for the average of the sequence (as discussed in \(\S\) Arithmetic mean)

\[ \left(\frac{a_1+a_2+\dots+a_n}{n}\right) n = \left(\frac{a_1+a_n}{2}\right) n. \]

Therefore, the sum of a finite arithmetic sequence starting with \(a_1\) and ending with \(a_n\) is

\[ \sum_{i=1}^{n}a_i = \left(\frac{a_1+a_n}{2}\right) n. \]

We have arrived at Equation 1!

Derivation

In addition to our analogy-based justification of the formula for the sum of a finite arithmetic series, we can derive it algebraically.

We know that an arithmetic sequence is an ordered list of numbers where every next number is generated by adding a constant to the previous number. Using this, we can describe any element in the sequence in terms of the first element plus some number of steps. The \(n^{th}\) element of an arithmetic sequence with common difference \(d\) would be

\[ a_n=a_1+(n-1)\,d. \tag{2}\]

To illustrate relationship, the sequence of multiples of three, starting with 3, can be written as: \[ 3+(1-1)\cdot 3,\quad 3+(2-1)\cdot 3, \quad 3+(3-1)\cdot 3,\quad \dots,\quad 3+(n-1)\cdot 3. \]

Using Equation 2, we have an algebraically convenient way to express the sum of an finite arithmetic sequence starting with \(a_1\) ending with \(a_n\) and having common difference \(d\):

\[ a_1+\dots+a_n = \sum_{i=1}^{n} a_1 + (i-1)\,d . \]

It is from this point that we begin our attempt to derive Equation 1:

\[\begin{align*} \sum_{i=1}^{n} a_1 + &(i-1)d \\ &= \sum_{i=1}^{n} a_1 + \sum_{i=1}^{n} (i-1)d\\ &= na_1 + d\sum_{i=1}^{n} (i-1)\\ &= na_1 + d \left[(1-1)+(2-1)+(3-1)+\dots+((n-2)-1)+((n-1)-1)+(n-1)\right]\\ &= na_1 + d \left[(1-1)+(2-1)+(3-1)+\dots+(n-3)+(n-2)+(n-1)\right]\\ \end{align*}\]

And here we come to a tricky step: folding the series onto itself. Notice that, as we list terms from \((1-1)\) to \((n-1)\), for every \((x-1)\) term we have in the first half of the series, we find an \((n-x)\) term in the second half of the series. Each of these pairs simplifies to \((n-x)+(x-1)=(n-1)\). Notice also, that there are \(n\) terms in the series, and therefore \(n/2\) of the aforementioned pairs in the series. In all, we simplify \(n/2\) pairs to \((n-1)\), so we write

\[\begin{align*} &= na_1 + d \left[(1-1)+(2-1)+(3-1)+\dots+(n-3)+(n-2)+(n-1)\right]\\ &= na_1 + d \left[(n-1)\frac{n}{2}\right]. \end{align*}\]

Remembering the equation for the \(n^{th}\) element of an arithmetic sequence (Equation 2), we can clean up our final expression a bit:

\[\begin{align*} na_1 + (n-1)\frac{n}{2}d &= \left( 2a_1 + (n-1) d \right)\frac{n}{2} \\ &= \left( a_1 + a_1 + (n-1) d \right)\frac{n}{2} \\ &= \left( a_1 + a_n\right)\frac{n}{2} \\ &= \left(\frac{a_1+a_n}{2}\right)n. \end{align*}\]

And so we have arrived at the familiar expression.

Proof

The derivation is a proof unto itself, but I thought it would be fun to include a proof with mathematical induction. If you are unfamiliar with mathematical induction, that’s fine, just skim over the proof once, then look it over again as you read the following section: An explanation of mathematical induction.

Proposition. If \(a_1,\dots,a_n\) is an arithmetic sequence of \(n\) elements, then the sum of that sequence is

\[ \sum_{i=1}^{n}a_i = \frac{a_1+a_n}{2}n. \]

Proof. We know the proposition is true for \(n=2\); we assume it is true for \(\,n-1\,\) and prove it true for \(n\).

We start by writing the series as

\[ \sum_{i=1}^{n}a_i = \sum_{i=1}^{n-1}a_i + a_n = \frac{a_1+a_{n-1}}{2}(n-1) + a_n. \tag{3}\]

But, we know that

\[ a_{n-1}=a_n-d \quad\text{and}\quad d=\frac{a_n-a_1}{n-1}, \]

so the expression becomes

\[\begin{align*} \frac{n-1}{2}\left(a_1+a_{n-1} \right)+ a_n &= \frac{n-1}{2}\left(a_1 + a_n - \frac{a_n-a_1}{n-1}\right) + a_n \\ &= \frac{1}{2}\left(\,n\,(a_1+a_n)-1(a_1+a_n)-(a_n-a_1)+2a_n\right) \\ &= n\,\frac{a_1+a_n}{2}. \\ \end{align*}\]

\(\blacksquare\)

An explanation of mathematical induction

Mathematical induction, as used here, basically works as follows: We provide some base case for which the proposition is true. Then we show that, if we assume it is true for \(n-1\), it must also be true for \(n\).

In the proof above, we assume the proposition is true for \(n-1\) by equating

\[ \sum_{i=1}^{n-1}a_i \quad\text{and}\quad \frac{a_1+a_{n-1}}{2}(n-1). \]

Then we show that, under this assumption, the proposition also holds for \(n\). After we have established these facts, we use our base case and inductive reasoning to conclude that the proposition holds for all natural numbers greater than our equal to our base case:

We know the proposition is true for the base case \(n=2\). So, we let \(2\) stand in for \(n-1\). We know that it holds for \(n=2\), so we know it holds for \(n-1=2\); and because it holds for \(n-1=2\), by the algebra in our proof, it must hold for \(n=3\). Now that we have proven it holds for \(n=3\), we equate \(3\) and \(n-1\). Our proposition is true for \(n=3\), so we know it holds for \(n-1=3\); and because it holds for \(n-1=3\), by the algebra in our proof, it must hold for \(n=4\). In this way, we build a ladder off into infinity, the integrity of every next rung being guaranteed by the integrity of the previous rung.

A second solution

Instead of checking every natural number in \([3,1000)\) for divisibility by \(3\) or \(5\), as we did in our first solution, we can concisely express the sum of all multiples of \(3\) or \(5\) below 1000 using Equation 1:

\[ \left(\frac{3+999}{2}\right)333 + \left(\frac{5+995}{2}\right)199 = 266333. \]

We know there are \(199\) elements in the sequence of multiples of five less than \(1000\) because \((1000-1)//5=199\).

  int sum{};
  sum += (3 + 999) * 333 / 2;
  sum += (5 + 995) * 199 / 2;
  std::cout << sum << '\n'; // 266333

Welp…comparing this to our check-every-number algorithm, which gives \(233168\), we can see that we have overcounted by a bit. Why?

Enumerating the multiples of \(3\) and \(5\), we see that the two sequences share some elements:

\[ 3,6,9,12,\underline{15},18,21,24,27,\underline{30},\dots \] \[ 5,10,\underline{15},20,25,\underline{30},\dots \]

These shared elements are being doubly counted: once in the sum of the multiples of \(3\), and once in the sum of the multiples of \(5\). So, we need to find the sum of all these shared numbers and subtract that from our total, so that they are counted only once and not twice.

How do we get a handle on these shared numbers? They are multiples of \(3\), and they are multiples of \(5\); in shorter words they are multiples of \(3\) and \(5\); in even shorter words, they are multiples of \(15\). So, we need to subtract the sum of all multiples of \(15\) less than \(1000\) from our total:

\[ \left(\frac{3+999}{2}\right)333 + \left(\frac{5+995}{2}\right)199 - \left(\frac{15+990}{2}\right)66 = 233168. \]

  int sum{};
  sum += (3 + 999) * 333 / 2;
  sum += (5 + 995) * 199 / 2;
  sum -= (15 + 990) * 66 / 2;
  std::cout << sum << '\n'; // 233168

Nice!

Now, what if we were interested in a more general question? What about the sum of multiples of some collection of positive integers less than some positive limit? The first step is to move from two divisors to three divisors: find the sum of all multiples of \(3\) or \(5\) or \(7\) below \(1000\).

First, let’s get a confident result from our check-every-number algorithm:

  // Check-Every-Number Algorithm
  int sum{};
  for (int i = 3; i < 1000; ++i) {
    if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
      sum += i;
    }
  }
  std::cout << sum << '\n'; // 271066

The next question is: how do we treat the over-counted numbers? Now that we have three divisors, some numbers will be singly counted, some doubly so, and some triply so. Do we subtract the series of the pair-wise least common multiples \(3\cdot5=15\), \(\,3\cdot7=21\), and \(\,5\cdot7=35\)? Or, do we subtract the series of the three-way least common multiple \(3\cdot5\cdot7=105\)? Maybe both?

The answer is found in a bit of discrete maths called the inclusion-exclusion principle. It directly addresses our problem of counting a thing once, and once only.

And it is here that the article ends abruptly.

I wrote most of this several months ago, and fully intended on investigating the inclusion exclusion principle, but kinda lost steam over time. Perhaps I’ll come back to it later.