La boucle qui ne termine pas toujours

La discipline de programmation · niveau 3 (difficile)

Énoncé

Démontrer que la boucle suivante se termine pour tout entier $n \geq 1$ :

def atteint_un(n: int) -> int:
    c = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = n + 1
        c = c + 1
    return c

Que se passe-t-il si l'on remplace n = n + 1 par n = 3 * n + 1 ?

Corrigé

Première partie : Si $n$ est pair, en une étape, la valeur devient $n /2 < n$ . Si $n$ est impair ( $n \geq 3$ ), l'étape suivante produit $n + 1$ (qui est pair) et l'étape d'après produit $(n + 1) /2$ . Pour $n \geq 3$ , on a $(n + 1) /2 < n$ . Ainsi, bien que la variable $n$ puisse augmenter ponctuellement d'une unité, sa valeur décroît strictement au bout de deux itérations successives au maximum. La suite des valeurs prises par $n$ toutes les deux étapes est strictement décroissante dans $N^{*}$ ; la boucle termine donc.
Deuxième partie : Le remplacement par 3 * n + 1 correspond à la conjecture de Syracuse. Pour cette version, il n'existe aucun variant connu ni aucune preuve générale de terminaison à ce jour.

Énoncé

Corrigé

Exercices semblables