Dans son
article sur les nombres palindromes du
Pour la Science n°480, Jean-Paul Delahaye nous lance un défi de voir si l'on pouvait repousser les limites du plus grand nombre palindrome construit à partir de N chiffres et des 4 opérations + - * /.
Un nombre palindrome est un nombre « miroir », il a la même valeur lu de gauche à droite ou de droite à gauche : 9, 727, 12321, ...
Les records précédents, listés sur
le site de Erich Friedman (Math and Computer Science Department at Stetson University, Floride) étaient les suivants, trouvés par Erich Friedman :
Nb chiffres | Formule | Plus grand palindrome |
12 | 7×8×8×8×8×9 × (4×7×7×9×9−3) | 4095995904 |
13 | 7×7×7×7×7×8 × (7×7×7×8×8×8+6) | 23613431632 |
14 | 9×9×9×9×9×9 × (9×9+2) × (4×7×7×8−6) | 68899199886 |
15 | 7×7×7×7×8×8×8×8×8 × (2+9) × (9×9×9+3) | 633498894336 |
En cherchant en brute force on est vite limité : pour passer de N à N+1, on ajoute un chiffre et un opérateur en plus ce qui multiplie par 9×4=36 la complexité. Pour 15 chiffres cela ferait 9
15×4
14=55268479930183339474944 soit près de 10
23 possibilités à parcourir...
Une autre technique consiste à penser chaque résultat comme la combinaison de 2 résultats, chacuns pouvant être eux-mêmes le résultat de 2 résultats, etc.
Notons n
i un nombre combinaison de i chiffres; 72 est un n
2 car 8×9=72, 82 est un n
3 car 9×9+1=82. Par exemple pour N=13 on a le produit d'un n
6 et un n
7 : le n
6 A=7×7×7×7×7×8, et le n
7 B=(7×7×7×8×8×8+6). A et B étant eux mêmes composés de 2 éléments n
x : A est le produit de deux n
3 (7×8×8)×(8×8×9) et B est le produit d'un n
5 et d'un n
1 :(4×7×7×9×9)−(3). Chacun peu à nouveau se décomposer jusqu'à des n
1.
Donc en stockant tous les n
2, on peut les réutiliser pour calculer tous les n
3, etc.
Remarque : dans notre cas on cherche le palindrome le plus grand, donc on ignorera la division, car tout n
i / x est un n
j avec j<i.
Voici le nombre de n
i , comparé au nombre de combinaisons possibles :
i | Nombre de ni | Nombre de combinaisons ci de i chiffres (9i×3i−1) | %age ni / ci |
2 | 30 | 243 | 12.3456789012% |
3 | 155 | 6561 | 2.3624447493% |
4 | 739 | 177147 | 0.4171676630% |
5 | 3665 | 4782969 | 0.0766260455% |
6 | 16807 | 129140163 | 0.0130145414% |
7 | 76117 | 3486784401 | 0.0021830142% |
8 | 363831 | 94143178827 | 0.0003864656% |
9 | 1764050 | 2541865828329 | 0.0000006939% |
10 | 8331952 | 68630377364883 | 0.0000001214% |
On peut alors parcourir l'arbre de recherche considérablement rétréci, et finir par trouver en 2h de calcul tous les n
13 (et donc le plus grand palindrome parmi ceux-ci), puis les n
14, et les n
15 en quelque 8h de calcul sur un simple PC. Voici donc les nouveaux résultats que j'ai obtenu, courant 2017 :
Nb chiffres | Formule | Plus grand palindrome | Date |
13 | 9×9×9×9×9×9 × (6×7×7×7×7×9−8) | 68899199886 | 10/2017 |
14 | (9×9×9×9×9×5+4) × (8×8×8×8×9×9−5) | 97955055979 | 10/2017 |
15 | ((5×9×9×9×9×9−7)×7) × ((8×9×9×9×9−7)×8) | 867685586768 | 10/2017 |
16 | ((7×7×7×7×7×8−5)×4) × (9×8×8×8×8×8×8×7) | 8881871781888 | 10/2017 |
17 | (8×8×8×8×8×(9×9×7+2)) × ((9×9×9×9×8×7+6)×9) | 61655222255616 | 10/2017 |
18 | (8×8×(8×8×8×8×8×7+1)) × (9×(9×9×9×9×9×9×9−1)) | 631931242139136 | 10/2017 |
19 | (6×8×8×8×8×8×8×9×9+5) × (9×8×8×(7×8×8×8×9+7)) | 2367573333757632 | 10/2017 |
20 | (8×8×8×8×8×9×9×9×9+3) × (9×9×7×(6×9×9×9×9×9+8)) | 43189347374398134 | 10/2017 |
21 | ((8×8×8×8×8×9×9×9+5)×7×9) × (2×8×8×9×9×9×9×9×9+3) | 86925062526052968 | 10/2017 |
22 | (6×9×9×9×9×9×9×9×9+3)×9 × ((7×7×7×7×9×9×9+7)×7×9×9) | 2306950757570596032 | 10/2017 |
23 | ((8×8×8×9×9×9×9×9×9×9-1)×9) × ((7×9×9-2)×9×9×9×9×9×9-3) | 6617798452548977166 | 11/2017 |
24 | ((7×9×9×9×9×9×9−8)×9×9×9×9) × (((6×8×8×8×8×8+5)×8×9×9+1)×9) | 9539972462642799359 | 11/2017 |
Le programme décrit donne non pas la formule mais la valeur du palindrome et seulement la dernière opération qui y a mené (une multiplication entre un n
i et un n
j). Il faut donc retrouver la décomposition de chacun. Un autre programme parcourt les possibilités qui y mènent.
La porte est ouverte pour d'autres records...