Conjecture de Syracuse

La conjecture de Syracuse (ou conjecture de Collatz) également connue sous le nom de problème 3n+1, stipule qu'en appliquant l'algorithme 3n+1 à n'importe quel nombre entier positif, on finira toujours par atteindre le nombre 1.

Prendre un nombre $ n $ (entier positif non nul), si $ n $ est pair, le diviser par $ 2 $, sinon multiplier par $ 3 $ et ajouter $ 1 $. Recommencer en donnant à $ n $ la valeur du résultat précédemment obtenu.

Mathématiquement l'algorithme est défini par la fonction $ f $ : $$ f_{3n+1}(n) = \begin{cases}{ \frac{n}{2}} & {\text{si }}n \equiv 0 \mod{2} \\ 3n+1 & {\text{si }} n \equiv 1 \mod{2} \end{cases} $$

Lorsque la valeur $ 1 $ est obtenue, suite est généralement considérée comme terminée, car l'algorithme rendre dans une boucle infinie de 4, 2, 1, 4, 2, 1, 4, 2, 1.

Si le nombre $ n $ est impair, alors le multiplier par $ 3 $ et ajouter $ 1 $ le rend forcément pair, l'étape suivante est obligatoirement une division par 2.

La version compressée (ou raccourcie) fusionne les calculs $ 3x+1 $ et $ x/2 $ en une seule étape $ (3x+1)/2 $

Non, personne n'a trouvé de nombre pour lequel ça ne fonctionne pas mais personne n'a trouvé de preuve mathématique que la conjecture fonctionne toujours.

C'est pourquoi la conjecture s'appelle aussi problème de Syracuse ou problème de Collatz et qu'il ne s'agit pas d'un théorème.

Toute personne trouvant un nombre qui ne termine pas à 1 aura alors résolu la conjecture en prouvant qu'elle est fausse.

Non, il y a eu récemment quelques avancées réelles mais la conjecture de Syracuse demeure non résolue malgré des dizaines des pseudo-scientifiques qui ont prétendu avoir une preuve.

Un nombre n'apparait jamais 2 fois dans la suite.

Toute suite se termine par une série de puissance de 2.

Un nombre impair est toujours suivi d'un nombre pair.

Les nombres 5 et 32 donnent la même suite.

Il existe plusieurs manière de programmer un code source pour l'algorithme 3x+1 :// Javascript
function step(n) {
if (n%2 == 0) return n/2;
return 3*n+1;
}
function collatz(n) {
var nb = 1;
while (n != 1) {
n = step(n);
nb++;
}
return nb;
}// Python
def collatz(x):
while x != 1:
if x % 2 > 0:
x =((3 * x) + 1)
list_.append(x)
else:
x = (x / 2)
list_.append(x)
return list_


D'autres noms de la conjecture/problème de Syracuse sont utilisés dans la littérature :

— conjecture de Collatz

— conjecture d'Ulam

— conjecture de Hailstone

— conjecture tchèque

— problème 3x+1 (ou 3n+1)

— algorithme de Hasse

— problème de Kakutani

— conjecture de Thwaite

Le nom de Syracuse proviendrait de l'Université de Syracuse, une ville de l'état de New York aux Etats-Unis.

Ce tableau regroupe tous les nombres jusqu'à 1000 sous la forme (temps de vol/iterations => nombres ayant ce temps de vol)

Ce tableau regroupe tous les nombres jusqu'à 1000 sous la forme (altitude maxi de vol => nombres ayant cette altitude maxi)

Le tableau ci-dessus montre des altitudes jusque 250504 pour les nombres jusque 1000. Mais il existe une infinité de nombre qui vont plus haut.

Pour tout nombre N donné (N très grand), alors le nombre impair le plus proche de N aura une altitude encore plus grande.

Formulée en 1937 par Lothar Collatz (mathématicien allemand), elle reste à ce jour irrésolue : personne n'a encore pu prouver que cette conjecture se termine toujours par 1.