Smart algorithm for finding perfect numbers

Question

Is there an algorithm that is quicker than O(N^2) for finding perfect numbers from a sample 1:N? Or any general speed improvements to do less computation? I know we can remove odd numbers from the sample if we assume they are not perfect (unproven but we can assume it here regardless).

You could use the [Euclid-Euler theorem](https://en.wikipedia.org/wiki/Euclid%E2%80%93Euler_theorem) for a substantial speed-up (albeit one that would require non-trivial programming to achieve). — John Coleman, Aug 26 '22 at 13:52

Riccardo Bucco · Accepted Answer · 2022-11-09T09:37:32.947

1

Here is a way to do it (num is your number):

if sum(i for i in range (1, num) if num % i == 0) == num:
    print(num, "is a perfect number")
else:
    print(num, "is not a perfect number")

EDIT (credits: @cdlane)

There is a one-to-one correspondence between the Mersenne primes and the even perfect numbers. You can use this fact to generate Mersenne primes with the Lucas–Lehmer primality test and get eventually a perfect number:

def lucas_lehmer(p):
    s = 4
    m = 2 ** p - 1
    for _ in range(p - 2):
        s = ((s * s) - 2) % m
    return s == 0

def is_prime(number):
    if number % 2 == 0:
        return number == 2
    i = 3
    while i * i <= number:
        if number % i == 0:
            return False
        i += 2
    return True

for num in range(3, N, 2):
    if is_prime(num) and lucas_lehmer(num):
        print(2 ** (num - 1) * (2 ** num - 1), "is a perfect number")

Output (with N=500):

28 is a perfect number
496 is a perfect number
8128 is a perfect number
33550336 is a perfect number
8589869056 is a perfect number
137438691328 is a perfect number
2305843008139952128 is a perfect number
2658455991569831744654692615953842176 is a perfect number
191561942608236107294793378084303638130997321548169216 is a perfect number
13164036458569648337239753460458722910223472318386943117783728128 is a perfect number
14474011154664524427946373126085988481573677491474835889066354349131199152128 is a perfect number

edited Nov 09 '22 at 09:37

answered Aug 26 '22 at 13:39

Riccardo Bucco

13,980
4
22
50

This is a slow method. it can already be made faster by checking if num is odd, since there are no odd perfect numbers – fvim Aug 26 '22 at 13:40
@fvim The complexity is the same. And it's been never proved that there are no odd perfect numbers ;) – Riccardo Bucco Aug 26 '22 at 13:41
The question isn't clear but I think that it is asking for a way to find all perfect numbers in 1 to N in a way that is better than O(N^2). If you use this in a naive loop it is O(N^2). – John Coleman Aug 26 '22 at 13:42
Yes you are right it has not been proven, but for something like 1:10^10 ? – fvim Aug 26 '22 at 13:43
@JohnColeman Then I think it's impossible, because of the very close relationship that perfect numbers have with prime numbers. Or at least such a solution is not known yet – Riccardo Bucco Aug 26 '22 at 13:43
@RiccardoBucco I only have what you posted, minus the odd numbers – fvim Aug 26 '22 at 13:45
1

@fvim you can slightly improve things by using these answers to compute factors in a faster way: https://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python – Riccardo Bucco Aug 26 '22 at 13:47
This is absolutely the wrong way to go about finding Perfect Numbers. You can greatly improve your results by searching for Mersenne primes using a Lucas–Lehmer primality test and then finding their companion Perfect Number. Although it will eventually become computationally problematic, you will have generated many more Perfect Numbers than this approach which bottoms out quickly. – cdlane Nov 08 '22 at 17:59
@cdlane Thanks for your very very useful comment, I updated my answer with your suggestions :) – Riccardo Bucco Nov 09 '22 at 09:39
@cdlane oh sorry I did not know you posted exactly the same answer, I wrote mine without even looking at it – Riccardo Bucco Nov 09 '22 at 09:41

score 1 · Answer 2 · answered Nov 08 '22 at 18:15

You can get a significant improvement by not searching for perfect numbers but rather search for Mersenne primes, and then output their companion perfect number:

def lucas_lehmer_test(p):
    s = 4
    m = 2 ** p - 1
    for _ in range(p - 2):
        s = ((s * s) - 2) % m
    return s == 0

def is_odd_prime(number):
    """
    Efficiency of this doesn't matter as we're only using it to
    test primeness of exponents not the mersenne primes themselves
    """

    i = 3

    while i * i <= number:
        if number % i == 0:
            return False
        i += 2

    return True

print(6)  # to simplify code, treat first perfect number as a special case

for n in range(3, 5000, 2):  # generate up to M20, found in 1961
    if is_odd_prime(n) and lucas_lehmer_test(n):
        print(2**(n - 1) * (2**n - 1))

Not perfect, but far better than trying to factor numbers looking for perfect ones.

Smart algorithm for finding perfect numbers

2 Answers2