Gustavo Paes

Project Euler: Problema 23

Ontem finalizei o problema 23 do Project Euler. O problema em si é de fácil solução, mas se você não pensar em otimizar ao máximo a execução do seu script, pode levar horas — como o meu levou — ou até mesmo dias, para conseguir o resultado final. E ainda pode conseguir um resultado errado.

O problema 23 explica o que é um número perfeito (aquele que a soma de seus divisores resultado no próprio número), número deficiente (aquele que a soma é menor que o próprio número) e número abundante (aquele que a soma é maior que o próprio número).

Como exemplo de um número perfeito, ele cita o 28, que possui os seguintes divisores:
1 + 2 + 4 + 7 + 14 = 28

E como exemplo de um número abundante, é citado o número 12:
1 + 2 + 3 + 4 + 6 = 16

Dito isso, o problema afirma que todos os números positivos inteiros maiores que 28123 podem ser encontrados através da soma de dois números abundantes. Mas que, de 0 até 28123, não é possível afirmar isso. E o problema pede no fim é que você encontre quais são os números que não podem ser encontrados através da soma de dois números abundantes e some eles. A resposta final essa.

Sabendo de tudo isso, algo que irá mudar sua vida a partir desse ponto, vamos pensar na solução. Primeira coisa que se precisa fazer é achar todos os números abundantes entre 0 e 28123. Para isso é preciso criar uma função que ache os divisores de um determinado número. Com ela, fica fácil descobrir quais são números abundantes e quais não são:

abundantes = []
for n in xrange(1, 28124):
	if sum(divisors(n)) > n:
		abundantes.append(n)

A função divisors retorna True ou False. Para conseguir achar tudo, a função leva cerca de meio minuto.

Com esses números em um array você tem duas opções:

1. Fazer um laço de 1 até 28123 verificando os números que podem ser encontrados através da soma de dois números abundantes;

2. Fazer todas as somas possíveis do números abundantes e guardar em um array para depois ir verificando de 1 a té 28123 qual deles existe nesse array.

A primeira opção foi a que eu escolhi primeiro (não tinha tido a segunda idéia ainda). Fiz o script sem grandes dificuldades mas logo percebi que a execução iria demorar, provavelmente, mais de dia.

Parti então para um segundo script — enquanto o primeiro ia ocupando 100% de um dos processadores — para tentar chegar a uma solução melhor. Foi quando pensei na segunda opção.

Mesmo com a segunda opção, que roda mais rápido que a primeira, o script levou quase 5 horas para encontrar o número final. O script é esse:

from divisors import divisors
import time

start = time.time()

# funcao que verifica se o parametro passado pode ser encontrado
# atraves da soma de algum dos numeros abundantes encontrado
def allSum(arr):
	all_sum = []
	limit = len(arr)

	f_index = 0 # primeiro indice
	s_index = 0 # segundo indice
	
	while f_index  n:
		abundantes.append(n)

print "... encontrados %d numeros" % len(abundantes)
print

print "Somando todos os abundantes entre si..."
all_sum = allSum(abundantes)

print "... encontrado %d resultados" % len(all_sum)
print

# percorre ate o limite
print "Descobrindo numeros que nao podem ser encontrados atraves da soma..."
numbers = []
for x in xrange(1, 28124):
	# apenas para controle no console
	if x%10 == 0:
		print x

	if x not in all_sum:
		numbers.append(x)

print
print
print sum(numbers)

print
print "achado em ", (time.time() - start) , "segundos"

Por sorte consegui chegar no resultado certo, senão seriam 5 horas de processamento jogados no lixo :)