Problem029.js

/*
Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
*/

function isPrime(number) {
  if (number<2) return false;
  for (var i=2; i<=Math.sqrt(number); i++) {
    if (number%i==0) return false;
  }
  return true;
}
// Primes up to 100
var primes = [];
for (var i=2; i<100; i++) if (isPrime(i)) primes.push(i);

function decompose(number) {
  var ret = [];
  for (var i=0; primes[i]<=number && i<primes.length; i++) {
    if (number%primes[i]==0) {
      number = number/primes[i];
      if (ret[i]) { ret[i]++; }
      else { ret[i] = 1; }
      i = -1;
    }
  }
  return ret;
}

var terms = [];
for (var a=2; a<=100; a++) {
  for (var b=2; b<=100; b++) {
    var aux = decompose(a);
    for (var i=0; i<aux.length; i++) if (aux[i]) aux[i] *= b;
    // Check for existence
    var alreadyExists = false;
    for (var i=0; i<terms.length && !alreadyExists; i++) {
      if (terms[i].length != aux.length) continue;
      alreadyExists = true;
      for (var j=0; j<aux.length && alreadyExists; j++) {
        alreadyExists = terms[i][j]==aux[j];
      }
    }
    if (!alreadyExists) terms.push(aux);
  }
}

console.log(terms.length);
// 9183