On the Euclid-Euler Theorem - benjamintoll.com

The other day I was on the Internets and I came across a problem that greatly interested me. The problem itself wasn’t difficult to solve, but the optimal solution was so clever I felt compelled to look into it further. The combination of math, history and code is just too much, and I lost control.

The problem: Write a function that returns true when a number is a perfect number.

My approach was a typical brute force; iterate through the range of numbers up to and including the square root of n.

const is_perfect = num => {
    const half = num / 2 >> 0;
    let res = 0;

    for (let i = 1; i <= half; i++) {
        if (num % i === 0) {
            res += i;
        }
    }

    return res === num;
};

// The first four perfect numbers.
[6, 28, 496, 8128]
.forEach(num =>
    console.log(
        is_perfect(num)
    )
);

This isn’t bad, and its complexity analysis is as follows:

Time complexity: O(√n), i.e., only iterate over the range 1 < i ≤ √num
Space complexity: O(1)

However, there is a solution that is faster, and has ancient origins.

First, it is necessary to understand that the list of known perfect numbers is ridiculously small, only fifty at the time of this writing. Here are the first eight:

6
28
496
8128
33550336
8589869056
137438691328

Second, there is a special kind of prime number known as a Mersenne prime, and there are also only 50 known Mersenne primes. Coincidence? Who knows!¹. Here are the first eight:

3
7
31
127
8191
131071
524287
2147483647

Named after the French polymath and ascetic Marin Mersenne, this is a prime number that is one less than a power of two.

Here is the definition:

2^p - 1

(p is also a prime number)

Beware, however, that not all numbers of the form 2^p − 1 with a prime p are prime (i.e., 2¹¹ − 1)!

Kool Moe Dee!

As you’ve probably guessed, it’s not coincidence at all. There is a one-to-one correspondence between even perfect numbers and Mersenne primes, which was proved by Euclid around 300 BCE in his famous mathematical treatise the Elements. He showed that if 2^p - 1 is a prime number, then 2^{p - 1} (2^p - 1) is a perfect number. Leonhard Euler, 20 centuries later and on a different continent, proved that the formula applies to all even perfect numbers. This is the Euclid-Euler Theorem.

Let’s look at the relationship between the two:

Legend: P = Prime number MP = Mersenne prime number

P	2^p - 1	MP	2^{p - 1} (2^p - 1)	Perfect Number
2	2² - 1	3	2^{2 - 1} (2² - 1)	6
3	2³ - 1	7	2^{3 - 1} (2³ - 1)	28
5	2⁵ - 1	31	2^{5 - 1} (2⁵ - 1)	496
7	2⁷ - 1	127	2^{7 - 1} (2⁷ - 1)	8128
13	2¹³ - 1	8191	2^{13 - 1} (2¹³ - 1)	33550336
17	2¹⁷ - 1	131071	2^{17 - 1} (2¹⁷ - 1)	8589869056
19	2¹⁹ - 1	524287	2^{19 - 1} (2¹⁹ - 1)	137438691328
31	2³¹ - 1	2147483647	2^{31 - 1} (2³¹ - 1)	2305843008139952128

All the known even perfect numbers end in either 6 or 8!

Ok, now that we see the relationship between even perfect numbers and Mersenne primes, let’s rewrite the algorithm to take advantage of this.

const euclid_euler = p =>
    (1 << p - 1) * ((1 << p) - 1)

const is_perfect = num =>
    [2, 3, 5, 7, 13, 17, 19, 31]
    .some(p =>
    euclid_euler(p) === num
    );

[6, 28, 496, 8128]
.forEach(p =>
    console.log(
        is_perfect(p)
    )
);

Because we now know that the eight primes in the list in the code can generate even perfect numbers, we can simply use them to generate a perfect number with which we then compare the value passed into our is_perfect function. And as a bonus, there’s some nifty bit shifting going down. Weeeeeeeeeeeeeeeeeeeeeeeeee

Now, the complexity analysis is:

Time complexity: O(log n)
Space complexity: O(log n)

It’s faster, though it will take more memory. I think that’s an acceptable trade-off.

¹ The Shadow knows.