CODEWITHSUNDEEP
javascript
Jerome
Jerome

Reputation: 870

Project Euler #29: Why is my answer off by 37?

I am working on Problem 29:

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

I have done a brute force solution with a filter:

var main = function() {

    var arr = [];

    for (var a = 2; a <= 100; a++) {
        for (var b = 2; b <= 100; b++) {
            arr.push(BigInt(Math.pow(a, b)));
        }
    }
    //arr.sort((a, b) => a - b);

    return arr.filter(function(elem, pos) {
        return arr.indexOf(elem) == pos;
    }).length;
}

console.log(main());

My program executes fine. Although the result I am getting is 9220 where as the correct answer is 9183. What am I missing here?

Upvotes: 2

Views: 695

Answers (3)

CertainPerformance
CertainPerformance

Reputation: 370979

The problem is that

BigInt(Math.pow(a, b))

Even with BigInt, the expression inside it gets evaluated before it gets passed to BigInt, and Javascript cannot precisely handle huge numbers. The behavior looks to be browser-dependent, unfortunately, the problem is not sufficiently reproducible on every environment.

For a cross-browser solution, you'll have to find another method, like finding the distinct factors of each number, and filtering out numbers with duplicate factor counts. (eg, 2^4's prime factors are 2x2x2x2, same as 4^2 - filter out all such duplicates.)

For example:

const isPrime = num => {
  for(let i = 2; i < num; i++)
    if(num % i === 0) return false;
  return num > 1;
}
const primes = Array.from(
  { length: 100 },
  (_, i) => i + 1
).filter(isPrime);

const addPrimesToObj = (num, prime, obj) => {
  while ((num / prime) % 1 === 0) {
    obj[prime] = (obj[prime] || 0) + 1;
    num = num / prime;
  }
  return num;
};
var main = function() {
  const factorsSet = new Set();
  for (let a = 2; a <= 100; a++) {
    for (let b = 2; b <= 100; b++) {
      const theseFactors = {};
      for (let i = 0; i < b; i++) {
        let innerA = a;
        primes.forEach((prime) => {
          innerA = addPrimesToObj(innerA, prime, theseFactors);
        });
      }
      const factorsStr = Object.entries(theseFactors)
        .map(([key, val]) => `${key}-${val}`)
        .join('_');
      factorsSet.add(factorsStr);
    }
  }
  return factorsSet.size;
}

console.log(main());

Upvotes: 1

Kamil Kiełczewski
Kamil Kiełczewski

Reputation: 92517

BigInt have sufficient (arbitrary) precision (support by chrome)

var main = function() {

    var arr = [];

    for (var a = 2; a <= 100; a++) {
        var p= BigInt(a);
        for (var b = 1; b <= 100; b++) {
            if(b>=2) arr.push(p);
            p=p*BigInt(a);
        }
    }

    return arr.filter(function(elem, pos) {
        return arr.indexOf(elem) == pos;
    }).length;
}

console.log(main());

Upvotes: 1

ellipsis
ellipsis

Reputation: 12152

Convert the array to a set, all duplicates will be removed automatically. Return the size of the set

var main = function() {

    var arr = [];

    for (var a = 2; a <= 100; a++) {
        for (var b = 2; b <= 100; b++) {
            arr.push(BigInt(Math.pow(a, b)));
        }
    }
    //arr.sort((a, b) => a - b);

   var e=new Set(arr);
   return e.size()
}

console.log(main());

Upvotes: -1

Related Questions