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

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 :

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 ( > 1016) 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 :

<CENTER>
<HR>
<INPUT TYPE=button NAME=Bouton VALUE="Lancer le programme" onclick="go()">
<HR>
</CENTER>

Programme bis :    


Prouver que si, dans le cas impair, on remplace : tripler et ajouter 1 par simplement ajouter 1, soit :
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 :

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


© Serge Mehl - www.chronomath.com