Resolvendo o prolema 23 do Project Euler

Inicialmente, para quem ainda não conhece, o Project Euler é um site que visa encorajar, desafiar e ajudar os desenvolvedores a melhorar suas habilidades técnicas de uma forma divertida e muito relacionada com o mundo da matemática.

Existem atualmente 356 desafios, sendo que destes, até o momento, resolvi 23. Não considero este último o mais difícil dentre os já resolvidos, mas, como possui o menor número de pessoas que solucionaram, achei interessante deixar exposta a forma como resolvi..

Primeiramente, vamos ao enunciado do problema 23:

Um número perfeito é um número cuja coma de seus divisores é exatamente igual ao próprio número. Por exemplo: a soma dos divisores de 28 é 1 + 2 + 4 + 7 + 14 = 28, o que significa que 28 é um número perfeito.
Um número n é chamado de deficiente quando a soma de seus divisores é menor do que n e é chamado de abundante se a soma exceder o número n.
Como 12 é o menor número abundante, 1 + 2 + 3 + 4 + 6 = 16, o menor número abundante que pode ser escrito com a soma de dois números abundantes é 24.
Por análise matemática, é sabido que todos os inteiros maiores que 28123 podem ser formados através da soma de dois números abundantes.
No entanto, este limite não pode ser reduzido através de análise, embora seja sabido que o maior número que não pode ser expresso como a soma de dois números abundantes é inferior a este limite.
Encontre a soma de todos os números inteiros positivos que não podem ser formados através da soma de dois números abundantes.


Ok, uma vez com o problema em mãos, pesquisei um pouco mais sobre números perfeitos, deficientes e abundantes e descobri que a incidência de números deficientes é muito maior do que a de números abundantes e perfeitos.

Para dar idéia melhor da proporção:

Deficientes = {1,2,3,4,5,7,8,9,10,11,13,14,15,16,17,…},
Abundantes = {12,18,20,24,30,36,40,42,48,54,56,60,66,70,72,…},
Perfeitos = {6, 28, 496, 8128, 33550336, 8589869056, 137438691328, . . . }

Com isso em mente, decidi tentar descobrir quantos números abundantes existiam no nosso espaço amostral de 28123. Como fazer isso?

Precisamos percorrer todos os números de 1 até 28123 e verificar se ele é abundante, se sim, devemos gurdar ele em uma lista.

Bom, mas de onde surgiu a função “isAbundant”? É, ela teve que ser totalmente implementada..

Para encontrarmos todos os divisores de um número existe um passo-a-passo, bem explicado neste documento do site Matemática Didática.

Basicamente, só é preciso fazer a fatoração de primos e trabalhar o resultado da fatoração de acordo com algumas regras.

Desta forma, o código escrito para se definir se um número é abundante engloba todo o código abaixo:

Agora que já possuímos os 6965 números abundantes existentes do conjunto dos primeiros 28123 números inteiros, podemos calcular todos os números que podem ser gerados a partir de 2 números abundantes.

Bom, agora ficou fácil… temos em mãos todos os valores, do intervalo 1-28123, possíveis de serem gerados a partir de 2 números abundantes.
Logo, para sabermos a soma de todos os números que não podem ser gerados pela soma de 2 números abundantes basta percorrermos cada valor do intervalo 1-28123 e verificarmos se este número não existe no conjunto “sum_2_abundants”. Caso o número não seja encontrado, adicionamos ele a nossa soma..

Com isso, chegamos a solução do problema, o valor 4179871. O algoritmo executa em aproximadamente 3 segundos, o que é bem razoável tendo em vista a quantidade de cálculos necessário para a descoberta da solução.