En tête general

(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/

Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.

Suites de Syracuse (corrigé)¶

*En langage Python, l’écriture __a%b__ permet de renvoyer le reste de la division euclidienne de __a__ par __b__ (où __a__ et __b__ sont des nombres entiers positifs, __b__ non nul).*

0. Question préliminaire : Si a est une variable contenant un nombre entier positif :

Quelles sont les valeurs que peut renvoyer la saisie ci-dessous ?

a=35 #Modifier cette valeur pour les tests
a%2

1

A quelles propriétés du nombre a correspondent chacune de ces valeurs ?

*__Définition de la suite de Syracuse associée à un nombre $a$ :__*

A partir d’un entier non nul __$a$__, on peut construire une suite de nombres de la façon suivante :

$u_0=a$ et

$u_{n+1} = \begin{Bmatrix} \frac{u_n}{2} & \hbox{ si $u_n$ est pair} \\ 3u_n+1 & \hbox{ si $u_n$ est impair} \end{Bmatrix} $

(chaque terme de la suite est obtenu en divisant le précédent par 2 si celui-ci est pair, et en le multipliant par 3 et en ajoutant 1 s’il est impair)

La vidéo ci-dessous présente la construction d'une suite de Syracuse.

La figure dynamique qui suit permet de représenter une suite de Syracuse.

*(Pour faire apparaître et activer la figure dynamique, sélectionner la cellule et valider avec SHIFT+Entrée).*

#Sélectionner cette zone puis SHIFT+ENTREE
from IPython.display import display, HTML ; display(HTML('fig_dyn_GeoGebra/Syracuse.html'))

1. Calculer, à la main, les 6 premiers termes de la suite de Syracuse associée au nombre 17, et vérifier à l'aide de la figure dynamique précédente.

2. Ecrire une fonction Python suiv_Syracuse(p) :

qui reçoit en argument un terme p d’une suite de Syracuse ;
qui renvoie le terme suivant de la suite.

NOTE : Pour s’assurer que la valeur renvoyée soit de type int, on pourra écrire la division sous la forme // qui renvoie le quotient entier d’une division.

def suiv_Syracuse(p):
    "calcul du terme suivant d'une suite de Syracuse"
    if p%2==0:
        return p//2
    else:
        return 3*p+1

suiv_Syracuse(17)

52

3. On considère la fonction Python Deb_Syracuse(a) suivante :

def Deb_Syracuse(a) :
    L=[a]
    for k in range(3) :
        n=len(L)
        suiv=suiv_Syracuse(L[n-1])
        L.append(suiv)
    return L

Compléter le tableau suivant avec les valeurs prises successivement par les variables, si on appelle la fonction Deb_Syracuse(a) avec a=7.

k	suiv	L
/		[ 7 ]
0
1
2

Vérifier que la liste renvoyée par l’instruction >>> Deb_Syracuse(7) est cohérente avec votre tableau.

Deb_Syracuse(7)

[7, 22, 11, 34]

Quelle est l’utilité de cette fonction Deb_Syracuse(a) ?

4. Ecrire une fonction Python Tab_Syracuse(a,N) :

qui reçoit en arguments le 1er terme a d’une suite de Syracuse et un nombre entier n≥1 ;
qui renvoie la liste des N premiers termes de cette suite de Syracuse.

def Tab_Syracuse(a,N):
    "établit la liste des N premiers termes d'une suite de Syracuse"
    L=[a]
    for k in range(N-1) :
        a=suiv_Syracuse(a)
        L.append(a)
    return L

Tab_Syracuse(17,10)

[17, 52, 26, 13, 40, 20, 10, 5, 16, 8]

*__Notion de vol associé à un nombre a :__*

On appelle vol correspondant à a, la liste des valeurs obtenues par la suite de Syracuse à partir de a, et s’arrêtant au premier terme valant 1. (*)

On appelle durée du vol le nombre de termes de la liste, et on appelle altitude maximale la plus grande valeur de cette liste.

5. Compléter, à la main, la suite de nombres obtenus à la question 1) pour obtenir le vol correspondant au nombre 17. Quelle est la longueur de ce vol ? Quelle est l’altitude maximale de ce vol ?

6. Ecrire une fonction Python Vol_Syracuse(a) :

qui reçoit en argument le 1er terme a d’une suite de Syracuse
qui renvoie la liste correspondant au vol obtenu avec a.

def Vol_Syracuse(a):
    "établit la liste correspondant à un vol"
    L=[a]
    n=len(L)
    while a!=1: #L[-1] donne le dernier élément de la liste L    
        a=suiv_Syracuse(a)
        L.append(a)
    return L

Vol_Syracuse(17)

[17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

7. Expliquer, pour chacune des instructions, ce que représente le résultat obtenu.

v=Vol_Syracuse(137)
v

[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]

max(v)

9232

len(v)

91

8. Prolongements possibles :

Ecrire une fonction Python qui renvoie la plus petite valeur a dont le vol atteint une altitude au moins égale à 150. Adapter la fonction pour qu’elle renvoie la plus petite valeur a dont le vol atteint une altitude au moins égale à M, où M est passé en argument.
Ecrire une fonction Python qui renvoie la plus petite valeur a dont la durée de vol est supérieure à 40. Adapter la fonction pour qu’elle renvoie la plus petite valeur a dont la durée de vol est supérieure à T, où T est passé en argument.
Ecrire une fonction Python qui renvoie la valeur de a inférieure à 100000 pour laquelle le vol est le plus long. Adapter la fonction pour qu’elle renvoie la valeur de a inférieure à N pour laquelle la durée de vol est maximale, où N est passé en argument.
Ecrire une fonction Python qui renvoie la valeur de a inférieure à 100000 pour laquelle l’altitude atteinte est maximale. Adapter la fonction pour qu’elle renvoie la valeur de a inférieure à N pour laquelle l’altitude atteinte est maximale, où N est passé en argument.

def altitude_150():
    "renvoie le plus petit a tel que le vol atteint l'altitude 150"
    a=1
    while max(Vol_Syracuse(a))<150:
        a=a+1
    return a
    
def duree_vol_40():
    "renvoie le plus petit a tel que le vol a une durée d'au moins 40"
    a=1
    while len(Vol_Syracuse(a))<40:
        a=a+1
    return a    
        
def altitude(M):
    "renvoie le plus petit a tel que le vol atteint l'altitude M"
    a=1
    while max(Vol_Syracuse(a))<M:
        a=a+1
    return a
    
def duree_vol(T):
    "renvoie le plus petit a tel que le vol a une durée d'au moins T"
    a=1
    while len(Vol_Syracuse(a))<T:
        a=a+1
    return a     

def vol_le_plus_long(N):
    "renvoie la valeur de a inférieure à N pour laquelle le vol est le plus long"
    candidat=1
    longueur_cand=1
    for a in range(2,N):
        long_a=len(Vol_Syracuse(a)) #pour ne pas effectuer 2x le calcul
        if long_a>longueur_cand:
            candidat=a
            longueur_cand=long_a
    return candidat #on peut compléter avec: ,longueur

def vol_le_plus_haut(N):
    "renvoie la valeur de a inférieure à N pour laquelle l'altitude atteinte est maximale"
    candidat=1
    altitude=1
    for a in range(2,N):
        alt_a=max(Vol_Syracuse(a)) #pour ne pas effectuer 2x le calcul
        if alt_a>altitude:
            candidat=a
            altitude=alt_a
    return candidat #on peut compléter avec: ,altitude

# 8a , 8b , 8c , 8d
altitude_150() , duree_vol_40() , vol_le_plus_long(100000) , vol_le_plus_haut(100000)

(15, 27, 77031, 77671)

(*) NOTE: La conjecture de Syracuse stipule que quelle que soit la valeur a choisie, la suite de Syracuse finira par « atterrir », c'est-à-dire qu’elle atteindra au bout d’un nombre fini d’itérations la valeur 1. A ce jour, cette conjecture n’a jamais été démontrée, mais elle a été vérifiée pour tous les entiers inférieurs à $2^{62}≈4,6×10^{18}$… avec des ordinateurs évidemment.

Lothar Collatz (1910 – 1990) est à l’origine de cette conjecture

Collatz Lothar