Exploring the Math Behind an Innovative Code Solution

Consider the following coding challenge:

Return the sum of all multiples of 3 or 5 that are below a number N, where N is an input parameter to the function

When writing software, there is no single correct answer. The author of the article below explores six different solutions to the aforementioned problem, working through the thought process behind iterating towards a final solution.

What I learned from writing six functions that all did the same thing

This article is definitely an interesting read, but what interested me the most was the function at the end, one which far surpassed the others in term of performance.

Here is the function:

function multMath(n) {
  var threes = Math.floor(--n / 3);
  var fives = Math.floor(n / 5);
  var fifteens = Math.floor(n / 15);
  
  return (3 * threes * (threes + 1) + 5 * fives * (fives + 1) - 15 * fifteens * (fifteens + 1)) / 2;
}
module.exports = multMath;

In the original article, the function was named multSilgarth, presumably after the user who wrote it. I have renamed the function here to minimize confusion.

Let’s break down what this function is doing

1. Find the number multiples of 3 below the specified number
2. Find the number multiples of 5 below the specified number
3. Find the number of multiples of 15 below the specified number
4. Perform some magic math and return the result

Math is cool!

When I read this article, I recognized a familiar formula, one which I believe may not be common knowledge to the average person.

created using https://www.codecogs.com/latex/eqneditor.php

This is the equation for the sum of natural numbers. Say one wanted to know how many pips (or dots) are on a 6-sided die; one would need to add up 1+2+3+4+5+6. This equation gives us a shortcut: n * (n + 1) / 2. For n = 6 (the upper limit of the series to be summed):

n*(n+1)/2
=> 6*(6+1)/2
==> 6*7/2
===> 42/2
====> 21

The insight of this solution, and why it was so efficient, is the way it uses math to avoid loops. Whereas using a for or while loop is an intuitive approach that would occur first to most programmers, using a formula to optimize summation is not necessarily self-evident. This mathematical approach reduces the complexity of the solution from O(n) to O(1)!

We don’t have a lot of control structures in programming (mostly if/else branches and for/while loops), so we tend to think of solutions to problems in those terms. I think this specific example is a good counterpoint to the notion that one does not need to be good at math when learning to code, as discussed in the article below. While most of the coding I have done requires little to no math, or basic math, math can sometimes help with optimizations.

You Don't Have to Be Good at Math to Learn to Code

Let’s break down the code for anything that might be unfamiliar

Here’s the original function again:

function multMath(n) {
  var threes = Math.floor(--n / 3);
  var fives = Math.floor(n / 5);
  var fifteens = Math.floor(n / 15);
  
  return (3 * threes * (threes + 1) + 5 * fives * (fives + 1) - 15 * fifteens * (fifteens + 1)) / 2;
}
module.exports = multMath;

(x * (x + 1)) / 2

The first important part to understand is that there is a formula to determine the sum of any series of natural numbers up to and including n: (n * (n + 1)) / 2. There are many good proofs, but here’s an explanation that makes the most sense to me.

Consider summing the digits 1–10. For each number in the sequence, we can pair it with a later number in the sequence to produce the same value.

0 + 10 => 10
1 + 9  => 10
2 + 8  => 10
3 + 7  => 10
4 + 6  => 10
5
n = 10, n / 2 = 5 groups

In this case, we have 5 groups of 10’s, plus a single 5 left over (the midpoint in the sequence). Because numbers from the earlier part of the sequence pair off with numbers in the later part of the sequence, we will always have n / 2 groups for even-numbered sequences (e.g. n = 10) OR (n + 1) / 2 groups for odd-numbered sequences (e.g. n = 5).

0 + 5  => 5
1 + 4  => 5
2 + 3  => 5
n = 5, (n + 1) / 2 = 3 groups

Additionally, in the case of even-numbered sequences, the midpoint number will be left out of any group, so we have an additional n/2 term.

Odd sequence: (n + 1) / 2 groups of n
Even sequence: (n / 2) groups of n, + (n / 2)

Now, groups of n is the same things as saying * n, so we can rewrite this as

Odd sequence: (n + 1) / 2 * n
Even sequence: (n / 2) * n + (n / 2)

Finally, simplifying the terms yields:

(n + 1) / 2 * n
=> (n * (n + 1)) / 2
(n / 2) * n + (n / 2)
=> (n^2 / 2) + (n / 2) 
==> (n^2 + n) / 2 
===> (n * (n + 1)) / 2

Note that the final equation for both sequences is (n * (n + 1)) / 2

function sumToN(n)

We could then write a simple helper function:

function sumToN(n) {
  return n * (n + 1) / 2;
}

Remember that multiplication and division are commutative, so it doesn’t matter in which order we perform them.

Plugging that function into the original code above would yield a more semantic version:

function multMath(N) {
  var threes = Math.floor(--n / 3);
  var fives = Math.floor(n / 5);
  var fifteens = Math.floor(n / 15);
  
  return (3 * sumToN(threes) + 5 * sumToN(fives) - 15 * sumToN(fifteens);
}
function sumToN(n) {
  return n * (n + 1) / 2;
end
module.exports = multMath;

3 * sumToN(threes)

The next part requires us to abandon how we might usually check for multiples of three or five (iterating over an integer range and using modulo, %).

// A traditional approach
function sumMultiplesOfThree(n) {
  let i = 0, sum = 0;
  while(i < n) {
    if(i % 3 == 0) {
      sum += i
    }
    i++;
  }
  return sum;
}

Consider solving this problem for N = 30

multiples of 3: 3, 6, 9, 12, 15, 18, 21, 24, 27
multiples of 5: 5, 10, 15, 20, 25

Since the problem specifies less than N, we have to exclude the number itself.

Unfortunately, the formula we derived above for the sum of natural numbers does not allow us to sum non-sequential sets of integers. However, we can see that the sets of multiples can be reduced by dividing by their factor:

multiples of 3: 3 * [1, 2, 3, 4, 5, 6, 7, 8, 9]
multiples of 5: 5 * [1, 2, 3, 4, 5]

Great! Now we have two sequences of natural numbers again! Substituting our helper function once more yields

sum of multiples of 3: 3 * sumToN(9)
sum of multiples of 5: 5 * sumToN(5)

Okay, but how do we know what number to pass to the sumToN function? Asking “How many multiples of three are there less than or equal to 30?” is the same as performing division; 30 / 3 = 10 is the same as saying “There are 10 multiples of 3 less than or equal to 30” because there is a sequence of 10 integers that you pass through by adding 3 to itself until you arrive at 30.

Now, since we want to sum the multiples “less than” the number n, we need to insure we never include n itself, which can be accomplished by (n — 1) / 3. Furthermore, to avoid decimal numbers in cases where n — 1 is not divisible by 3 (e.g. 29 / 3 = 9.66666666...), we use the mathematical function floor, which just means “always round down to the next lowest integer.”

Putting this all together, we see that the number of multiples of three less than n is

Math.floor((n - 1) / 3);

Generalizing to any divisor, we can create another helper function:

function numberOfMultiplesLessThanN(divisor, n) {
  Math.floor((n - 1) / divisor);
}

Then, substituting what we’ve just learned into the original function gives us our final version of the function:

function multMath(n) {
  var threes = numberOfMultiplesLessThanN(3, n);
  var fives = numberOfMultiplesLessThanN(5, n);
  var fifteens = numberOfMultiplesLessThanN(15, n);
  
  return (3 * sumToN(threes) + 5 * sumToN(fives) - 15 * sumToN(fifteens);
}
function sumToN(n) {
  return n * (n + 1) / 2
end
function numberOfMultiplesLessThanN(divisor, n) {
  Math.floor((n - 1) / divisor);
}
module.exports = multMath;

Of course this could be generalized further to accept both divisors as additional arguments to multMath, or even an array of any number of divisors! That is left as an exercise for the reader.

15 * sumToN(fifteens)

There’s just two more pieces left to discuss! First, why do we care about fifteen? As you probably noticed above, our sets of multiples of three and multiples of five are not mutually exclusive

multiples of 3: 3, 6, 9, 12, 15, 18, 21, 24, 27
multiples of 5: 5, 10, 15, 20, 25
multiples of 3 AND 5: 15

There is one number that is in both lists — 15. Any number that is both a multiple of 3 and a multiple of 5 will be double counted. Conveniently, we can also say that all of these numbers will be multiples of 15 (if a number is divisible by two integers, it is also divisible by the product of those integers). So subtracting out the sum of the multiples of 15 will remove these duplicates.

--n

Lastly, there is the matter of —-n. In our version of the function, we are using a helper function for the number of multiples, so we do not use this approach. However, in the original version, we see this

var threes = Math.floor(--n / 3);
var fives = Math.floor(n / 5);
var fifteen = Math.floor(n / 15);
// This is equivalent to
var threes = Math.floor((n - 1) / 3);
var fives = Math.floor((n - 1) / 5);
var fifteen = Math.floor((n - 1) / 15);

-- is the decrement operator, so --n is equivalent to n -= 1 or n = n — 1, with one important caveat: --n mutates the value of n before it is used in whatever expression is surrounding it, where as n-- mutates the value of n after using it in the current expression.

n = 2
--n * 2
=> 2
n
=> 1
n = 2
n-- * 2
=> 4
n
=> 1

Although a minor optimization, using —-n only does the subtraction once by mutating the variable in place.

Conclusion

In closing, most programmers will very rarely come across a problem that requires advanced or esoteric math to solve. But the more math you know, the easier it will be for you to spot these opportunities.