Exercice : Suite de Syracuse

À faire

2025-2026

Extraire le code dans un fichier pour le compiler.

En mathématique, on appelle suite de Syracuse une suite d’entiers naturels définie de la manière suivante : On part d’un nombre entier plus grand que zéro ; s’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et on ajoute 1. En répétant l’opération, on obtient une suite d’entiers positifs dont chacun ne dépend que de son prédécesseur.

Par exemple, à partir de 14, on construit la suite des nombres : \(14, 7, 22, 11, 34, 17,\) \(52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2\dots\). C’est ce qu’on appelle la suite de Syracuse du nombre 14.

Lorsque le nombre \(1\) a été atteint, la suite des valeurs \(1, 4, 2, 1, 4, 2\dots\) se répète indéfiniment en un cycle de longueur 3, appelé cycle trivial.

1. Dans un nouveau fichier, définissez la procédure syracuse qui prend en paramètre une variable contenant un terme de la suite, calcule le terme suivant et le range dans la même variable.

   BEGIN SOLUTION

   void syracuse(int &u) {
       if (u % 2 == 0) u = u / 2;
       else            u = 3 * u + 1;
   }
   

   END SOLUTION

2. Dans le terminal, tapez la commande git add suivie du nom de votre fichier, afin que votre fichier soit pris en compte dans les futures soumissions de votre TP. Ceci est à faire à chaque fois que vous créez un nouveau fichier, nous ne le rappellerons plus dans la suite.

3. La fonction suivante calcule le nombre de fois qu’il faut itérer la suite pour arriver sur \(1\), à partir d’un \(u_n\) donné.

   int longueurTransient (int un){
       int i=0;
       while (un != 1) {
           syracuse(un);
           i++;
       }
       return i;
   }
   

   Cette fonction pourrait ne pas être définie pour tous les entiers. La conjecture de Syracuse dit qu’elle l’est, mais personne ne l’a jamais démontré! Écrivez un programme principal qui calcule cette fonction longueurTransient sur les nombres de 1 à 1000, et affiche le résultat, pour étudier son comportement.

   BEGIN SOLUTION

   void main() {
       for (int i = 1; i < 1000; i++) 
           cout << longeurTransient(i) << ", ";
   }
   

   END SOLUTION