There is a direct relationship between perfect numbers and the Mersenne prime numbers . A prime number of Mersenne is nothing more than a prime number that can be written in the form M n = 2 n - 1, for given n integer, and the relation of the perfect numbers is a power of 2. It is worth emphasizing in the answer that the concepts applied here are valid for only perfect even numbers, but the solution holds true given the fact that no perfect perfect number is known yet by mathematics - on the day they find out I edit the solution, I promise.
Thus, given a prime number of Mersenne M n = 2 n -1, we can obtain the perfect number by making P n = (2 n-1 ) (2 n -1).
- P n = 1 = (2 1-1 ) (2 1 - 1) = 1
(2 2 - 1) = 6
(2 3 - 1) = 28
(2 4 - 1) = 120
(2 5 - 1) = 496
- ...
Notice that when 2 n - 1 is not prime, in cases of n = 1 and n = 4, the result will not be a perfect number. So the first challenge of this approach is to ensure that we have a prime number as 2 n - 1.
And this challenge is very easy to solve. Mathematically, we can define that 2 n - 1 is a prime number and, by the way, we solve our problem. However, by solving one, another appears: but 2 n - 1 is a cousin of Mersenne?
To ensure that the prime number P n = 2 n - 1 is a Mersenne prime, there must be an integer value
n that validates the expression. That is, if there is a
n such that n = log 2 (P n +1) is integer, then P n will be a cousin of Mersenne.
The approach will then be to go through the list of prime numbers, check if it is a Mersenne cousin, and when it does, calculate its perfect number. With luck, we already know how to calculate primes efficiently
So just go through those values and see which are Mersenne's cousins, calculating the perfect number:
# Percorre a lista de números primos menores que N:
for prime in sieve_of_eratosthene(N):
# Calcula o valor de n que define o Pn:
n = math.log2(prime+1)
# Verifica se n é inteiro, sendo um primo de Mersenne:
is_mersenne = n.is_integer()
# Se for um primo de Mersenne, calcula o número perfeito:
if is_mersenne:
print(2**(n-1) * prime)
See working at Repl.it | Ideone | GitHub GIST
So by testing here, it took about 34 seconds to figure out the perfect number 137438691328. Above this I started having memory problems, which I will try to solve soon.
Additional references
Two videos I recommend watching on the subject are:
Looking to optimize the code, I was able to do without using Sieve. Basically what the code does is define a generator that returns all the prime numbers of Mersenne by checking if the number is prime and using the Lucas-Lehmer Primality Test .
def is_prime(number):
# Condição para number=2 ignorada propositalmente, visto que a menor entrada será 3
i = 3
while i**2 <= number:
if number % i == 0:
return False
i += 2
return True
def lucas_lehmer(p):
s = 4
M = 2**p - 1
for _ in range(p - 2):
s = ((s * s) - 2) % M
return s == 0
def mersenne_primes():
p = 3
while True:
if is_prime(p) and lucas_lehmer(p):
yield (p, 2**p - 1)
p += 2
To use it, for example, searching for the first 10 perfect numbers, just do:
numbers = mersenne_primes()
for _ in range(10):
p, mersenne = next(numbers)
perfect = 2**(p-1) * mersenne
print(perfect)
See working at Repl.it | Ideone | GitHub GIST
Some results I got:
- For the top 10 perfect numbers: 0.0003993511199951172s
- For 15 first perfect numbers: 1.9178969860076904s
- For the 16 first perfect numbers: 6.957615613937378s
- For 17 first perfect numbers: 28.416791677474976s
- For 18 first perfect numbers: 78.89492082595825s
- For 19 first perfect numbers: 93.7487268447876s
For 20 I was too lazy to wait.
