dm d’informatique n˚2
La suite de Syracuse
Dans tout le sujet, on pourra décrire les algorithmes en langage naturel ou en Python. Lorsqu’il sera question
d’un tableau indexé à partir de 1, comme ce n’est pas la convention en Python, on pourra tout simplement
créer un tableau contenant une case de plus et ignorer la case d’indice 0.
On considère dans ce problème la suite (xn )n≥0 définie par son premier terme x0 > 0 et la relation de
récurrence
(
xn
si xn est pair,
xn+1 =
2
3xn + 1
sinon.
Partie I — Calcul des termes de la suite
1˚) Écrire un algorithme qui étant donné x0 > 0 affiche tous les termes de la suite jusqu’à ce que l’un d’entre
eux soit égal à 1, et s’arrête alors. On ne demande pas de prouver la terminaison de cet algorithme.
2˚) Que fait la suite qui démarre à x0 = 1 ? Plus généralement, que se passe-t-il pour une suite partant
d’un x0 quelconque, et telle que xn0 = 1 pour un certain indice n0 ?
3˚) Quelle suite obtient-on en partant de x0 = 7 ?
Partie II — Temps de vol
Le temps de vol de la suite démarrant à x0 > 0, noté v(x0 ), est le plus petit indice n tel que xn = 1.
1˚) Écrire un algorithme qui calcule le temps de vol de la suite, connaissant x0 . L’utiliser pour calculer
v(127), puis v(2 361 235 441 021 745 907 775).
2˚)
a) Écrire un algorithme qui étant donné un entier N détermine le plus petit entier x0 > 0 tel que
v(x0 ) ≥ N.
b) Que donne cet algorithme appliqué à N = 100 ?
3˚) On se donne un tableau T de taille M, dont les cases sont indexées à partir de 1. On souhaite remplir
T de sorte que la case T[i] contienne la valeur de v(i).
a) Supposons avoir calculé v(1), v(2), . . ., v(m) ; on souhaite calculer v(m + 1). Soit xn le premier
terme de la suite commençant à x0 = m + 1 tel que xn < m + 1. Exprimer v(m + 1) en fonction
de n et des v(i) déjà calculés.
b) En déduire un algorithme qui étant donné le nombre M construit ce tableau T.
c) Écrire un algorithme qui détermine, parmi tous les x0 inférieur à une valeur donnée M, détermine
celui qui a le temps de vol le plus élevé. Qu’obtient-on pour M = 10000 ?
Partie III — Sommets de la suite
Nous dirons qu’un nombre x0 est un sommet si tous les termes de la suite qui démarre à x0 lui sont strictement
inférieurs.
1˚) Parmi les nombres inférieurs à onze, lesquels sont des sommets ? Quel est le plus petit sommet ?
Lycée Saint Louis — MP 1/MP* 2
1
DM d’informatique n˚2
2˚)
a) Démontrer qu’un nombre x0 est un sommet si et seulement il existe un indice n ≥ 1 tel que xn
est un sommet et tel que xi < x0 pour tout i ∈ {1 ; 2 ; . . . ; n}.
b) En déduire un algorithme qui étant donné un entier M construit un tableau T[1 : M] de booléens
tel que T[i] est vrai si et seulement si i est un sommet.
3˚) Écrire un algorithme qui étant donné un tableau T[1 : M] de booléens construit la liste de tous les
indices i pour lesquels T[i] est vrai.
4˚) Déduire des questions qui précèdent le nombre de sommets inférieurs à 1000. Il n’est évidemment pas
demandé de calculer ce nombre à la main.
5˚) Quel est le plus grand sommet parmi toutes les suites ayant un premier terme inférieur à 1 000 000 ?
Partie IV — Plus longues descentes
Une descente dans une suite de Syracuse est une succession de divisions par 2. Par exemple, si xn = m × 2k
pour un entier impair m, la sous-suite finie (xn ; xn+1 ; . . . ; xn+k ) est une descente de longueur k. Le terme
xn+k+1 est alors égal à 3xn+k + 1 = 3m + 1, et est ainsi supérieur à xn+k .
1˚) Écrire un algorithme qui étant donné un nombre x0 > 0, détermine la plus longue descente dans la
suite de Syracuse commençant à x0 . On donnera la longueur et le premier terme de cette descente.
2˚) Écrire un algorithme qui étant donné un entier naturel x non nul renvoie l’unique couple (m ; k) tel
que x = m × 2k , où m est un entier impair.
3˚) Déterminer la plus longue descente qu’on trouve dans les suites dont le premier terme est inférieur à
1 000 000.
Lycée Saint Louis — MP 1/MP* 2
2
DM d’informatique n˚2
© Copyright 2024 ExpyDoc
