La conjecture de Syracuse

Exercice supplémentaire · niveau 3 (difficile) · sciences numériques et technologie (seconde), chapitre 4 — Les boucles · La boucle non bornée : while

Énoncé

On part d'un entier n strictement positif et on répète : s'il est pair on le divise par $2$ , sinon on le remplace par $3 n + 1$ . On s'arrête quand on atteint $1$ .

Écrire une fonction duree_vol(n) renvoyant le nombre d'étapes, et la tester sur $n = 6$ , $n = 7$ et $n = 27$ . Pourquoi ne peut-on pas démontrer que cette boucle se termine ?

Corrigé

def duree_vol(n):
    etapes = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        etapes = etapes + 1
    return etapes

print(duree_vol(6))    # 8
print(duree_vol(7))    # 16
print(duree_vol(27))   # 111

Le vol de $6$ est court, celui de $27$ passe par $9232$ avant de retomber.

Pourquoi on ne peut rien démontrer : dans toutes les boucles vues jusqu'ici, on exhibait une quantité entière positive strictement décroissante. Ici, la valeur diminue quand $n$ est pair mais augmente quand il est impair ; aucune quantité décroissante n'est connue.

Que la boucle s'arrête pour tout entier de départ est la conjecture de Syracuse, vérifiée par ordinateur jusqu'à des nombres gigantesques, mais non démontrée à ce jour. C'est le seul programme de ce livre dont personne ne sait prouver qu'il se termine.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.