Project Euler 001 The Hard Way

Historical Context

This is a rewrite of an article I wrote in January 2012 where I discover the hidden complexity of a simple programming problem.

Problem 001

On the popular programming challenge website Project Euler, the first problem seems quite trivial. However, with deeper examination we can discover layers of complexity as we try to generalize the problem.

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.

It looks almost like a generic screening interview problem. The problem should be solvable anywhere between 1 and 5 minutes by any developer. It's a simple loop, some logic, and addition.

Initial Brute Force Solution

The most straightforward approach using a simple loop

function sumMultiplesOfThreeAndFive(n){
var sum = 0;
for (var i=1;i<n;i++) {
  if (((i % 3) === 0) || ((i % 5) === 0)) {
    sum += i;
  }
}
return sum;
}
console.log(sumMultiplesOfThreeAndFive(1000))

Solving every set of multiples

Looking at the code it's quite obvious 3 and 5 are replaceable with any set of other numbers. All we need to do is tweak the code to support accepting an array of multiples that will be tested.

Generalized Solution

Extended to work with any array of multiples

function sumMultiples(n, multiples){
var sum= 0;
var isMultiple = function(n, multiple){
  return ((n % multiple) === 0);
};
var commonMultiples = function (n,multiples){
  var isCommon = false;
  for (var i=0;i<multiples.length;i++){
    isCommon = (isCommon || isMultiple(n, multiples[i]));
  }
  return isCommon;
};
for (var i=1;i<n;i++) {
  if (commonMultiples (i,multiples)) {
    sum += i;
  }
}
return sum;
}
console.log(sumMultiples(1000, [3,5]))

Fixing the performance issue

Every time it searches for a higher number it ends up taking longer to run. So how else might I try to solve this? I recalled a story a high school math teacher told me about the Mathematician Gauss. His teacher punished him with the daunting task of adding together all the numbers between 1 and 100. Gauss solved it in minutes, because saw a simple pattern which he invented called the Arithmetic Sum.

The formula for an arithmetic series is:

$S_n = \frac{n}{2}(a_1 + a_n) = \frac{n}{2}(a + a \cdot n)$

Where:

• $n$ is the number of terms
• $a$ is the first term
• $a_n$ is the last term

The sum is equal to the first and last number in the series, multiplied by half the count of numbers in the series.

What's amazing about this is it scales at O(1), there's no Ifs or Loops here. It works the same way for 100 as it does 10e100.

If we find the sum of 3s, we just find the number of times 999 can be divided by 3, then apply the arithmetic series formula. The same for 5s. This does however introduce a slight problem: just adding the two values together is higher than the final result. We need to subtract all multiples that are common to both 3 and 5 (to avoid double-counting).

So, in summary, find the sum of 3s, 5s, and subtract once the sum of 15s (since 15 is the LCM - Least Common Multiple - of 3 and 5).

Mathematical Optimization

Using arithmetic series formula for O(1) performance

function sumMultiplesOfTwoOrThree(n){
var sum= 0;
var arithmeticSum = function(a, n){
  return (1/2)*n*(a+a*n);
};
var arithmeticSumFromSeriesMultiple = function(series, multiple){
  series -= 1; //Euler problem #1 wants numbers less than 1000.
  var a = multiple;
  var n = Math.floor(series/multiple);
  return arithmeticSum(a, n);
}
sum += arithmeticSumFromSeriesMultiple(1000, 3);
sum += arithmeticSumFromSeriesMultiple(1000, 5)
sum -= arithmeticSumFromSeriesMultiple(1000, 15);
return sum;
}
console.log(sumMultiplesOfTwoOrThree(1000))

Solving all combinations with performance

Thinking back to set theory and Venn diagrams, there's a visual intersection between 3s and 5s that is clearly just the set of 15s that need to be negated once. In more generic terms, if provided A and B, the script must run sum(A)+sum(B)-sum(AB).

Using two for-loops this is an easy task, but again leads to a slow running solution. The real problem here is finding a way to generate all permutations for a set. There's a great way to do that: simply counting in boolean and assigning a place-value to each element in the list of multiples.

That sounds a bit confusing so visualizing here will help. Let's look at this set of multiples with 3s, 5s, and 7s.

So there's some overlap between all these sets:

• 3s and 5s
• 5s and 7s
• 7s and 3s
• 3s, 5s, and 7s combined

So in this case I'd have to: sum(3)+sum(5)+sum(7)-sum(3×5)-sum(3×7)-sum(7×3)+sum(3×5×7).

As mentioned above, another way to look at this is binary mapping:

001 = C      (cardinality 1: ADD)
010 = B      (cardinality 1: ADD)  
011 = BC     (cardinality 2: SUBTRACT)
100 = A      (cardinality 1: ADD)
101 = AC     (cardinality 2: SUBTRACT)
110 = AB     (cardinality 2: SUBTRACT)
111 = ABC    (cardinality 3: ADD)

Simply knowing this mapping we can generate all the combinations of sums needed. If it's added or subtracted is simply a matter of how many 1s are in a number: odd numbers get added, even gets removed.

Bitwise Magic

What's exciting here is using bitwise operators to generate all possible combinations. Each number from 1 to 2^n-1 represents a unique subset when interpreted as a binary mask!

This follows the inclusion-exclusion principle, which can be expressed mathematically as:

$\left| \bigcup\limits_{i=1}^n A_i \right| = \sum\limits_{i=1}^n | A_i | - \sum\limits_{1 \le i<j \le n} | A_i \cap A_j | + \sum\limits_{1 \le i < j < k \le n} | A_i \cap A_j \cap A_k | - \ldots + (-1)^{n-1} | A_1 \cap A_2 \cap \ldots \cap A_n |$

For our specific case with three sets (multiples of 3, 5, and 7), this becomes:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

So with this known, we simply need a combination generator. This will take ["a", "b", "c" , "d"] and return ["a", "b", "ab", "c", "ac", "bc", "abc", "d", "ad", "bd", "abd", "cd", "acd", "bcd", "abcd"] (all combinations of ABCD).

Helper Functions

Utility functions for combinations and arithmetic operations

/*Generate a list of all Combinations*/
function getCombinations(list){
var combinations = []; //All combinations
var combination = []; //Single combination
var quantity = (1 << list.length);
for (var i = 0; i < quantity ; i++){
  combination = [];
  for (var j=0;j<list.length;j++) {
    if ((i & (1 << j))){
      combination.push(list[j]);
    }
  }
  if (combination.length !== 0) {
    combinations.push(combination);
  }
}
return combinations;
}

/*Generate a product from a list of numbers*/
function listProduct(list){
var product=1;
for (var i=0;i<list.length;i++){
  product *=list[i];
}
return product;
}

/*Return the arithmetic sum*/
function arithmeticSum (a, n){
return (1/2)*n*(a+a*n);
}

/*Generate the arithmetic sum of a series based on a multiple*/
function arithmeticSumFromSeriesMultiple (series, multiple){
series -= 1; //Euler problem #1 wants numbers less than the range.
var a = multiple;
var n = Math.floor(series/multiple);
return arithmeticSum(a, n);
}

Now combining everything together the result is something like this:

Complete Optimized Solution

Final solution using inclusion-exclusion principle with O(1) arithmetic series

/*Generate a list of all Combinations*/
function getCombinations(list){
var combinations = []; //All combinations
var combination = []; //Single combination
var quantity = (1 << list.length);
for (var i = 0; i < quantity ; i++){
  combination = [];
  for (var j=0;j<list.length;j++) {
    if ((i & (1 << j))){
      combination.push(list[j]);
    }
  }
  if (combination.length !== 0) {
    combinations.push(combination);
  }
}
return combinations;
}

/*Generate a product from a list of numbers*/
function listProduct(list){
var product=1;
for (var i=0;i<list.length;i++){
  product *=list[i];
}
return product;
}

/*Return the arithmetic sum*/
function arithmeticSum (a, n){
return (1/2)*n*(a+a*n);
}

/*Generate the arithmetic sum of a series based on a multiple*/
function arithmeticSumFromSeriesMultiple (series, multiple){
var a = multiple;
var n = Math.floor(series/multiple);
return arithmeticSum(a, n);
}

function sumMultiples(range, multiples){
var sum= 0;
var subsetSums = [];
var multiplesCombination=getCombinations(multiples);
for (var i=0;i<multiplesCombination.length;i++){
  //Generate product from combinations of multiples
  //and
  //Find individual sums of all combinations.
  subsetSums.push(
    arithmeticSumFromSeriesMultiple(
      range,
      listProduct(multiplesCombination[i])
    )
  );
}

for (var i=1; i< subsetSums.length + 1;i++){
  //Check if i is an even base 2.
  if ((i & (i - 1)) == 0){
    sum += subsetSums[i-1];
  } else {
    sum -= subsetSums[i-1];
  }
}
return sum;
}

console.log(sumMultiples(999, [3,5]));

Results

A quick check of performance yields these results:

• Using really large numbers, the math approach is much faster.
• Using really small sets, the simple for-loop is faster in 2020, but I remember it was slower in 2012 when I originally tested this.

Performance Insight

The mathematical approach scales at O(1) regardless of range size - it works the same for 1,000 as it does for 10^100. The brute force approach scales linearly with the range size.