Efficiency in Perfect number code (Python)

Question

n = int(input())
sum1 = 0
for i in range(1, n//2  + 1):
    if(n % i == 0):
        sum1 = sum1 + i
if (sum1 == n):
    print("YES")
else:
    print("NO")

this is my code to check a number is perfect or not in python, it's giving correct output, but when i try submitting it on website (codechef) I get a timeout. how can i make this more efficient?

the error is:

Status: time limit exceeded

Answer 1

I kind of struggled with this one too, but I was doing the problem here on leetcode. The best solution I could come up with myself was this (adapted for your case):

divs = []
for i in range(1, int(n**0.5 + 1)): 
    if (n % i == 0) and n != i: 
        divs.append(i)
        divs.append(n/i)

print('YES') if sum(divs) - n == n else print('NO')
    

It took me a while to get to but sites like leetcode let you test solutions very easily so you can play around with different approaches. Plus you can look on the solutions or discussions tab to find answers better than what you have so you can improve.

Answer 2

If you add the divisor's counterpart each time you find a divisor, you will only need to scan numbers up to the square root of n. :

def isPerfect(N):
    return N == (N>1) + sum(d+N//d for d in range(2,int(N**0.5)+1) if N%d==0)

isPerfect(137438691328) # True 

isPerfect(10**14) # False

An even faster method is to generate divisors based on the prime factors of the number:

def primeFactors(N):
    while not N&1:yield 2;N//=2
    p = 3
    while p*p<=N:
        while not N%p: yield p;N//=p
        p+=2
    if N>1: yield N

def isPerfect(N):
    divisors = {1}
    for p in primeFactors(N):
        divisors.update([d*p for d in divisors])
    return N == sum(divisors)-N

This will allow checking much larger numbers (as long as they have small enough prime factors):

isPerfect(2305843008139952128) # True (0.007 second my laptop)

isPerfect(10**25)              # False (0.002 second)

isPerfect(2658455991569831744654692615953842176) # True (125 seconds)

Answer 3

As @hivert points out, the solution below assumes that perfect numbers are even. In fact, it is not known whether any odd perfect number exists, however there is a lot of information pointing to there being no odd perfect numbers. (https://en.wikipedia.org/wiki/Perfect_number#Odd_perfect_numbers).

For starters, we must have N > 10¹⁵⁰⁰. With that, we will proceed with the even case.

An even number is perfect if it has the following form:

2^{p - 1} * (2^p - 1), where p is a Mersenne prime.

We will need a prime number checker handy to do this efficiently. Fortunately, this is a very popular topic and there are very many existing functions in the wild for doing this. For example, the answer provided @Alexandru to the question How to create the most compact mapping n → isprime(n) up to a limit N? is a very nice and straightforward python implementation. However, if we are going for pure speed, we will need to employ alternative methods, such as Miller Rabin. This is provided in the library sympy

And here is our very efficient perfect even number checker:

from sympy.ntheory import isprime
 
def IsPerfect(N):
    ## First get the number of 2's that divide N
    ## If there are none, the number is not perfect
 
    p = 0
 
    while N % 2 == 0:
        N = N >> 1
        p += 1
 
    if p == 0:
        return False
 
    q = 2**(p + 1) - 1
 
    if N != q:
        return False
 
    if isprime(N):
        return True
    else:
        return False

Here are some examples:

IsPerfect(137438691328)
True

IsPerfect(33550336)
True

## Note 11 is not Mersenne
2**(11 - 1) * (2**11 - 1)
2096128

IsPerfect(2096128)
False

IsPerfect(2658455991569831744654692615953842176) ## instant on my laptop
True

Here are all of the primes less than 100:

mersenne = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89]
not_mersenne = [11, 23, 29, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97]

[IsPerfect(2**(p - 1) * (2**p - 1)) for p in mersenne]
[True, True, True, True, True, True, True, True, True, True]

[IsPerfect(2**(p - 1) * (2**p - 1)) for p in not_mersenne]
[False, False, False, False, False, False, False, False, False, False, False, False, False, False, False]

Answer 4

I wrote a program that does a perfect number test which includes the Lucas Lehmer test:

def ffs(x):
    return (x&-x).bit_length()-1

def levelx(N, withstats=False):
  if N <= 1: return False
  temp = N
  newlevel = temp.bit_length()
  primetest = temp//(2**(ffs(temp)))
  offset = temp//primetest
  s = 4
  
  nextlevel = newlevel // 2
  
  check = temp // (2**nextlevel)

  prevtemp = 2**nextlevel

  if withstats == True:
    print (newlevel, newlevel, temp)
    print (newlevel, nextlevel+one, prevtemp)
 
        
  if (prevtemp & (prevtemp-1) == 0) and prevtemp != 0:
       if offset.bit_length() == primetest.bit_length():
          if ((primetest+1) & ((primetest+1)-1) == 0):
             for x in range(primetest.bit_length()-1):
               s = (s * s - 2) % primetest
               if withstats == True:
                  print(s)
               if s in [0,2]: return True
             return False
          else: return False
       else: return False

Sample Output:

      
In [8]: for x in range(2,2300): 
   ...:     if levelx((2**(x-1))*(2**x-1)) == True: 
   ...:         print(x) 
   ...:                                                                                                                                                         
2
3
5
7
13
17
19
31
61
89
107
127
521
607
1279
2203
2281