Exercice 2 — Des nombres qui volent

Sujet

Soit \(N\) un nombre entier naturel non nul. On s'intéresse à la liste de nombres, numérotés \(u_{0}, u_{1}, u_{2}, u_{3}, \ldots\), construite de la façon suivante :
\(u_{0}=N\). Si un élément \(a\) de la liste est pair, son suivant est \(\frac{a}{2}\) et s'il est impair son suivant est \(3 a+1\).
Ainsi, on a pour \(N=5: u_{0}=5, u_{1}=16, u_{2}=8, u_{3}=4, u_{4}=2, u_{5}=1, u_{6}=4, u_{7}=2 \ldots\)
et pour \(N=7: u_{0}=7, u_{1}=22, u_{2}=11, u_{3}=34, u_{4}=17, u_{5}=52, u_{6}=26, u_{7}=13, u_{8}=40 \ldots\)
1 . On suppose que \(N=3\).
a. Déterminer les cinq premiers termes de la liste associée à ce nombre.
b. Quel est le plus petit entier \(m\) tel que \(u_{m}=1\) ?
c. Que peut-on dire des termes suivants ?
2. On suppose que \(N=7\).
a. Déterminer le plus petit entier \(m\) tel que \(u_{m}=1\). On dit que \(m\) est la durée de vol du nombre \(N\).
b. Représenter graphiquement les 20 premiers termes de la liste.

On portera en abscisse l'entier \(i\) et en ordonnée le nombre \(u_{i}\).
c. Quel est le plus grand terme de cette liste? Il s'agit de l'altitude maximale du vol du nombre \(N\).
d. Quel est le plus petit entier \(i\) tel que \(u_{i+1} 3. On suppose que \(N=11\).
a. Quelle est sa durée de vol?
b. Quelle est sa durée de vol en altitude ?
c. Quelle est l'altitude maximale de son vol?

Si \(N\) est un entier naturel non nul, on dit que sa durée de vol est finie s'il existe un entier naturel \(m\) tel que \(u_{m}=1\).
La conjecture de Syracuse affirme que tout nombre a une durée de vol finie. Elle n'a pas été démontrée à ce jour.
4. On suppose que le nombre \(N\) a une durée de vol finie.

Écrire un algorithme qui permette de calculer sa durée de vol.
5. Montrer que pour tout entier naturel non nul \(p\), il existe au moins un entier \(N\) ayant une durée de vol égale à \(p\).
6. Quels sont les nombres ayant une durée de vol en altitude nulle?
7. Soit \(N\) un entier naturel supérieur ou égal à 2 ayant une durée de vol finie. Justifier qu'il a une durée de vol en altitude finie.
8. Soit \(N\) un entier naturel supérieur ou égal à 2 , tel que :

• tout nombre entier inférieur à \(N\) a une durée de vol finie,
• \(N\) a une durée de vol en altitude finie.

Montrer que \(N\) a une durée de vol finie.
9. On peut écrire tout nombre entier naturel \(N\) sous l'une des formes \(4 k, 4 k+1,4 k+2,4 k+3\) avec \(k \in \mathbb{N}\).
a. Montrer pour trois de ces quatre cas que le nombre \(N\) a une durée de vol en altitude finie.
b. Quels sont les nombres entiers naturels non nuls ayant une durée de vol en altitude égale à 2 ?

On démontre (ce résultat est ici admis) à partir des questions 8 et 9 , que si \(N\) est un entier naturel non nul quelconque, les affirmations suivantes sont équivalentes :
a. Tout nombre inférieur ou égal à \(N\) a une durée de vol finie.
b. Tout nombre inférieur ou égal à \(N\) a une durée de vol en altitude finie.
10. a. Expliquer pourquoi, pour vérifier que les 10000 premiers nombres entiers non nuls ont une durée de vol finie, il suffit de faire des calculs pour 2500 nombres.
b. Écrire un algorithme qui permette, en effectuant le moins de calculs possibles, de déterminer l'entier naturel non nul inférieur ou égal à 10000 ayant la durée de vol en altitude la plus longue. Justifier votre choix.
11. Proposer une méthode qui permette de limiter encore de façon significative les calculs à faire pour vérifier si les 10000 premiers nombres entiers non nuls ont une durée de vol finie.