La conjecture de Syracuse

Prenez un entier positif. S’il est pair, divisez-le par 2 ; s’il est impair, multipliez-le par 3 et ajoutez 1. Recommencez avec le résultat.

En partant de 6, on obtient : 6, 3, 10, 5, 16, 8, 4, 2, 1… et la suite boucle sur 4, 2, 1. La conjecture de Syracuse affirme que c’est toujours le cas, quel que soit l’entier de départ.

Temps de vol et altitude

On appelle temps de vol le nombre d’étapes nécessaires pour atteindre 1, et altitude maximale la plus grande valeur rencontrée en chemin. Ces deux nombres varient de façon très irrégulière d’un entier de départ à l’autre :

Partir de 7 donne ainsi : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. La suite monte jusqu’à 52 avant de retomber d’un coup, comme un grêlon ballotté dans un nuage.

Un problème ouvert

La conjecture est attribuée au mathématicien allemand Lothar Collatz, qui l’aurait formulée dans les années 1930. Son nom français vient de l’université de Syracuse, aux États-Unis, où elle a beaucoup circulé dans les années 1950.

• Elle a été vérifiée par ordinateur pour tous les entiers jusqu’à plus de 10²⁰.

• En 2019, Terence Tao a montré que « presque toutes » les suites finissent par descendre très bas, sans pouvoir conclure pour toutes.

• Personne ne sait la démontrer : c’est l’un des problèmes les plus simples à énoncer et les plus difficiles à résoudre.

Les mathématiques ne sont pas encore prêtes pour de tels problèmes.

— Phrase attribuée à Paul Erdős

Explorer avec Python

def syracuse(n):
    vol, altitude = 0, n
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        vol += 1
        altitude = max(altitude, n)
    return vol, altitude

print(syracuse(27))