Une boucle sans variant connu

/* A */ while (n > 0) { n = n / 2; }

/* B */ while (n != 1) { n = (n % 2 == 0) ? n / 2 : 3 * n + 1; }

(A) termine, et la preuve tient en deux lignes. Variant : $V=n$. Il est entier, minoré par $0$ tant que la condition tient, et il décroît strictement à chaque tour — pour $n\ge 1$, $\lfloor n/2\rfloor <n$. La boucle s'arrête donc, en $\lfloor {\log }_{2}n\rfloor +1$ tours : mesuré, à partir de $n=1000000$, elle en fait $20$.

(B) est la suite de Syracuse, et personne ne sait la prouver. On mesure sans peine qu'elle s'arrête sur des cas particuliers :

n =   6 :   8 etapes, sommet atteint    16
n =   7 :  16 etapes, sommet atteint    52
n =  27 : 111 etapes, sommet atteint  9232
n = 871 : 178 etapes, sommet atteint 190996
pour tout n <= 10000 : au plus 261 etapes, atteintes en n = 6171

Ce qui ferme la porte à un variant simple est visible dans ces chiffres : partant de $27$, la suite monte jusqu'à $9232$ avant de redescendre. Aucune quantité évidente ne décroît. Et la conjecture de Collatz — « (B) termine pour tout $n\ge 1$ » — est ouverte depuis 1937.

Un test ne remplacerait pas la preuve. On peut vérifier (B) pour tous les $n$ jusqu'à $10^{20}$ — cela a été fait — sans rien démontrer. C'est la mise en garde du chapitre chap:discipline : « un test qui passe ne prouve rien ».