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 915×414=55268479930183339474944 soit près de 1023 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 ni un nombre combinaison de i chiffres; 72 est un n2 car 8×9=72, 82 est un n3 car 9×9+1=82. Par exemple pour N=13 on a le produit d'un n6 et un n7 : le n6 A=7×7×7×7×7×8, et le n7 B=(7×7×7×8×8×8+6). A et B étant eux mêmes composés de 2 éléments nx : A est le produit de deux n3 (7×8×8)×(8×8×9) et B est le produit d'un n5 et d'un n1 :(4×7×7×9×9)−(3). Chacun peu à nouveau se décomposer jusqu'à des n1.
Donc en stockant tous les n2, on peut les réutiliser pour calculer tous les n3, etc.
Remarque : dans notre cas on cherche le palindrome le plus grand, donc on ignorera la division, car tout ni / x est un nj avec j<i.
Voici le nombre de ni , 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 n13 (et donc le plus grand palindrome parmi ceux-ci), puis les n14, et les n15 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 ni et un nj). 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...
