(Oh non !) Encore un blog de Geek

…parce que c’est quand même particulièrement bon de voir son ordinateur bosser à plein temps pour une fois! Pour rappel, Project Euler (en anglais) est un site qui propose des dizaines de problèmes mathématiques à résoudre grâce à une logique implacable, des algorithmes de programmation très poussés… ou tout simplement avec la très connue méthode dite de Brute Force ! (en gros on tente de créer un algorithme pas trop lent et on laisse l’ordi exécuter des calculs monstrueux en priant pour que ça ne prenne pas trop de temps et que l’ordi ne plante pas à 99% de la recherche) ^^

Je suis tombé tout à l’heure sur le Problème 21 dont voici l’énoncé :

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Peut-être est-il possible de trouver la solution de tête (tous mes voeux de no-lifitude à ceux qui en sont capables), mais pourquoi faire simple quand on peut faire compliqué, hein ? Voici donc mon petit programme en PHP :

<?php
function sum_of_proper_divisors ($n)
{
	$sum  = 1;
	$limit = sqrt($n)+1;
	for ($i=2; $i<$limit; $i++)
	{
		if ($n % $i == 0)
			$sum += $i + $n / $i;
	}
	return $sum;
}
 
function sum_of_amicable_numbers_below ($limit=1000)
{
	$sum  = 0;
	$skip = array(); // Skip redondant calculations by saving "b" values into an array
	for ($a=1; $a<$limit; $a++)
	{
		// Skip iteration if "a" equals a previous "b"
		if (in_array($a, $skip))
			continue;
		$b = sum_of_proper_divisors($a);
		if ($a != $b && $a == sum_of_proper_divisors($b))
		{
			echo '(',$a,', ',$b,')<br />',"\n";
			flush(); // Flush the buffer to the browser so that we can see the progress
			$sum += $a + $b;
			$skip[] = $b; // Store "b" value in an array to avoid processing it later
		}
	}
	return $sum;
}
 
echo '<h1>Problem 21</h1>',"\n";
$start = microtime(true);
$sum   = sum_of_amicable_numbers_below(10000);
$stop  = microtime(true);
echo '<p>Sum of amicable numbers below 10000 : '.$sum,'</p>';
echo '<p>',round($stop-$start, 5),'</p>';
?>

PHP 5.3, Pentium IV à 3.00 Ghz et 1 Go de RAM … ~5 secondes pour obtenir la solution

Si vous voyez des trucs à améliorer dans ce code, n’hésitez pas à me le dire en commentaires, c’est pour m’améliorer que je me suis inscrit à Project Euler après tout