Como calcular números perfeitos de forma rápida? – python python-3.x for

Pergunta:


Estou tentando realizar um exercício para mostrar os números perfeitos presentes dentro de um determinado range, porém eu só consigo realizar tal feito até o quarto número perfeito. Se eu aumentar o range, ele acaba demorando muito tempo e não responde:

def perfeito(n_max):
    lista = []
    for n in range(1, n_max + 1):
        soma = 0
        for div in range(1, n):
            if n % div == 0:
                soma += div
        if n == soma:
            lista.append(n)
    return lista

Aqui definimos o range, neste caso 500, e ele retornará os 3 primeiros:

print(perfeito(500)) 

Conjunto números perfeitos: {6, 28, 496, 8128, 33550336, 8589869056, …}

Após o 4º número. não consigo mais exibir. Alguma dica de otimização para meu código?

Autor da pergunta HV Lopes

Existe uma relação direta entre os números perfeitos e os números primos de Mersenne. Um número primo de Mersenne nada mais é que um número primo que pode ser escrito na forma Mn = 2n – 1, para dado n inteiro, e a relação dele com os números perfeitos é uma potência de 2. Vale ressaltar na resposta que os conceitos aplicados aqui valem para, apenas, números perfeitos pares, porém a solução se mantém válida dado o fato que ainda não é conhecido pela matemática nenhum número perfeito ímpar – no dia que descobrirem eu edito a solução, prometo.

Assim, dado um número primo de Mersenne Mn = 2n – 1, podemos obter o respectivo número perfeito fazendo Pn = (2n-1) (2n – 1).

  • Pn=1 = (21-1) (21 – 1) = 1
  • Pn=2 = (22-1) (22 – 1) = 6
  • Pn=3 = (23-1) (23 – 1) = 28
  • Pn=4 = (24-1) (24 – 1) = 120
  • Pn=5 = (25-1) (25 – 1) = 496

Perceba que quando 2n – 1 não é primo, nos casos de n=1 e n=4, o resultado não será um número perfeito. Então o primeiro desafio desta abordagem é garantir que tenhamos como 2n – 1 um número primo.

E esse desafio é muito fácil resolver. Matematicamente, podemos definir que 2n – 1 é um número primo e, pronto, resolvemos o nosso problema. Porém, resolvendo um, aparece outro: mas 2n – 1 é um primo de Mersenne?

Para garantir que o número primo Pn = 2n – 1 seja um primo de Mersenne deve existir um valor inteiro n que valide a expressão. Ou seja, se existir um valor n tal que n = log2(Pn+1) seja inteiro, então Pn será um primo de Mersenne.

A abordagem consistirá, então, de percorrer a lista de números primos, verificar se é um primo de Mersenne e, quando for, calcular o respectivo número perfeito. Com sorte, nós já sabemos calcular os números primos de uma forma eficiente

Então basta percorrer esses valores e verificar quais são primos de Mersenne, calculando o número perfeito:

# 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)

Veja funcionando no Repl.it | Ideone | GitHub GIST

Assim, testando aqui, ele levou cerca de 34 segundos para calcular até o número perfeito 137438691328. Acima disso comecei a ter problemas com memória, que buscarei resolver em breve.

Referências adicionais

Dois vídeos que recomendo assistir sobre o assunto são:


Buscando otimizar o código, consegui fazer sem utilizar o Sieve. Basicamente o que o código faz é definir um gerador que retorna todos os números primos de Mersenne verificando se o número é primo e utilizando o teste de primalidade de Lucas-Lehmer.

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

Para utilizá-lo, por exemplo, buscando os 10 primeiros números perfeitos, basta fazer:

numbers = mersenne_primes()

for _ in range(10):
    p, mersenne = next(numbers)
    perfect = 2**(p-1) * mersenne
    print(perfect)

Veja funcionando no Repl.it | Ideone | GitHub GIST

Alguns resultados que obtive:

  • Para os 10 primeiros números perfeitos: 0.0003993511199951172s
  • Para os 15 primeiros números perfeitos: 1.9178969860076904s
  • Para os 16 primeiros números perfeitos: 6.957615613937378s
  • Para os 17 primeiros números perfeitos: 28.416791677474976s
  • Para os 18 primeiros números perfeitos: 78.89492082595825s
  • Para os 19 primeiros números perfeitos: 93.7487268447876s

Para 20 eu fiquei com preguiça de esperar.

O seu programa apenas está levando um tempo muuuuuuito longo para calcular.

Observe que você tem um for dentro do outro. O laço de fora vai rodar mais de 33 milhões de vezes para achar o 5º número. O laço de dentro vai percorrer em cada iteração o mesmo valor do número do laço externo menos 1.

Se o laço externo roda n_max vezes, isso significa que o laço de dentro vai acabar executando um número de vezes igual n_max * (n_max - 1). Se n_max for 33550336, então o laço interno vai ter que rodar 1.125.625.012.162.560 de vezes até que o quinto número seja encontrado. Para chegar a esse número de mais de um quadrilhão de iterações, é possível que o programa leve alguns dias.

Já para encontrar o 8589869056, ele provavelmente levaria anos.

É possível fazer algumas simplificações:

  • Cortar o laço interno quando soma ultrapassar n.

  • Quando você encontra que n % div == 0, você encontra dois divisores, e não apenas um. Um deles é div e o outro é n / div. Com isso, você consegue diminuir o limite superior da iteração e só precisa ir até a raiz quadrada de n.

  • Já fazer soma começar com 1 e começar a testar a partir do 2. Pode parecer bobo, mas sem isso as duas otimizações anteriores não funciona porque ao achar o 1, ele também acharia o n e cortaria o laço imediatamente.

Com isso, é possível otimizar o laço interno mais ou menos assim:

soma = 1
for div in range(2, math.ceil(math.sqrt(n))):
    if n % div == 0:
        soma += div
        div2 = int(n / div)
        if (div != div2):
            soma += div2
        if soma > n:
            break

Você também pode acrescentar um parâmetro n_min e ao invés de percorrer de 1 até n_max, percorrer de n_min até n_max. Com essas mudanças, ao pesquisar os números perfeitos no intervalo 33550337 e 33550338, ele acha o 33550336 num piscar de olhos.

O código completo fica assim:

import math

def perfeito(n_min, n_max):
    lista = []
    for n in range(n_min, n_max + 1):
        soma = 1
        for div in range(2, math.ceil(math.sqrt(n))):
            if n % div == 0:
                soma += div
                div2 = int(n / div)
                if (div != div2):
                    soma += div2
                if soma > n:
                    break
        if n == soma:
            lista.append(n)
    return lista

print(perfeito(33550335, 33550337))

Veja aqui funcionando no ideone.

Tentei usando print(perfeito(2, 33550337)). Os números 6, 28, 496 e 8128 surgiram em milisegundos (coloquei um print antes do append para ver isso). No entanto, ainda demora várias horas para o 33550336 aparecer.

Somando às resposta já publicadas, um ponto a ser notado é que todo o número perfeito é um número hexagonal. Então, ao invés de testar um por um dos números, você pode percorrer apenas os números hexagonais. Ex:

def gen_hexagonal():
    n = 1
    while True:
        yield (2 * n * (2 * n - 1)) // 2
        n += 1

for i, num in gen_hexagonal():
    print(num)

# 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325, 378, 435, ...

Exemplo funcionando

Fonte

Related Posts:

Qual a diferença entre AppCompatActivity e Activity? – android android-activity
Pergunta: Qual a diferença da AppCompatActivity para Activity ? A partir de qual versão a AppCompatActivity foi adicionada ao Android? Autor da pergunta Luhhh A diferença reside ...
Como abreviar palavras em PHP? – php string
Pergunta: Possuo informações comuns como nome de pessoas e endereços, e preciso que elas contenham no máximo 30 caracteres sem cortar palavras. Exemplo: 'Avenida Natalino João Brescansin' ...
Qual é a finalidade de um parêntese vazio numa declaração Lambda? – c# expressões-lambda característica-linguagem
Pergunta: Criei um exemplo de uma declaração Lambda sem argumentos, entretanto, estou com duvidas referente a omissão do parêntese vazio () na declaração. Veja o exemplo: class ...
Boas práticas para URI em API RESTful – api rest restful
Pergunta: Estou com dúvida em relação às URIs de alguns recursos da api que estou desenvolvendo. Tenho os recursos projetos e atividades com relação 1-N, ...
Dúvidas sobre a integração do MySQL com Java – java mysql netbeans
Pergunta: Estou criando um sistema no NetBeans, utilizando a linguagem Java e o banco de dados MySQL. Escrevi o seguinte código para realizar a conexão ...
Qual é a finalidade da pasta Model do framework Inphinit? – php inphinit
Pergunta: No Inphinit micro-framework existe a pasta Model que fica dentro da pasta application, e nela é onde ficam as classes, mas eu estou muito ...
Uso do ‘@’ em variáveis – javascript typescript coffeescript
Pergunta: Vejo em algumas linguagens que compilam para javascript, como TypeScript e CoffeeScript, o uso do @ em variáveis, como também, casos em que o ...
Qual tamanho máximo um arquivo JSON pode ter? – json arquivo
Pergunta: Vou dar um exemplo para conseguir explicar minha duvida: Preciso recuperar informação de imagens vindas de uma API, esse banco de imagens me retorna JSON's ...
O que é Teste de Regressão? – terminologia engenharia-de-software testes
Pergunta: Na matéria de Teste de Software o professor abordou um termo chamado Teste de Regressão, isto dentro da disciplina de teste de software. Sendo ...
O que é um construtor da linguagem? – php característica-linguagem
Pergunta: Em PHP, já li e ouvi várias vezes a respeito dos Construtores da Linguagem. Os casos que sempre ouvi falar deles foi em casos ...
Função intrínseca para converter numérico para string – cobol
Pergunta: Estou a tentar saber se existe alguma função intrínseca do COBOL para converter um data numérico para string sem precisar usar a cláusula REDEFINES: ( ...
Porque usar implements? – java android
Pergunta: Qual a diferença entre usar btn.setOnClickListener(new OnClickListener() { e public class MainActivity extends Activity implements OnClickListener{ Estive fazendo um curso de Android e meu professor falou que ...
O que é XHTML e quando deve ser usado? – html xml xhtml
Pergunta: O que eu sei é que o XHTML precisa ser XML válido. Isso implica, por exemplo, que todas as tags precisam ser fechadas. Por ...
Uma placa aceleradora de vídeo pode melhorar o desempenho não-gráfico? [fechada] – desempenho
Pergunta: Para desenvolver em Ruby on Rails, eu utilizo aqui uma máquina virtual do VirtualBox com Ubuntu Server 14.04 sem interface gráfica instalada. Recentemente descobri uma ...
Concat() VS Union() – c# .net
Pergunta: Qual a diferença entre Concat() e Union() ? Quando usar Concat() e quando usar Union() ? Somente pode ser usado em list ? ...

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *