The Integrated

Since I discovered it yesterday, I’ve been hooked on Project Euler, working furiously on solving as many problems as possible. It’s a site that poses hundreds of math problems designed to be solved by writing computer programs, and tracks which ones you’ve solved. Naturally, I’m using JavaScript, and I’ve solved the first ten problems so far. Now, given my inexperience, the solutions I arrived at are going to be flawed—mostly in terms of efficiency—but obviously they work.

I made a file for the project, euler.html, where I’ll write my solutions for each problem. Of course there will be some functions shared among different problems, which is part of the reason for doing it in a single script. I’ll put a button on the page for each problem that’ll run its solution and spit out the answer. Although it doesn’t really matter here, I’ll also stick to best-practices and avoid polluting the global namespace by encapsulating my script’s functionality in a self-executing function. Common, private variables and functions will be defined, and then a hash will be returned with a member for each problem. This exposes them to the rest of the page (so the aforementioned buttons can call them), but they’ll have access to the private stuff thanks to closure.

var Euler = (function() {
  // private stuff here

  return {
    P1: function() {
      // algorithm for problem 1
    },
    // etc...
  };
})();

On to the first 10 problems. Note: If you want to solve them yourself, “spoilers” follow after the jump! Please don’t cheat.

Problem #1

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.

You’ll see that most of my solutions are what could be described as “brute-force”, which is mainly because it’s been several years since I had a math class. The first one is typical. I just loop from 1 to 999, test each number to see if it’s evenly divisible by 3 or 5, and keep a running sum.

// Project Euler: #1
var sum = 0;

for (var i = 1; i < 1000; i++) {
  if (!(i % 3) || !(i % 5))
    sum += i;
}

return sum;

Problem #2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

The easiest way to generate the Fibonacci sequence is to start with 1 and 1 as initial values, then keep track of the last two values f1 and f2 you generated, add them to get f’, then make f2 and f’ your new f1 and f2 for the next iteration. Testing for even values is easy; the number merely has to be evenly divisible by two.

// Project Euler: #2
var f1  = 1,
    f2  = 1,
    sum = 0;

do {
  fp = f1 + f2;
  f2 = f1;
  f1 = fp;
  if (!(fp % 2)) sum += fp;
} while (fp < 4000000);

return sum;

Problem #3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

And here we get the first problem where I’ll be breaking off part of the solution into a private function for Euler, because I’ll need it again. To prime factorize a number, I need to generate prime numbers. To do this, I’ll loop over ever-increasing numbers until I find one that meets a test for primality. If a number is evenly divisible by any prime number up to or including its square root, it’s not prime. Actually, if it’s evenly divisible by any number period between two and its square root, it’s not prime, but we really only need to test against prime numbers, because the rest can by definition be broken down into primes anyway. Testing only prime numbers with our prime candidate should be faster than testing every number.

To do this, I’ll keep around an array of the primes I’ve already generated, starting with the first prime, two. This array will be looped over, testing whether each number divides evenly into our prime candidate. If any of them do, the candidate’s not prime, so increment it and start again. This will eventually generate the next prime and return it, and append it to the array, enabling the function to get the next prime the next time it’s called. We’ll only keep testing our candidate until we hit the end of the array of primes, we hit a prime that’s greater than the square root of the candidate, or we find a prime that divides evenly into the candidate (once you’ve already failed, no point in continuing). As long as we do keep finding a prime factor, we’ll keep starting over and incrementing the candidate number.

// Prime number generation: testing even divisibility by smaller primes
var primes = [2];

function findNextPrime() {
  var factorFound,
      pl = primes.length,
      i = primes[pl-1];

  do {
    i++;
    factorFound = false;
    for (var j = 0; (j < pl) && (primes[j] <= Math.sqrt(i)) && !factorFound; j++) {
      if (!(i % primes[j])) factorFound = true;
    }
  } while (factorFound);

  primes.push(i);
  return i;
}

This algorithm works pretty well for relatively small primes; the obvious problem as you keep generating larger and larger primes is that the primes array is going to get very big. Eventually, most browsers will freeze the script to prevent it from crashing the program or your system. For the size of primes that I need to solve problem #3, however, it won’t get anywhere near that point.

The actual factorization is simple: find the first prime number that evenly divides into the number. Now take the result of this division and repeat the process. Repeat as many times as you have to; eventually the decreasing number (as you divide it over and over) and the increasing series of primes you’re generating converge on the same, prime number (dividing evenly into itself). This is the largest prime factor, and the other primes you used along the way are the other prime factors. I don’t bother storing them, though, as I have no need for them here.

// Project Euler: #3
var n = 600851475143,
    i = 2;

do {
  if (!(n % i))
    n = n / i;
  else
    i = findNextPrime();
} while (primes.indexOf(n) == -1);

return n;

Problem #4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

This is a fun problem, because it requires a little string magic. First, a test of palindromosity (no, that’s not a word). Use the String.split() function to break a string into an array of characters. Then, compare the outermost characters, move in and compare, move in and compare, until we’ve determined if everything matches up or not.

// Test if string s is a palindrome.
function isPalindrome(s) {
  var l = Math.floor(s.length / 2),
      a = s.split("");

  for (var i = 0; i < l; i++) {
    if (a[i] != a[a.length - (i + 1)]) return false;
  }

  return true;
}

Now, we simply start looping two factors starting at 999 each, and if we find a palindrome that’s larger than the last one we found, keep it.

// Project Euler: #4
var highPal = 0;

for (var i = 999; i > 99; i--) {
  for (var j = i; j > 99; j--) {
    var p = i * j;
    if (isPalindrome(p.toString()) && p > highPal) {
      highPal = p;
      break;
    }
  }
}

return highPal;

Problem #5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Clearly, another iterate-and-test problem. What’s new here is that we’re given significant information in the question that reduces the search space. Since the result must be evenly divisible by 1-10, and 2520 is evenly divisible by 1-10, there are three major consequences for our search:

1. The result must be evenly divisible by 2520.
2. We don’t need to test for even divisibility by 1-10, so long as condition 1 is fulfilled.
3. We don’t need to test any number below 2520, so long as condition 1 is fulfilled.

Thus, start at 2520 and increment by 2520. This guarantees 1., and allows us to take 2. into account by only testing even divisibility by 11-20.

// Project Euler: #5
var n = 2520,
    isDivisibleByAll;

do {
  n += 2520;
  isDivisibleByAll = true;
  for (i = 20; i > 10; i--) {
    if (n % i) isDivisibleByAll = false;
  }
} while (!isDivisibleByAll);

return n;

Problem #6

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Another straightforward problem. Loop from 1 to 100 and keep running sums of the numbers and their squares, then square the former once you’re done and compare.

// Project Euler: #6
var sum     = 0,
    sumOfSq = 0;

for (var i = 1; i <= 100; i++) {
  sum += i;
  sumOfSq += Math.pow(i,2);
}

return Math.abs(sumOfSq - Math.pow(sum,2));

Problem #7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^th prime is 13.

What is the 10001^st prime number?

Stupidly easy with the prime number generator I provided earlier. It’ll quickly go up to 10,001 primes without your browser even breaking a sweat.

// Project Euler: #7
while (primes.length < 10001) {
  findNextPrime();
}

return primes[10000];

Problem #8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

More fun with strings! Store the number as a string, and just take each 5-character substring you can out of this sucker, split() it, and multiply the digits together. Keep track of the highest product you find.

// Project Euler: #8
var s = "73167176531330624919225119674426574742355349194934" +
        "96983520312774506326239578318016984801869478851843" +
        "85861560789112949495459501737958331952853208805511" +
        "12540698747158523863050715693290963295227443043557" +
        "66896648950445244523161731856403098711121722383113" +
        "62229893423380308135336276614282806444486645238749" +
        "30358907296290491560440772390713810515859307960866" +
        "70172427121883998797908792274921901699720888093776" +
        "65727333001053367881220235421809751254540594752243" +
        "52584907711670556013604839586446706324415722155397" +
        "53697817977846174064955149290862569321978468622482" +
        "83972241375657056057490261407972968652414535100474" +
        "82166370484403199890008895243450658541227588666881" +
        "16427171479924442928230863465674813919123162824586" +
        "17866458359124566529476545682848912883142607690042" +
        "24219022671055626321111109370544217506941658960408" +
        "07198403850962455444362981230987879927244284909188" +
        "84580156166097919133875499200524063689912560717606" +
        "05886116467109405077541002256983155200055935729725" +
        "71636269561882670428252483600823257530420752963450",
    highProduct = 0;

for (var i = 0; i < 995; i++) {
  var p     = 1,
      chunk = s.substr(i,5);

  chunk = chunk.split('');

  for (var j = 0; j < 5; j++) {
    p *= chunk[j];
  }

  if (p > highProduct) highProduct = p;
}

return highProduct;

Problem #9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Once again, we benefit from a search space that is severely limited due to conditions in the problem. Because a < b < c and their sum is 1000, a cannot be greater than 332 (¹/₃ of the sum) and b cannot be greater than 499 (½ of the sum). For each b starting at 499, we’ll test each a, both counting down. I actually didn’t work in the limitation of a being less than 332, but the algorithm works without it. A more complex initialization for a that sets it to 332 if b minus one is greater than 332 would work, and possibly be faster, but the code would be harder to read.

// Project Euler: #9
for (var b = 499; b > 1; b--) {
  for (var a = b - 1; a > 0; a--) {
    var c = 1000 - (a + b);
    if (a * a + b * b == c * c)
      return a * b * c;
  }
}

Problem #10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

At this point, I began to worry about the size of my primes array. I wrote a second function that follows the same steps, except that it tries each number from two up to the square root of the candidate, instead of just the primes, and doesn’t store any numbers in an array. Even so, in Firefox 3.0.11 I got multiple warnings that I had to click “Continue” on to keep the script running until it calculated the answer (which it did sucessfully). In Firefox 3.5, however, with its vastly improved TraceMonkey JavaScript engine, it completes in a few seconds with no warnings. Safari and Chrome ought to do it near-instantly—the SquirrelFish engine in WebKit is even faster than TraceMonkey. I haven’t tested that, though. The code is very simple.

// Project Euler: #10
var sum = 0;

for (var p = 2; p < 2000000; p = altFindNextPrime(p)) {
  sum += p;
}

return s;

I’d love to hear any comments on how to improve my solutions here. I’ll keep working and keep posting about the next set of problems, and maybe come back to these if I find better ways of doing them.