Suite de Syracuse

Exercice · OCaml (option informatique), chapitre 4 — Programmation impérative : références et boucles

Énoncé

Écrire syracuse n ( $n \geq 1$ ), le nombre d'étapes pour atteindre $1$ (étape : $n \mapsto n /2$ si pair, $n \mapsto 3 n + 1$ sinon), avec une boucle while.

Corrigé

let syracuse n =
  let m = ref n and etapes = ref 0 in
  while !m <> 1 do
    if !m mod 2 = 0 then m := !m / 2
    else m := 3 * !m + 1;
    etapes := !etapes + 1
  done;
  !etapes

On itère la transformation jusqu'à atteindre 1, en comptant les étapes. Contrairement aux exemples précédents, on ne connaît aucun variant prouvant la terminaison pour tout n : c'est la conjecture de Syracuse, ouverte à ce jour. La boucle s'arrête en pratique, mais nul ne sait le démontrer en général.

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.