Problem 1

Multiples of 3 and 5

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.

http://projecteuler.net/problem=1

Brute Force

function euler1() {
  var sum = 0,
      i = 1000;
  while (--i) {
    if (i % 3 && i % 5)
      continue;
    sum += i;
  }
  return sum;
}
timer(euler1, 100000);
// euler1 x 100000: 348.270ms
// 233168

# Time O(n)

To brute force an answer, we check each number less than 1000 is a multiple of 3 or 5, adding it to the sum if it passes the check.

Another way to brute force the problem is to add all the multiples of 3 and multiples of 5 then subtract the multiples of both 3 and 5. The last step is necessary because the multiples of 15 have been added sum twice.

function euler1() {
  function sumMultiples(multiple, N) {
    var sum = 0,
        i = multiple;
    while(i < N) {
      sum += i;
      i += multiple;
    }
    return sum;
  }
  return sumMultiples(3, 1000) + sumMultiples(5, 1000) - sumMultiples(15, 1000);
}
timer(euler1, 100000);
// euler1 x 100000: 105.516ms
// 233168

# Time O(n)

This method ends up being less performant than our initial approach but is a step in the right direction.

Arithmetic Progressions and Series

An arithmetic progression is a sequence when the difference between two consecutive members is constant delta.

An arithmetic series is the sum of all the members a finite arithmetic progression. It can be generalized as:

Having this information, we can replace the loop in our previous solution with a function that returns the sum.

function euler1() {
  function sumMultiples(multiple, N) {
    var n = Math.floor((N-1) / multiple); // number of integers in series
    return n * (multiple + (n * multiple)) / 2;
  }
  return sumMultiples(3, 1000) + sumMultiples(5, 1000) - sumMultiples(15, 1000);
}
timer(euler1, 100000);
// euler1 x 100000: 11.850ms
// 233168

# Time O(1)