(Oh non !) Encore un blog de Geek

Oui, je suis de nouveau un “projecteuler-addict“… aurai-je le maximum des points à mon BAC pour autant, cela reste à prouver, mais au moins j’aurai tout fait pour En cette fin d’après-midi, c’est au problème n°12 que je me suis attaqué… voici l’énoncé :

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

     1: 1
     3: 1,3
     6: 1,2,3,6
    10: 1,2,5,10
    15: 1,3,5,15
    21: 1,3,7,21
    28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

En fait, j’ai écris plusieurs versions du solveur (en PHP), juste pour manipuler la récurrence et les variables statiques. Voici la première version du programme. Notez la fonction triangle_number, totalement inutile mais assez amusante à coder (utilisation d’une variable de cache statique à cause des erreurs d’imbrication dues à la récurrence sur de grands nombres) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

<?php
set_time_limit(0);
function nb_divisors_of ($n=1234)
{
	if ($n == 1)
		return 1;
	$nb = 2;
	$limit = sqrt($n);
	for ($i=2; $i<$limit; $i++)
	{
		if ($n % $i == 0)
			$nb += 2;
	}
	return $nb;
}
function triangle_number ($n=1)
{
	// Static variable which contains a list of all the triangle numbers we calculated
	static $cached = array('1' => 1);
	// If we haven't calculated the triangle number $n, then calculate it and store it
	if (!isset($cached[(string)$n]))
		$cached[(string)$n] = triangle_number($n-1) + $n;
	return $cached[(string)$n];
}
function first_triangle_number_with_divisors_over ($n=10)
{
	// Yep, that's an infinite loop, F E A R
	for ($i=1; true; $i++)
	{
		if (nb_divisors_of(triangle_number($i)) > $n)
			return triangle_number($i);
	}
	return 'huh... wtf are you doing here ?';
}
echo '<h1>Problem 12</h1>',"\n";
$start  = microtime(true);
$number = first_triangle_number_with_divisors_over(500);
$stop   = microtime(true);
echo '<p>First triangle number with over 500 divisors : ',$number,'</p>';
echo '<p>',round($stop-$start, 5),'s</p>';
?>

Et voici la seconde version, qui bien que plus concise et plus rigoureuse (par exemple les fonctions retournent obligatoirement quelquechose de cohérent, hem) est nettement moins marrante! Ah si, j’ai tout de même réussi à utiliser la forme condensée de la boucle for (c.a.d tout faire tenir sur une ligne):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

<?php
set_time_limit(0);
function nb_divisors_of ($n=1234)
{
	if ($n == 1)
		return 1;
	$nb = 2;
	$limit = sqrt($n);
	for ($i=2; $i<$limit; $i++)
	{
		if ($n % $i == 0)
			$nb += 2;
	}
	return $nb;
}
function first_triangle_number_with_divisors_over ($nb=10)
{
	$triangle = 1;
	for ($i=1; nb_divisors_of($triangle) <= 500; $i++, $triangle += $i);
	return $triangle;
}
$start  = microtime(true);
$number = first_triangle_number_with_divisors_over(500);
$stop   = microtime(true);
echo '<p>First triangle number with over 500 divisors : ',$number,'</p>';
echo '<p>',round($stop-$start, 5),'s</p>';
?>

En ce qui concerne la vitesse néanmoins, pas de quoi se vanter : ~90s pour le premier programme et pas tellement moins pour le second… j’essaierai une autre approche ce soir. :/

Et… c’est parti pour le problème suivant !