5
\$\begingroup\$

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 < 2) {
    throw new TypeError(`First parameter is expected to a ` +
                      `number larger then 1 which is not NaN.`);
  }

  while (currentTry <= upperLimit) {  // <------- Start outer loop
    divisor = 2;
    sum = 0;

    while (currentTry >= divisor) {   // <------- Start inner loop
      let fraction = currentTry / divisor;
      let leftOver = currentTry % divisor;

      if (leftOver === 0) {
        sum += fraction;
      }

      divisor++;
    }                                 // <-------- End inner loop

    if (sum === currentTry) {
      perfectNumbers.push(currentTry);
    }

    currentTry++;
  }                                   // <-------- End outer loop

  return perfectNumbers;
}

// ------------ Demo ... --------------------------
console.log(findPerfectNumbers(1000));               // Returns : [6, 28, 496]
console.log(findPerfectNumbers(8140, 8100));         // [8128]
console.log(findPerfectNumbers(33550340, 33550335)); // [33550336]

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:

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

  2. 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.

\$\endgroup\$
5
\$\begingroup\$

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:

  1. For a prime \$p\$
  2. Calculate \$m = 2^p-1\$
  3. If \$m\$ is prime, it's a Mersenne prime
  4. 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.

\$\endgroup\$
2
\$\begingroup\$

A few things to note about perfect numbers:

  • Although this has not been proven, it is highly likely that there are no odd perfect numbers. There are definitely no odd perfect numbers in the range your program will operate on. Let's assume a number is not perfect if it's not even.

  • All even perfect numbers have either \$6\$ or \$8\$ for their last digit.

  • All even perfect numbers are triangular numbers, viz. numbers of form \$\frac{i*(i+1)}{2}\$


Here is a revised version of your code, after applying the above "lemmas":

function isPerfect(n) {
  // Note that due to short-circuit evaluation, as soon as
  // one of these functions returns `false`, the result of
  // boolean multiplication (aka AND aka &&) is false, and
  // therefore other functions don't have to be be called.
  // This saves a *lot* of time, because for example
  // 8 out of 10 numbers do not end with 6 or 8.
  return endsWithSixOrEight(n)
      && isTriangular(n)
      && isReallyPerfect(n);
}

function endsWithSixOrEight(n) {
  const lastDigit = n % 10;
  return (lastDigit === 6) || (lastDigit === 8);
}

function isTriangular(n) {
  // `triBase` is the `i` in above formula for triangular numbers;
  // `n` is the possible "result" of that formula.
  // This function checks whether it actually is or not.
  // i * (i+1) / 2 = n
  // i * (i+1) = n * 2
  // i ≈ √(n * 2)
  // i = ⌊ √(n * 2) ⌋
  const triBase = Math.floor(Math.sqrt(n * 2));
  const triangular = triBase * (triBase+1) / 2;
  return n === triangular;
}

function isReallyPerfect(n) {
  // Every number is divisible by 1 (and itself),
  // so the initial sum is 1.
  let sum = 1;
  let divisor = 1;

  // You don't have to divide `n` by `d` if `d` is greater than n / 2,
  // because the result would be less than 2 (either a decimal, or 1 –
  // – which we already have added to the sum).
  // Furthermore, you can divide `n` by each number from 2 up to its
  // square root and add both the divisor _and_ the quotient to the sum.
  const maxdiv = Math.floor(Math.sqrt(n));

  // In this loop, you can check whether the sum is less than `n`.
  // If is' not, you're done – if it's equal to `n`, it _might_ be
  // perfect, if it's greater than `n`, you know it's not.
  while (++divisor <= maxdiv && sum < n) {
    if (n % divisor === 0) {
      sum += divisor + (n / divisor);
    }
  }

  return sum === n;
}

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

  if (typeof upperLimit !== 'number' || isNaN(upperLimit) || 
          upperLimit < 2) {
    throw new TypeError(`First parameter is expected to a ` +
                      `number larger then 1 which is not NaN.`);
  }

  while (currentTry <= upperLimit) {
    if (isPerfect(currentTry)) {
      perfectNumbers.push(currentTry);
    }
    currentTry++;
  }

  return perfectNumbers;
}

There are many possibilities for further optimization. Flambino's approach offers a good example, and incidentally the biggest bottleneck of his approach is the same as of this – factorization. Whether it's factorization of a prime or a perfect number.

\$\endgroup\$
  • \$\begingroup\$ Absolutely awesome answers. Once again: Can accept only one answer. But both are definitely helpful. Thank you both for your efforts answering. \$\endgroup\$ – michael.zech Apr 4 '17 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.