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.

List abundants = new ArrayList();
for (int i = 12; i <= 28123; i++) {
  if(isAbundant(i))
    abundants.add(i);
}
System.out.println("total of abundants: " + abundants.size());

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:

public static boolean isAbundant(int number){
	return sumDivisors(number) > number;
}

public static Integer sumDivisors(int number){
	Set<Integer> divisors = divisors(number);
	Integer sum = 0;
	for (Integer div : divisors) {
		sum += div;
	}
	return sum;
}

public static Set<Integer> divisors(int number){
	Set<Integer> divs = new HashSet<Integer>();
	divs.add(1);

	Set<Integer> mults = new HashSet<Integer>();
	mults.add(1);

	List<Integer> factorization = primeFactorization(number);
	for (Integer prime : factorization) {
		if( prime < number )
			divs.add(prime);

		Set<Integer> newMults = new HashSet<Integer>();
		for (Integer mult : mults) {
			Integer value = prime * mult;
			if(value < number)
				newMults.add(value);
		}

		mults.addAll(newMults);
	}
	divs.addAll(mults);
	return divs;
}

private static final List<Integer> PRIMES = generatePrimes(28123);

public static List<Integer> primeFactorization(int number){
	List<Integer> f = new ArrayList<Integer>();

	int primeIndex=0;
	Integer prime = PRIMES.get(primeIndex);	

	while(number>1){
		if(number % prime == 0){
			number=number/prime;
			f.add(prime);
		}else{
			prime = PRIMES.get(++primeIndex);
		}
	}
	return f;
}

public static List<Integer> generatePrimes(int max) {
	List<Integer> primes = new ArrayList<Integer>();
	OUTERLOOP: for (int i = 2; i <= max; i++) {
		for (Integer p : primes)
			if (i % p == 0)
				continue OUTERLOOP; // i is not prime
			primes.add(i);
	}
	return primes;
}

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.

// cache the possibilities of sum between two abundant numbers
for (int i = 0; i < abundants.size(); i++) {
	Integer i_abundant = abundants.get(i);
	for (int j = i; j < abundants.size(); j++) {
		sum_2_abundants.add(i_abundant + abundants.get(j));
	}
}
System.out.println("total of sum possibilites: " + sum_2_abundants.size());

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..

int sum=0;
for (int i = 1; i <= 28123; i++) {
	if(! sum_2_abundants.contains(i)){
		sum += i;
	}
}
System.out.println("The solution is: " + sum);

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.