Exercice 3 — Transformation de Collatz — Olympiades 2018 Poitiers

Sujet

La transformation de Collatz d'un nombre entier strictement positif \(a\) est définie de la façon suivante :

\[ \left\{\begin{array}{c} \text { si } a \text { est pair, alors } a \text { devient } \frac{a}{2} \\ \text { si } a \text { est impair, alors } a \text { devient } \frac{3 a+1}{2} \end{array}\right. \]

La trajectoire du nombre \(a\) est alors constituée des valeurs prises par \(a\) au cours d'une succession de transformations de Collatz. Par exemple, on peut représenter la trajectoire de 12 ainsi :

Temps de vol et altitude maximale :

Le temps de vol de \(a\) est le nombre minimal de transformations à l'issue desquelles la trajectoire de \(a\) atteint 1, si cela arrive. On le note \(t(a)\).
L'altitude maximale de \(a\) est le plus grand nombre apparaissant dans la trajectoire de \(a\). On la note \(m(a)\). Par exemple, le temps de vol de 12 est \(t(12)=7\) et son altitude maximale est \(m(12)=12\).

Déterminer la trajectoire de 13 , ainsi que \(t(13)\) et \(m(13)\).
L'algorithme ci-contre doit calculer \(t(a)\) et \(m(a)\), le nombre entier strictement positif \(a\) étant donné en entrée. Compléter cet algorithme.
Calculer les 7 premiers termes de la trajectoire de 27, puis les 10 premiers termes de la trajectoire de 2018. Que dire alors de la trajectoire de ces deux nombres ?
L'algorithme précédent appliqué à \(a=27\) donne \(t(27)=71\) et \(m(27)=4616\). Déterminer \(t(2018)\) et \(m(2018)\).
Combien existe-t-il de trajectoires dont le temps de vol vaut 6 ?

Entrée : nombre entier strictement positif \(\boldsymbol{a}\).
Sorties : temps de vol \(\boldsymbol{t}\), altitude maximale \(\boldsymbol{m}\).
\(\boldsymbol{t}=\mathbf{0}\)
\(\boldsymbol{m}=\boldsymbol{a}\)
Tant que \(\boldsymbol{a}\) est différent de 1, faire :
    Si \(a\) est pair, alors \(a\) prend la valeur
    sinon \(a\) prend la valeur
    Fin si
    \(\boldsymbol{t}\) prend la valeur

\(\_\_\_\_\)

    Si \(a>m\), alors
    Fin si
Fin tant que
Afficher \(\boldsymbol{t}\)
Afficher \(\boldsymbol{m}\)