Multiples of 3 or 5: A Rare Mathematical Solution to a Common Problem

Sort Codewars by popularity and the kata sitting on top is this one:

Given a number N, return the sum of all positive multiples of 3 or 5 below it. If a number is a multiple of both, count it once. If N is negative, return 0.

It's also Project Euler problem 1, which is where it originally crawled out of. Hundreds of thousands of solutions, and almost every single one is the same loop. There is a much better answer hiding in plain sight.

The obvious approach

You read the problem, you write the loop. It's almost a reflex.

function sumMultiplesOf3Or5(n: number): number {
  if (n <= 0) return 0;
  let total = 0;
  for (let i = 1; i < n; i++) {
    if (i % 3 === 0 || i % 5 === 0) total += i;
  }
  return total;
}

This works. It passes every test. It is also, depending on how charitable you're feeling, either fine or a small crime. It does N iterations and two modulo checks each, when the answer is fully determined by N alone and could be computed in constant time. The loop is doing arithmetic the maths department settled in the 1700s.

If N is a hundred, who cares. If N is 10**18, you care a great deal.

The actual approach

The sum of every multiple of k strictly below N is just k times the sum of 1, 2, 3, ..., floor((N-1)/k). That second sum is a triangle number, and triangle numbers have a closed form Gauss is alleged to have derived as a primary-school child to spite a lazy teacher:

T(n) = n * (n + 1) / 2

So the sum of multiples of k below N is:

k * T( floor((N-1)/k) )

Apply that to 3 and 5, add them, and you've double-counted every multiple of 15. Subtract those off (also a triangle-number calculation) and you're done. This is inclusion-exclusion in its cleanest form.

function sumMultiplesOf3Or5(n: number): number {
  if (n <= 0) return 0;
  return sumMultiplesBelow(n, 3)
       + sumMultiplesBelow(n, 5)
       - sumMultiplesBelow(n, 15);
}

function sumMultiplesBelow(n: number, k: number): number {
  const highestIndex = Math.floor((n - 1) / k);
  return k * triangle(highestIndex);
}

function triangle(n: number): number {
  return (n * (n + 1)) / 2;
}

No loop. No modulo. Three multiplications, three divisions, two additions, a subtraction. Constant time, regardless of whether N is 10 or 10**18.

Why it works

The reason k * T(m) gives you the sum is worth sitting with for a second, because the moment it clicks you stop seeing this kind of problem the same way.

The multiples of 3 below 16 are 3, 6, 9, 12, 15. Factor out the 3 and you've got 3 * (1 + 2 + 3 + 4 + 5). The thing in brackets is the fifth triangle number. The "5" came from floor((16 - 1) / 3) — the count of multiples of 3 that fit under 16. That's the whole trick. Every multiples-of-k sum is a triangle number wearing a coat.

The triangle number closed form itself is the bit Gauss is supposed to have spotted. Pair the first and last term, the second and second-to-last, and so on — every pair sums to n + 1, and there are n/2 of them. So n(n+1)/2. Draw it as a triangle of dots, duplicate it, rotate the copy 180 degrees, and you've made an n by n+1 rectangle. Same proof, picture form.

Inclusion-exclusion handles the overlap. A number that's a multiple of both 3 and 5 is a multiple of 15, so it appears in both the threes sum and the fives sum. Subtract the fifteens sum once and the double-count cancels exactly. Two sets, one intersection — the cleanest case the principle has.

The lesson

After I submitted, I went looking for other people's triangle-number solutions on Codewars. The top-voted answer is a loop with i++. The next several are loops with reduce. You scroll, and scroll, and eventually find a triangle-number solution sitting at a fraction of the votes, written by someone who clearly enjoyed themselves.

Algorithmic answers and mathematical answers are different categories of thing. The algorithmic answer asks "how do I compute this step by step." The mathematical answer asks "what is this, actually." They feel like the same question in the moment, but they aren't. The loop is faithful to the problem statement. The closed form is faithful to the structure underneath it.

Most coding-interview-style problems sit somewhere in between. You can almost always grind out an algorithmic answer. Occasionally — and this is one of those occasions — there's a mathematical answer that makes the algorithmic one look like you've shown up to a dinner party with a bag of raw potatoes. The skill worth cultivating isn't the maths, exactly. It's the pause before the loop, where you ask whether the problem is actually a problem or just a sum you haven't recognised yet.