Suite de Syracuse (Conjecture de Collatz) — exercice corrigé de Python (école d'ingénieur) (chapitre 2)

Suite de Syracuse (Conjecture de Collatz)

Structures de contrôle : conditions et boucles

Énoncé

La suite de Syracuse est définie par : $u_{n + 1} = {u_{n} /2 3 u_{n} + 1 si u_{n} est pair si u_{n} est impair$ La conjecture affirme que pour tout $u_{0} > 0$ , la suite atteint 1. Écrire une fonction temps_de_vol(n) qui renvoie le nombre d'étapes pour atteindre 1.

Corrigé

def temps_de_vol(n):
    """
    Retourne le temps de vol de n (nombre d'étapes jusqu'à 1)
    Précondition : n >= 1
    """
    if n <= 0:
        raise ValueError("L'entrée doit être positive")
    
    etapes = 0
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        etapes += 1
    return etapes

Exemples :

$n$	Suite	Temps de vol
1	1	0
2	$2 \to 1$	1
3	$3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$	7
6	$6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$	8

Remarque algorithmique : On peut utiliser la mémoïsation avec functools.lru_cache pour optimiser :

from functools import lru_cache

@lru_cache(maxsize=None)
def temps_de_vol_memo(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + temps_de_vol_memo(n // 2)
    else:
        return 1 + temps_de_vol_memo(3 * n + 1)