How to find the 5th perfect number (which is 33550336)? The problem is taking forever to run

Let's check the properties of a perfect number. This Math Overflow question tells us two very interesting things:

  1. A perfect number is never a perfect square.
  2. A perfect number is of the form (2k-1)×(2k-1).

The 2nd point is very interesting because it reduces our search field to barely nothing. An int in Java is 32 bits. And here we see a direct correlation between powers and bit positions. Thanks to this, instead of making millions and millions of calls to isPerfectNumber, we will be making less than 32 to find the 5th perfect number.

So we can already change the search field, that's your main loop.

    int count = 0;
    for (int k = 1; count < 5; k++) {

      // Compute candidates based on the formula.
      int candidate = (1L << (k - 1)) * ((1L << k) - 1);

      // Only test candidates, not all the numbers.
      if (isPerfectNumber(candidate)) {
        count++;
        System.out.println(candidate);
      }
    }

This here is our big win. No other optimization will beat this: why test for 33 million numbers, when you can test less than 100?

But even though we have a tremendous improvement, your application as a whole can still be improved, namely your method isPerfectNumber(int).

Currently, you are still testing way too many numbers. A perfect number is the sum of all proper divisors. So if d divides n, n/d also divides n. And you can add both divisors at once. But the beauty is that you can stop at sqrt(n), because sqrt(n)*sqrt(n) = n, mathematically speaking. So instead of testing n divisors, you will only test sqrt(n) divisors.

Also, this means that you have to start thinking about corner cases. The corner cases are 1 and sqrt(n):

  • 1 is a corner case because you if you divide n by 1, you get n but you don't add n to check if n is a perfect number. You only add 1. So we'll probably start our sum with 1 just to avoid too many ifs.
  • sqrt(n) is a corner case because we'd have to check whether sqrt(n) is an integer or not and it's tedious. BUT the Math Overflow question I referenced says that no perfect number is a perfect square, so that eases our loop condition.

Then, if at some point sum becomes greater than n, we can stop. The sum of proper divisors being greater than n indicates that n is abundant, and therefore not perfect. It's a small improvement, but a lot of candidates are actually abundant. So you'll probably save a few cycles if you keep it.

Finally, we have to take care of a slight issue: the number 1 as candidate. 1 is the first candidate, and will pass all our tests, so we have to make a special case for it. We'll add that test at the start of the method.

We can now write the method as follow:

  static boolean isPerfectNumber(int n) {
    // 1 would pass the rest because it has everything of a perfect number
    // except that its only divisor is itself, and we need at least 2 divisors.
    if (n < 2) return false;
   

    // divisor 1 is such a corner case that it's very easy to handle:
    // just start the sum with it already.
    int sum = 1;

    // We can stop the divisors at sqrt(n), but this is floored.
    int sqrt = (int)Math.sqrt(n);

    // A perfect number is never a square.
    // It's useful to make this test here if we take the function
    // without the context of the sparse candidates, because we
    // might get some weird results if this method is simply
    // copy-pasted and tested on all numbers.
    // This condition can be removed in the final program because we
    // know that no numbers of the form indicated above is a square.
    if (sqrt * sqrt == n) {
      return false;
    }
    
    // Since sqrt is floored, some values can still be interesting.
    // For instance if you take n = 6, floor(sqrt(n)) = 2, and
    // 2 is a proper divisor of 6, so we must keep it, we do it by
    // using the <= operator.
    // Also, sqrt * sqrt != n, so we can safely loop to sqrt
    for (int div = 2; div <= sqrt; div++) {
      if (n % div == 0) {
        // Add both the divisor and n / divisor.
        sum += div + n / div;
        // Early fail if the number is abundant.
        if (sum > n) return false;
      }
    }
    return n == sum;
  }

These are such optimizations that you can even find the 7th perfect number under a second, on the condition that you adapt the code for longs instead of ints. And you could still find the 8th within 30 seconds.

So here's that program (test it online). I removed the comments as the explanations are here above.

public class Main {
  public static void main(String[] args) {
    int count = 0;
    for (int k = 1; count < 8; k++) {
      long candidate = (1L << (k - 1)) * ((1L << k) - 1);
      if (isPerfectNumber(candidate)) {
        count++;
        System.out.println(candidate);
      }
    }
  }

  static boolean isPerfectNumber(long n) {
    if (n < 2) return false;
    long sum = 1;
    long sqrt = (long)Math.sqrt(n);
    for (long div = 2; div <= sqrt; div++) {
      if (n % div == 0) {
        sum += div + n / div;
        if (sum > n) return false;
      }
    }
    return n == sum;
  }
}

The result of the above program is the list of the first 8 perfect numbers:

6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128

You can find further optimization, notably in the search if you check whether 2k-1 is prime or not as Eran says in their answer, but given that we have less than 100 candidates for longs, I don't find it useful to potentially gain a few milliseconds because computing primes can also be expensive in this program. If you want to check for bigger perfect primes, it makes sense, but here? No: it adds complexity and I tried to keep these optimization rather simple and straight to the point.


There are some heuristics to break early from the loops, but finding the 5th perfect number still took me several minutes (I tried similar heuristics to those suggested in the other answers).

However, you can rely on Euler's proof that all even perfect numbers (and it is still unknown if there are any odd perfect numbers) are of the form:

2i-1(2i-1)

where both i and 2i-1 must be prime.

Therefore, you can write the following loop to find the first 5 perfect numbers very quickly:

int counter = 0,
i = 0;

while (counter != 5) {
    i++;
    if (isPrime (i)) {
        if (isPrime ((int) (Math.pow (2, i) - 1))) {
            System.out.println ((int) (Math.pow (2, i -1) * (Math.pow (2, i) - 1)));
            counter++;
        }
    }
}

Output:

6
28
496
8128
33550336

You can read more about it here.

If you switch from int to long, you can use this loop to find the first 7 perfect numbers very quickly:

6
28
496
8128
33550336
8589869056
137438691328

The isPrime method I'm using is:

public static boolean isPrime (int a)
{
  if (a == 1)
    return false;
  else if (a < 3)
    return true;
  else {
    for (int i = 2; i * i <= a; i++) {
      if (a % i == 0)
        return false;
    }
  }
  return true;
}

Tags:

Java

Recent Posts