Bienvenue sur le site Free 1 de Maurice Rignon

Les palindromes

C'est un exercice proposé par Alain Raymond, notre professeur de Mathématiques Récréatives à l'UIAD. La dernière question est assez déconcertante : Est-il raisonnable de penser que 196 n'est pas palindromique ?

Pour reprendre un peu le contexte :

• Un palindrome est un nombre de n chiffres dans lequel, pour tout i de 1 à n, le chiffre n° i est égal au chiffre n° n + 1 - i.
• Exemple : 4321234 est un palindrome. n = 7. Le ch1 = le ch7 = 4 ; ch2 = ch 6 = 3 ; ch3 = ch5 = 2 ; ch4 = ch4 = 1
• A partir d'un nombre quelconque, palindrome ou non palindrome, on peut modifier ce nombre en l'ajoutant à son renversement.
• Le renversement d'un nombre est un nouveau nombre dans lequel le chiffre n° 1 du nouveau est égal au chiffre n° n + 1 - i du précédent.
• Exemple : le renversement de 184 est 481
• Le fait d'ajouter son renversé à un nombre apporte un certain ordre qui peut se diriger vers un résultat palindrome.
• Exemple : 184 + 481 = 665. Le nouveau nombre n'est pas un palindrome.
• Si on poursuit : 665 + 566 = 1231 ; 1231 + 1321 = 2552. On a un palindrome au 3ème renversement. 184 est palindromique au 3ème renversement.
• A remarquer ici :
• Dans l'addition de 184 + 481 il y a une retenue au chiffre des dizaines, reportée sur le chiffre des centaines, ce qui perturbe la tentative de mise en ordre par le renversement
• Dans l'addition de 665 + 566 il y a 3 retenues
• Dans l'addition de 1231 + 1321 il n'y a aucune retenue et on obtient un palindrome
• La dernière question de l'exercice est un problème non résolu à propos du nombre 196 qui ne semble pas palindromique.
• Darly Francis a fait 196 100 renversements et n'a pas obtenu de palindrome.

Comment faire une démonstration rigoureuse que 196 n'est pas palindromique ? Trouver un palindrome trancherait définitivement la question. Mais il est fortement probable qu'on ne trouvera jamais un palindrome issu de 196. Deux critères sont abordés ici - 1 - L'existence d'une retenue dans l'addition - 2 - La probabilité d'apparition d'un palindrome lorsque le nombre de chiffres augmente.

06.12

Le texte complet de l'exercice n° 12 du cours n° 6 du 14 janvier 2019

Haut de page

Exploration des retenues au cours des renversements successifs

L'examen des retenues dans les additions des renversements successifs a été pratiqué à l'aide d'Excel. Les limites fixées sont les suivantes :

• Les nombres pris en compte vont de 11 à 20 000
• Pour un nombre donné, les renversements sont effectués jusqu'à obtenir un nombre qui comporte au maximmum 99 chiffres

Les conclusions sont les suivantes :

1. Il n'y a aucun résulat non palindrome sans retenue
2. On a obtenu 21 718 résultats non palindromes avec une ou plusieurs retenues dans l'addition
3. Il y a 6 461 résultats palindromes sans retenue
4. Il y a 90 résultats palindromes avec retenue

A retenir : Pas de nombre non palindrome sans retenue, mais quelques palindromes avec retenue. Il semble donc que dans quelques cas particuliers, l'addition avec retenue ne perturbe pas l'apparition d'un palindrome. Voici un exemple : 29 + 92 = 121. Par chance ici, la retenue de la colonne des dizaines apporte le chiffre 1 aux centaines et ce chiffre 1 est le même que celui de l'addition de 9 et 2 aux unités. Donc la règle n'est pas absolue. L'apparition d'un palindrome dans les renversements successifs n'est pas exclusivement liée à l'absence de retenue dans l'addition.

A

Fichier Excel, exploration des retenues

Haut de page

Apparition d'un palindrome dans les grands nombres des renversements successifs

Etablissement d'une liste de travail

Le fichier A de l'étude des retenues permet d'examiner les suites des renversements successifs. Il apparaît que certaines suites se répètent dans l'étude de plusieurs nombres différents. Donc on élague tout nombre dont l'étude a déjà été faite précédemment et tout nombre qui fait apparaître dès les premiers renversements une suite qui a déjà été étudiée auparavant. Ainsi les 20 000 nombres se trouvent réduits à 627.

B

Fichier Excel, Préparation de l'élaguage

C

Liste élaguée

Haut de page

Statistiques sur les grands nombres

Le temps de calcul du fichier A est environ de 3 minutes. Il est envisagé de tenter de construire des renversements jusqu'à 999 chiffres à partir des 627 nombres définis précédemment qui représentent une étendue d'étude des nombres de 11 à 20 000. Le temps de calcul du dernier fichier D est :

• 4 heures 30 environ avec un microprocesseur AMD A6-3410MX APU
• 2 heures 20 environ avec un Intel Core i7-7500U CPU

Les nombres étudiés ont été regroupés en 10 classes suivant le nombre de chiffres

Voici les résultats du comptage

D

Statistiques sur les grands nombres

E

Dans un but de contrôle, cet outil affiche la suite des renversements d'un nombre

Haut de page

Conclusions

• Sur les 1 507 146 renversements effectués, 1 876 ont produit un palindrome (0,1 %)
• Il est confirmé que sur cet échantillonnage de renversements jusqu'à 999 chiffres aucun ne donne un non palindrome sans retenue
• Il n'y a que 3 palindromes obtenus avec une ou des retenues à l'addition. Ce résultat est en accord avec les conclusions après le traitement du fichier A, car dans le fichier A il y a beaucoup de nombres qui appartiennent aux trois grands groupes. Mais ce résultat reste à vérifier.
• Ce qui nous intéresse le plus est la répartition des palindromes dans les classes. Le résultat est assez caractéristique. A partir de la classe 6 il n'y a plus aucun palindrome généré. Dans cette grande classe de 6 à 9, c'est à dire dès que le nombre atteint une taille de 50 chiffres, on a généré 75 703 + 151 520 + 454 804 + 757 152 = 1 439 179 renversements pour lesquels absolument aucun n'est palindrome.

La conclusion n'est pas absolue, mais les chances que 196 soit palindromique sont quasiment nulles.

Les renversements palindromiques obtenus avec une retenue à l'addition

Tous les renversements non palindromiques sont avec des additions à retenue. Les renversements palindromiques sont pour la majeure partie avec des additions sans retenue. Pourtant quelques uns subsistent avec une addition à retenue. Qu'est-ce qui fait que l'ordre apporté par le renversement n'est pas perturbé par l'existence d'une retenue ?

Le fichier F explore les renversements palindromiques avec des additions à retenue et en fait la liste dans les limites suivantes :

• les nombres étudiés vont de 11 à 20 000
• Les renversements effectués pour chacun des nombres s'arrêtent lorsqu'on atteind un renversement de plus de 99 chiffres. On sait qu'à partir de 50 chiffres on ne produit plus de palindromes

On obtient 6 renversements palindromiques, chacun pouvant être issus de différents nombres.

Les remarques

• Les couples de chiffres ajoutés dans une colonne donnent toujours le résultat 11 : 2 + 9, 3 + 8, 4 + 7, . . . , 8 + 3, 9 + 2
• La retenue est utilisée de deux façons différentes :
  • Soit elle s'ajoute à une autre addition 11 pour faire 12,
  • Soit elle s'ajoute à une colonne de zéros pour faire un total de 1
• Les palindromes issus d'une addition à retenue(s) ne contiennent que les chiffres 0, 1 ou 2