Building Better Teams

Articles and Posts

Blog

 

Project Euler 001 The Hard Way

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.

function sumMultiplesOfTwoAndThree(n){
  var sum = 0;
  for (var i=1;i<n;i++) {
    if (((i % 3) === 0) || ((i % 5) === 0)) {
      sum += i;
    }
  }
  return sum;
}
console.log(sumMultiplesOfTwoAndThree(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.

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 sum is equal to the first and last number in the series, multiplied by half the count of numbers in the series.

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 sales 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 100 can be divided into 3, and add the highest value to the lowest value. 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 of 3 and 5 (to avoid double-counting in each set).

So, in summary, find the sum of 3s, 5s, and subtract once the sum of 15s.

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(sumMultiplesOfTwoAndThree(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.

chart.png

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
010 =  B
011 =  BC
100 = A
101 = A C
110 = AB
111 = ABC

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.

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

Now combining everything together the result is something like this:

/*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)))


    }
    if (combination.length !== 0) 


    }
    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.

You can access all the code on github if you want to look deeper.

Brian Graham