récréations informatiques

home & thèmes & liens & contact

 

Résumé : ce problème n’a toujours pas trouvé de solution. Et pourtant, il est très simple : on prend un nombre quelconque, s’il est pair, on le divise par deux, s’il est impair, on le multiplie par trois et on lui ajoute 1. Quelle valeur obtient alors?

Mots-clés : théorie des nombres, vitesse de convergence, simulation, arithmétique, parité.

Solutions :

La solution actuellement proposée est donnée par les fichiers MatLab : syracuse.m et syracusdemo.m.

thèmes

de plus

J'aimerais tant voir Syracuse (USA)

Ce problème est tiré d’un article intitulé "Le problème de Syracuse: compréhensible par un tout jeune enfant, ce problème n’a pas été résolu par les mathématiciens" écrit par Brian Hayes et publié dans Récréations informatiques chez Belin, 1984.

Trois pas en avant, deux pas en arrière : ce n’est peut-être pas la meilleure façon de marcher, mais au moins il paraît certain qu’elle permet d’arriver au but. Et pourtant un curieux problème non résolu de la théorie des nombres jette le doute sur cette conclusion. Le problème peut s’énoncer comme suit. Soit N un entier positif quelconque : si N est impair, multipliez-le par 3 et ajoutez 1, autrement dit, remplacez N par 3N + 1 ; si N est pair, divisez-le par 2 et remplacez N par N∕2. Dans les deux cas vous obtiendrez une nouvelle valeur de N et vous répétez l’opération. Après un grand nombre d’itérations, le nombre N a-t-il tendance à croître ou a décroître ? Est-ce qu’il augmente indéfiniment ? Et combien d’opérations faut-il pour voir le « destin » d’un nombre ?

La courbe ci-dessous décrit le comportement du nombre 27:



A titre d’information, tous les entiers jusqu’à 240
1,1⋅1012 ont déjà été testés à l’Université de Tokyo par Nabuo Yoneda.

L’origine du problème remonte aux années 1930 : Lothar Collatz, alors étudiant à l’Université de Hambourg, a travaillé sur une classe de problèmes qui inclut le problème de Syracuse, mais son travail n’a été publié que plus tard. Un collègue de Collatz nommé Helmut Hasse a introduit le problème à l’Université de Syracuse (Etats-Unis) (d’où son nom !) vers 1950... Pendant un mois tout le monde à Yale a travaillé sur ce problème, sans résultat. On a même prétendu que le problème serait le résultat d’une conspiration destinée à ralentir les recherches mathématiques aux Etats-Unis.

Le problème consiste à écrire un programme permettant de calculer et de représenter le profil de la suite de Syracuse pour tout entier ; il est également intéressant de mesurer les longueurs de parcours et les hauteurs maximales atteintes pour les suites. Il existe d’autres suites « à la Syracuse », notamment les suites de Prabekhar. Pour une de ces suites, on part d’un nombre N quelconque, on fait la somme des carrés de ses chiffres et cette somme constitue le second nombre de la suite auquel on réapplique le même algorithme... et ainsi de suite. Plus intéressante est la suite de Prabekhar où chaque nombre de la suite est égal à la somme des cubes des chiffres du nombre précédent.

Indications

Il faut chercher une méthode permettant de tester la parité d’un nombre, puis faire appel aux boucles.

Pour obtenir des valeurs intéressantes, il est conseillé de prendre :

N = 27, 871, 703, 100759293214567 ou encore: