La suite de Syracuse⚓︎
Exploration de la suite⚓︎
La suite de Syracuse
On appelle suite de Syracuse toute suite de nombres obtenue à l'aide de l'algorithme ci-dessous, avec U
un nombre entier strictement positif.
Tant que U > 1:
Si U est pair:
U ← U/2
Sinon:
U ← 3U+1
Afficher U
Même s'il n'y a aucune preuve dans le cas général, tous les nombres testés produisent une suite qui se termine par \(1\). L'existence, ou non, d'un nombre produisant une suite infinie reste un problème ouvert.
Plus d'information ici :
Exercice 3 (sur papier)
Calculer les valeurs successives obtenues en partant de 5 et jusqu'à arriver à 1.
Refaire de même en partant de 7 et de 21.
Solutions
- \(5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)
- \(7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)
- \(21 \rightarrow 64 \rightarrow 32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)
Déterminer la parité d'un entier
Pour tester si un nombre est pair, en Python, il faut utiliser le reste de la division euclidienne par 2 :
- Si le reste est 0, le nombre est pair ;
- Si le reste est 1, il est impair.
>>> 1563 % 2 == 0 # (1)!
False
>>> 4594 % 2 == 0 # (2)!
True
- 1563 n'est pas pair, donc le reste de la division euclidienne par 2 n'est pas 0, mais 1.
- 4594 es pair, donc le reste de la division euclidienne par 2 est 0.
Exercice 4
Compléter le code de la fonction prochain_syracuse
qui prend en paramètre un entier u
et qui renvoie la valeur qui vient après u
dans la suite de Syracuse.
Construire la liste des valeurs
La fonction suivante renvoie la liste des valeurs prises par la suite en partant de u
. Elle permettra de tester les résultats des autres fonctions. Il faut exécuter ce programme pour pouvoir l'utiliser ensuite.
Les listes Python
Une liste est une suite d'éléments séparés par des virgules et mis entre crochets. La liste vide est représentée par []
. La fonction len(liste)
permet de connaître le nombre d'éléments dans liste
.
>>> liste_vide = []
>>> liste = [4, 1, 3, 9, 21]
>>> len(liste) # le nombre d'éléments dans la liste
5 # il y en a bien 5
Il est possible d'ajouter des éléments en fin de la liste en faisant liste.append(element)
. On peut bien entendu rajouter plusieurs fois le même élément dans la liste.
>>> liste.append(7)
>>> liste.append(3)
>>> liste
[4, 1, 3, 9, 21, 7, 3] # On a bien mis 7 puis 3
Nous reviendrons plus tard sur ces listes.
# Tests
(insensible à la casse)(Ctrl+I)
Exercice 5
On appelle altitude maximale d'une suite de Syracuse le plus grand nombre de la suite.
Compléter le code de la fonction altitude_max
qui prend en paramètre un entier u
et qui renvoie l'altitude maximale en partant de u
.
Indice
Vous pouvez utiliser prochain_syracuse
.
>>> altitude_max(11)
52
>>> suite_syracuse(11)
[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
>>> altitude_max(32)
32
>>> suite_syracuse(32)
[32, 16, 8, 4, 2, 1]
# Tests
(insensible à la casse)(Ctrl+I)
Exercice 6
On appelle durée de vol la longueur d’une suite de Syracuse, en comptant le nombre de départ.
Écrire le code de la fonction duree_vol
qui prend en paramètre un entier u
et qui renvoie la durée de vol en partant de u
.
>>> duree_vol(1)
1
>>> duree_vol(7)
17
>>> suite_syracuse(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
# Tests
(insensible à la casse)(Ctrl+I)
# Tests
(insensible à la casse)(Ctrl+I)
Altitudes et durées records⚓︎
Exercice 7
Compléter le code de la fonction record_altitude
qui prend en paramètre un entier u_limite
et qui renvoie la valeur de u
qui donne la suite avec l’altitude maximale, en partant entre 1
et u_limite
.
La fonction renvoie également l’altitude maximale atteinte. En cas d’égalité en partant de deux valeurs différentes de u
, c’est la plus petite qui est renvoyée.
>>> record_altitude(10)
(7, 52) # le record est en partant de 7 et on atteint 52
>>> suite_syracuse(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
# Tests
(insensible à la casse)(Ctrl+I)
Exercice 8
À l'aide de la fonction précédente, trouver le nombre inférieur à 10 000 qui a l'altitude maximale.
Exercice 9
Écrire le code de la fonction record_duree
qui prend en paramètre un entier u_limite
et qui renvoie la valeur de u
qui donne la suite avec l’altitude maximale, en partant entre 1
et u_limite
.
La fonction renvoie également le record de durée atteint. En cas d’égalité en partant de deux valeurs différentes de u
, c’est la plus petite qui est renvoyée.
>>> record_duree(10)
(9, 20) # en partant de 9, on a une durée de vol de 20
>>> suite_syracuse(9)
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
# Tests
(insensible à la casse)(Ctrl+I)
# Tests
(insensible à la casse)(Ctrl+I)
Exercice 10
À l'aide de la fonction précédente, trouver le nombre inférieur à 10 000 qui a la duree de vol maximale.
Pour aller plus loin⚓︎
Exercice 11
Écrire le code de la fonction altitude_donnee
qui prend en paramètre un entier alt
et qui renvoie le plus petit nombre dont l’altitude maximale est supérieure ou égale à alt
.
Trouver le plus petit nombre dont l’altitude maximale dépasse 100 000 000.
>>> altitude_donnee(100)
15
>>> suite_syracuse(15)
[15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
# Tests
(insensible à la casse)(Ctrl+I)
Exercice 12
Écrire le code de la fonction duree_donnee
qui prend en paramètre un entier duree
et qui renvoie le plus petit nombre dont la durée de vol est supérieure ou égale à duree
.
Trouver le plus petit nombre dont la durée de vol dépasse 300.
>>> duree_donnee(100)
27
>>> suite_syracuse(27)
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
>>> len(suite_syracuse(27)) # La longueur de la suite obtenue en partant de 27
112
# Tests
(insensible à la casse)(Ctrl+I)
# Tests
(insensible à la casse)(Ctrl+I)