Improve code for finding perfect numbers

JavaScript
1

I have a script to calculate perfect numbers. It’s an exercise in using web workers. It finds the first 4 perfect numbers in no time and the 5th in about 8 minutes, but it has yet to find the 6th despite running for over 2 hours.

Can I make my code more efficient? I don’t think I can expect it to come up with the 7th perfect number, but I would be happy if I can speed it up enough to find the 6th.

This is the worker code:

// Find perfect numbers
// ====================

let n = 1;  // number to check
while (true) {
  n++;
  let nr2 = Math.floor(Math.sqrt(n)),
    j = 1;  // sum of factors
  for (let i = 2; i <= nr2; i++) {
    if (n % i === 0) {
      j += i + n / i;  // if i is a factor, so is n/i
    }
  }
  if (n === j) {
    postMessage(n);
    console.log(Date());
  }
}
2

I guess the most CPU-expensive operation here is Math.sqrt(), so I’d search for another calculation algorithm which doesn’t use square roots.

Here is a good place to start:

1 Like
3

sqrt takes time and so does the modulus operator.
Instead of finding divisors of numbers which is time consuming I would investigate going the reverse.
1 is always going to be a factor so it always needs to be included.
I also seem to think that there will be an odd number of factors, because of including 1.
Testing factors by first adding them and then dividing the sum of the trial-factors by each trial-factor seems more efficient. For a seven factor test: 1 is a factor by default.
if the number is even dividing it by 2 should give the highest factor as the quotient. So only half of the factors need to be used as a divisor.
Perfect numbers are expected to be always even. No odd perfect number has been discovered Then 1 and 2 are the first two factors and there must be an even number of odd factors. No perfect number can be a square so an odd number of trial factors must be added to 1 & 2.
Finally would recursion be better than several levels of looping?
Hope this helps.

1 Like
4

Thanks for the ideas, guys. :slight_smile:

5

According to the text books all known perfect numbers can be expressed by 2^(p-1)(2^p - 1) ie 2 to the power of (p-1) multiplied by (2 to the power of p) -1
Where p is a prime number.
eg. for 5:
2^4 = 16
2^5 - 1 = 31
and 16 x 31 = 496 which is a perfect number
16 and 31 are factors of 496
2^p is an even number so divide it by 2 to get the other factor that pairs with 2.
while the quotient is even then multiply the divisor by 2 and repeat until an odd number is returned.
Then repeat with the other prime numbers.
You could also filter further by requiring (2^p) -1 to be prime.

This should help to find perfect number candidates.

2 Likes
6

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.