Finding Divisors of Even Perfect Numbers Efficiently

In this post, I’ll discuss an efficient algorithm for finding the divisors of even perfect numbers in $O(log N)$ time. Since no odd perfect numbers are known, this method specifically applies to even ones.

Here’s the pseudocode for the algorithm:

Require: An integer p representing the Mersenne exponent  
Ensure: A list of proper divisors of the even perfect number associated with p  

Initialize an empty list `divisors`  
Set `value` to 1  
Append `value` to `divisors`  

for i = 1 to p − 1 do  
    `value ← value × 2`  
    Append `value` to `divisors`  
end for  

Set `mersenne_prime` to `(value × 2) − 1`  
Append `mersenne_prime` to `divisors`  

Set `value` to `mersenne_prime`  
for i = 1 to p − 2 do  
    `value ← value × 2`  
    Append `value` to `divisors`  
end for  

Return `divisors`  

This approach leverages the structure of even perfect numbers, which are always of the form $2^{p-1} \times (2^p - 1)$ when $2^p - 1$ is a Mersenne prime.
By iterating through the powers of $2$ up to $p-1$ and then incorporating the Mersenne prime factor, we efficiently generate all divisors in logarithmic time.