JavaScript function for finding perfect numbers

The following function has been created for finding "Perfect Numbers".

About Perfect Numbers: Wikipedia



`function findPerfectNumbers(upperLimit, currentTry = 2) {
let perfectNumbers = [];
let divisor;
let sum;

if (typeof upperLimit !== 'number' || isNaN(upperLimit) ||
upperLimit = divisor) { //



It finds the first five Perfect Numbers. So I suppose my algorithm is basically correct.

But practically it doesn't work well.

Currently, it has a runtime complexity of \$O(n^2)\$. Therefore it becomes practically unusable from the fourth Perfect Number on upwards.

Therefore my question to the programmers who are more advanced than me:

-
Is there a way to improve the runtime complexity of the function?

-
If it isn't possible to change the algorithm, are there performance tricks one could use? like for example using shift operators instead of arithmetic operators?

All hints, comments, and tips concerning the points described above and the function in general appreciated.

If you check the wikipedia article you linked, you'll see the following:


It was not until the 18th century that Leonhard Euler proved that the formula \$2^{p−1}(2^p − 1)\$ will yield all the even perfect numbers. Thus, there is a one-to-one correspondence between even perfect numbers and Mersenne primes; each Mersenne prime generates one even perfect number, and vice versa. This result is often referred to as the Euclid–Euler theorem.

A Mersenne prime is a prime that's constructed from \$2^p−1\$, where \$p\$ is prime. Not all values of \$p\$ produce a Mersenne prime, but it makes for much simpler code for finding perfect numbers:

• For a prime \$p\$

• Calculate \$m = 2^p-1\$

• If \$m\$ is prime, it's a Mersenne prime

• And thus \$2^{p-1}m\$ is a perfect number

So you'll want code to generate prime numbers, and code to check whether a number is prime.

There are a bunch of ways to generate primes (like this for starters) but for illustration let's use the simplest way: Loop through numbers, and check if they're prime. That's also the same feature we'll need later to check for Mersenne primes anyway.

const isPrime = (n) => {
  const limit = Math.sqrt(n);
  for(var i = 2 ; i <= limit ; i++) {
    if(n % i === 0) return false;
  }
  return true;
}

I.e. if a number is divisible by anything between 2 and its own square root, it's not prime.

Now, let's use that to generate, say, 10 primes:

const primes = [];
var i = 2;
while(primes.length < 10) {
  if(isPrime(i)) primes.push(i);
  i++;
}

So now we have 10 primes. Again, this is a very naïve way to do things, but it works for illustrative purposes.

So now, we can loop through those primes, and use them to construct Mersenne primes (sometimes), and from there, perfect numbers:

primes.forEach(p => {
  const m = Math.pow(2, p) - 1; // calculate 2^p - 1

  if(!isPrime(m)) {
    return; // go to next prime if m isn't a (Mersenne) prime
  }

  // calculate and print the perfect number
  const perfectNumber = Math.pow(2, p - 1) * m;
  console.log(perfectNumber);
});

Another way to write (and get an array back) might be:

const perfectNumbers = primes
  .map(p => { return {p: p, m: Math.pow(2, p) -1} })
  .filter(pair => isPrime(pair.m))
  .map(pair => pair.m * Math.pow(2, pair.p - 1));

Point is, from the first 10 primes you get the first 7 perfect numbers:

6
28
496
8128
33550336
8589869056
137438691328

in a few milliseconds.

So that's cool. But don't overdo it; this is not a simple problem. Wikipedia notes that only 49 Mersenne primes are known to date (the largest has 44,677,235 digits!) and thus only 49 perfect numbers. And in JavaScript, things will go wrong long before that: Since all JS numbers are 64-bit floats they simply can't hold large enough values.

The largest integer that a JS number can hold without introducing floating point errors is Number.MAX_SAFE_INTEGER, which is 9,007,199,254,740,991. Pretty big, sure, but only big enough for the first 7 perfect numbers listed above. The 8th should be 2,305,843,008,139,952,128 but the closest JS can do is 2,305,843,008,139,952,000. Oh well.

You might try looking just for the many-orders-of-magnitude-smaller Mersenne primes, and skip the actual calculation of the corresponding perfect number. If you have a Mersenne, you have a perfect number, after all. Unfortunately though, the 8th Mersenne prime is already \$2^{61} - 1\$ and thus too big to store. So in regular JS, you'll have to be happy with the first 7 Mersenne primes/perfect numbers.

StackExchange Code Review Q#159723, answer score: 5