Problème de Syracuse

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Problème (ou conjecture) de Syracuse » programme Javascript

Ce "petit" problème d'arithmétique apparaît pour la première fois, en 1937, aux États-Unis, posé par le professeur Lothar Collatz (1910-1990) de l'université de Syracuse (non pas en Sicile mais dans l'État de New York, USA). Le problème a pris de nombreux noms depuis (Collatz problem, conjecture de Thwaites, conjecture de Kakutani, algorithme de Hasse, ...), suite aux travaux de chercheurs américains intrigués par ce problème. En voici l'algorithme :

On se donne un entier naturel n non nul :

s'il est pair, on le divise par 2;

s'il est impair, on le triple et on ajoute 1;

on itère le procédé sur le nouvel entier obtenu tant qu'il est supérieur à 1.

Dans tous les cas essayés depuis son origine, cet algorithme conduit à 1 en finissant toujours par 4 - 2 - 1

♦ 1 → 4 → 2 → 1

♦ 2 → 1

♦ 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

♦ 4 → 2 → 1

♦ 5 → 16 → 8 → 4 → 2 → 1

♦ 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

➔ 7 est le premier cas non trivial... :

♦ 17 → 52 → 26 → 13 → 40 → 20 → 10 →5 → 16 → 8 → 4 → 2 → 1

♦ 1000 → 500 → 250 → 125 → 376 → 188 → ... 9232 ...→... → 4 → 2 → 1

Ce dernier exemple montre que la suite des entiers obtenus successivement peut "durer" fort longtemps... Voici le détail pour ce cas n = 1000 :

➔ Cependant, si n est une puissance de 2, la suite est clairement strictement décroissante dans N^*et converge donc vers 1. Les autres cas sont moins triviaux...

Des nombres énormes ( > 10¹⁶) ont été testés sur ordinateur : ça marche tout le temps... Le problème de Syracuse est un problème ouvert : des études très poussées n'ont pas, à ce jour (10 février 2011), conduit à la preuve de cette conjecture.

La documentation sur le sujet est très fournie. On trouvera d'excellentes et nombreuses pages sur le Web en français et en anglais (» quelques références en fin de page).

Mise à l'épreuve de la conjecture... :

On se propose ici d'écrire un petit programme en JavaScript vérifiant la conjecture et affichant le nombre d'itérations (longueur du cycle) nécessaires pour arriver à 1.

<SCRIPT LANGUAGE=JavaScript>
function go()
{
var n=7, iter=0
n=eval(prompt("Entrez un nombre:",n))
nn=n;
aff=n.toString()+ " - ";
while (n > 1)
{
if (n%2 == 0) {n=n/2} else {n = 3*n + 1}
iter++
aff=aff + n.toString()+ " - "
}
alert("Nombre étudié : " + nn +"."+ "\n" + "1 est atteint en "+ iter + " cycles." + "\n" + aff)
}
}
</SCRIPT>

➔ Code HTML du formulaire permettant de lancer les calculs ci-dessus :

Programme bis :

∗∗∗
Dans le cas impair, prouver que si l'on remplace tripler et ajouter 1 par simplement ajouter 1, c'est à dire :
if (n%2 == 0) {n = n/2} else {n = n + 1} alors l'algorithme converge encore vers 1 en finissant également par 4 - 2 - 1☼

➔ Pour en savoir plus :

1er problème de Collatz (Hambourg, 1932) : http://utenti.quipo.it/base5/numeri/collazorig.htm
Sur le site d'Eric Weisstein : http://mathworld.wolfram.com/CollatzProblem.html