La conjecture de Syracuse nous enseigne que

\(\forall n \in \mathbb{N^*}, \exists (a,b,c)! ~~/~~ n= \frac{(6a \pm1).2^b -1}{3}.2^c\)

sachant que \(b\) est pair avec la formule utilisant \(6a+1\) et impair avec la formule utilisant \(6a-1\).

La marche à suivre pour convertir ainsi n’importe quel nombre entier \(n\) non nul est la suivante :

on calcule d’abord le nombre de fois que \(n\) est divisible par \(2\), ce qui donne \(c\). On obtient ainsi un nombre impair \(i\) puisque \(n=i.2^c\). On calcule son successeur impair unique \(\frac{3i+1}{2^b}\) où \(b\) est le nombre de fois qu’il aura fallu diviser par \(2\) le nombre pair \(3i+1\) pour le rendre impair. Le successeur impair est alors de la forme \(6a+1\) ou \(6a-1\) d’où l’on déduit facilement \(a\). Le triplet \((a, b, c)\) étant désormais connu, il est facile de vérifier que la formule donne bien le nombre choisi au départ. On constate d’ailleurs à cette occasion que la parité de \(b\) est correcte à savoir qu’on a bien \(b\) pair si la formule est exprimée avec \(6a+1\) et impair si la formule est exprimée avec \(6a-1\).

La formule se démontre aisément par récurrence sachant que

\(i.2^n-1 |3 \Rightarrow i.2^{n+2}-1 |3 \)

ce qui se démontre également par récurrence. On utilise ici la lettre \(i\) parce que ce nombre est impair dans ce contexte mais l’implication est vraie quel que soit \(i\), pair ou impair. On évite un exposant nul pour avoir une vraie puissance de \(2\). Si la formule est vraie pour \(n=1\), elle sera vraie pour tout exposant impair de la puissance de \(2\) ; si la formule est vraie pour \(n=2\), elle sera vraie pour tout exposant pair de la puissance de \(2\). Quand on aura montré que la formule précédente est vraie pour une petite valeur de \(a\), on en conclura qu’elle est vraie pour la parité de \(b\) utilisée en invoquant cette implication, sachant qu’on peut ne travailler que sur les nombres impairs donc avec \(c=0\).