%display latex
from IPython.display import HTML
styles = """
<style>
h1 {
text-align: center ;
font-weight: bold ;
margin: 0.5em !important ;
}
</style>
"""
HTML(styles)
import matplotlib.pyplot as plt # on importe la fonction pyplot du module matplotlib (qu'on abrège en plt) permettant de dessiner des graphiques
Conjecture de Syracuse
Définition
La suite de Syracuse $(s_k)$ pour un nombre entier $n$ est définie par :$ \left\{ \begin{array}{ll} s_0=n \\ \forall k \geq 0, s_{k+1}= \left\{ \begin{array}{ll} \cfrac{s_k}{2} & \text{si $s_k$ est pair} \\ 3 \times s_k + 1 & \text{si $s_k$ est impair} \\ \end{array} \right. \end{array} \right. $
Exemples¶
pour n = 3 : 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...
pour n = 105 : 105, 316, 158, 79, 238, 119, 358, 179, 538, 269, 808, 404, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20,10, 5, 16, 8, 4, 2, 1, 4, 2, 1 ...
Conjecture¶
On se rend compte facilement que si un élément de la suite est de la forme $2^k$ , alors les suivants seront $2^{k-1}$, $2^{k-2}$, $\dots$, 2, 1, puis la suite entrera dans une boucle infinie 4, 2, 1, 4, 2, 1, ...
On a constaté (en 2023) que pour toute valeur de $n$ jusqu'à $2^{68}$, soit environ $2\times 10^{20}$, on a ce comportement.
La question (non encore résolue début 2024) est : est-ce que pour tout entier $n$, la suite de Syracuse de $n$ finit par avoir ce comportement ?
Programmes construisant la "liste" de Syracuse d'un entier¶
On appellera liste de Syracuse de l'entier $n$ la liste (finie) obtenue en tronquant la suite de Syracuse $(s_k)_{k \in \mathbb{N}}$ de $n$ au premier entier $k$ tels que $s_k$=1
## Version procédurale itérative
def Syr1(n):
k = n
while k != 1:
print(k, end=", ")
if k % 2 == 0:
suivant = k / 2
else:
suivant = 3 * k + 1
k = suivant
print(k)
Syr1(129)
129, 388, 194, 97, 292, 146, 73, 220, 110, 55, 166, 83, 250, 125, 376, 188, 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
## Version procédurale récursive
def Syr2(n):
print(n, end=", ")
if n % 2 == 0:
suivant = n / 2
else:
suivant = 3 * n + 1
if suivant == 1:
print(suivant)
else:
Syr2(suivant)
Syr2(100)
100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
## Version fonctionnelle itérative
def syr3(n):
lst = [n]
d = lst[-1] # lst[len(lst) - 1]
while d != 1:
if d % 2 == 0:
lst = lst + [d / 2]
else:
lst = lst + [3 * d + 1]
d = lst[-1]
return lst
print(syr3(1005))
# G = plt.plot(syr3(1005))
[1005, 3016, 1508, 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]
## Version fonctionnelle récursive
def syr4(n):
if n == 1:
return [1]
else:
if n % 2 == 0:
suivant = int(n / 2)
else:
suivant = 3 * n + 1
return [n] + syr4(suivant)
print(syr4(1005))
[1005, 3016, 1508, 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]
Longueurs des listes de Syracuse (durée du vol)¶
for i in range(1, 100):
print(len(syr3(i)), end = "; ")
#longueurs = [len(syr3(i)) for i in range(1, 11)] # suite des longueurs
#G = plt.plot(longueurs)
1; 2; 8; 3; 6; 9; 17; 4; 20; 7; 15; 10; 10; 18; 18; 5; 13; 21; 21; 8; 8; 16; 16; 11; 24; 11; 112; 19; 19; 19; 107; 6; 27; 14; 14; 22; 22; 22; 35; 9; 110; 9; 30; 17; 17; 17; 105; 12; 25; 25; 25; 12; 12; 113; 113; 20; 33; 20; 33; 20; 20; 108; 108; 7; 28; 28; 28; 15; 15; 15; 103; 23; 116; 23; 15; 23; 23; 36; 36; 10; 23; 111; 111; 10; 10; 31; 31; 18; 31; 18; 93; 18; 18; 106; 106; 13; 119; 26; 26;
Maxima de la liste de Syracuse (altitude maximale)¶
maxima = [max(syr3(i)) for i in range(1, 101)]
G = plt.plot(maxima)
Antoine Totaro¶
def Eratosthene(n):
#retourne la tableau des nombres premiers <= n (crible d'Eratosthene)
#Si la valeur du nombre dans le tableau est différente de 0, donc égale
#au nombre, celui-ci est premier
tableau = [0,0] + [i for i in range(2, n)]
for i in range(2, n):
if tableau[i] != 0:
# c'est un nombre 1er: on le garde, mais on neutralise ses multiples
for j in range(i*2, n, i):
tableau[j] = 0
#return(tableau)
return [n for n in tableau if n != 0]
def est_premier(n):
if n == 2:
return True
d = 2
ok = True
while d < n:
if n % d == 0:
ok = False
break
d = d + 1
return ok
def premier(k):
""" Renvoie le k-ième nombre premier, avec premier(1) = 2 """
lst = [2]
n = 3
while len(lst) <= k:
if est_premier(n) == True:
lst = lst + [n]
n = n + 1
return lst[-2]
def consommation(n):
""" consommation entre les stations n et n + 1 """
return premier(n + 1) - premier(n)
def nbLitresEnSortant(n):
if n == 1:
return 2
else:
return nbLitresEnSortant(n - 1) - consommation(n - 1) + premier(n)
n = int(input("Jusqu'à quelle station voulez vous arriver au minimum, tapez son numéro ? : "))
"""
print("en sortant de la station", n, "(numéro", premier(n), ")", "vous avez", nbLitresEnSortant(n), "litres de carburant et vous allez en consommer", consommation(n), "pour arriver à la station suivante")
"""
for i in range(1, n + 1):
print("en sortant de la station", i, "(numéro" , str(premier(i)) + ")", "vous avez", nbLitresEnSortant(i), "litres de carburant et vous allez en consommer", premier(i + 1) - premier(i), "pour arriver à la station suivante")
"""
n=int(input("Jusqu'à quelle station voulez vous arriver au minimum, tapez son numéro ? : "))+1
#on suppose qu'on peut traverser le désert avec n stations
TableauNbPremiers=Eratosthene(n+1)
#print("Les nombre premirs inférieurs à "+str(n)+" : ")
#print(TableauNbPremiers)
print(TableauNbPremiers)
JePeuxTraverser=True # on suppose qu'on pourra traverser, a priori
NbLitresDansLeReservoir=0
for i in range(2,n):
NbLitresDélivrés=TableauNbPremiers[i] #nb de litres délivré à la station i
NbLitresDélivrés=Eratosthene(n-1)
NbLitresDansLeReservoir=NbLitresDansLeReservoir+NbLitresDélivrés
# nb litres dans le réservoir après l'avoir rempli à la staztion i
NbLitresNécessaires=TableauNbPremiers[i+1]-TableauNbPremiers[i]
#nb de litres nécessaires pour aller de la station n à la station i+1
if NbLitresDansLeReservoir-NbLitresNécessaires<=0:
#pas assez d'essence pour rallier la station suivante
JePeuxTraverser=false # on est obligé de s'arrêter faute d'essence
break # c'est le cas de le dire, panne d'essence
else: #on continue le parcours dans le désert jusqu'à la station suivante
NbLitresDansLeReservoir=NbLitresDansLeReservoir-NbLitresNécessaires
#j'enlève du réservoir ce qui a été consommé pour arriver à la station suivante
if JePeuxTraverser==True:
print("Bravo vous êtes toujours vivant dans le désert, courage ! Vous êtes arrivé à la station n° : "+str(i))
print("Dans votre réservoir il reste : ",str(NbLitresDansLeReservoir)+" litres")
else:
print("Mince, vous êtes tombé en panne d'essence ! Courage Michel Damiens va venir vous sauver !")
print("Vous êtes à la station n° : "+str(i))
print("Dans votre réservoir il reste : ",str(NbLitresDansLeReservoir)+" litres")
"""
en sortant de la station 1 (numéro 2) vous avez 2 litres de carburant et vous allez en consommer 1 pour arriver à la station suivante en sortant de la station 2 (numéro 3) vous avez 4 litres de carburant et vous allez en consommer 2 pour arriver à la station suivante en sortant de la station 3 (numéro 5) vous avez 7 litres de carburant et vous allez en consommer 2 pour arriver à la station suivante en sortant de la station 4 (numéro 7) vous avez 12 litres de carburant et vous allez en consommer 4 pour arriver à la station suivante en sortant de la station 5 (numéro 11) vous avez 19 litres de carburant et vous allez en consommer 2 pour arriver à la station suivante en sortant de la station 6 (numéro 13) vous avez 30 litres de carburant et vous allez en consommer 4 pour arriver à la station suivante en sortant de la station 7 (numéro 17) vous avez 43 litres de carburant et vous allez en consommer 2 pour arriver à la station suivante en sortant de la station 8 (numéro 19) vous avez 60 litres de carburant et vous allez en consommer 4 pour arriver à la station suivante en sortant de la station 9 (numéro 23) vous avez 79 litres de carburant et vous allez en consommer 6 pour arriver à la station suivante en sortant de la station 10 (numéro 29) vous avez 102 litres de carburant et vous allez en consommer 2 pour arriver à la station suivante
def CalculSuite(n,ElémentsDeLaSuite):
if n==1:
# condition de sortie : on a fini , on est arrivé au dernier élément de la suite
#print(n)
ElémentsDeLaSuite=ElémentsDeLaSuite+[(n)]
print(ElémentsDeLaSuite)
else:
if n%2 == 0: #n est pair
n=n/2
else: # n est impair
n=3*n+1
#print(n)
ElémentsDeLaSuite=ElémentsDeLaSuite+[(n)]
CalculSuite(n,ElémentsDeLaSuite) # on itère le calcul tant que n est différent de 1
N=int(input("Vous voulez calculer la suite de Syrecuse pour quel nombre ? "))
print("Voici tous les éléments de la suite :")
ElémentsDeLaSuite=[]
CalculSuite(N,ElémentsDeLaSuite)
Voici tous les éléments de la suite : [2, 1, 1]
def Eratosthene(n):
#retourne la tableau des nombres premiers <= n (crible d'Eratosthene)
#Si la valeur du nombre dans le tableau est différente de 0, donc égale
#au nombre, celui-ci est premier
tableau = [0,0] + [i for i in range(2, n)]
for i in range(2, n):
if tableau[i] != 0:
# c'est un nombre 1er: on le garde, mais on neutralise ses multiples
for j in range(i*2, n, i):
tableau[j] = 0
return(tableau)
n=int(input("Jusqu'à quelle station voulez vous arriver au minimum, tapez son numéro (<150) ? : "))
#on suppose qu'on peut traverser le désert avec n stations
TableauNbPremiers=Eratosthene(1001)
TableauNbPremiersUniquement=[]
#print("Les nombre premirs inférieurs à "+str(n)+" : ")
#print(TableauNbPremiers)
for i in range(0,1001):
if TableauNbPremiers[i]!=0:
TableauNbPremiersUniquement=TableauNbPremiersUniquement+[TableauNbPremiers[i]]
#print(TableauNbPremiersUniquement)
JePeuxTraverser=True # on suppose qu'on pourra traverser, a priori
NbLitresDansLeReservoir=0
for i in range(0,n):
NbLitresDélivrés=TableauNbPremiersUniquement[i] #nb de litres délivré à la station i
NbLitresDansLeReservoir=NbLitresDansLeReservoir+NbLitresDélivrés
# nb litres dans le réservoir après l'avoir rempli à la station i
NbLitresNécessaires=TableauNbPremiersUniquement[i+1]-TableauNbPremiersUniquement[i]
#nb de litres nécessaires pour aller de la station n à la station i+1
if NbLitresDansLeReservoir-NbLitresNécessaires<=0:
#pas assez d'essence pour rallier la station suivante
JePeuxTraverser=false # on est obligé de s'arrêter faute d'essence
break # c'est le cas de le dire, panne d'essence
else: #on continue le parcours dans le désert jusqu'à la station suivante
NbLitresDansLeReservoir=NbLitresDansLeReservoir-NbLitresNécessaires
#j'enlève du réservoir ce qui a été consommé pour arriver à la station suivante
NbLitresDansLeReservoir=NbLitresDansLeReservoir+NbLitresNécessaires
if JePeuxTraverser==True:
print("Bravo vous êtes toujours vivant dans le désert, courage ! Vous êtes arrivé à la station n° : "+str(i+1))
print("Dans votre réservoir il reste : ",str(NbLitresDansLeReservoir)+" litres")
else:
print("Mince, vous êtes tombé en panne d'essence ! Courage Michel Damiens va venir vous sauver !")
print("Vous êtes à la station n° : "+str(i))
print("Dans votre réservoir il reste : ",str(NbLitresDansLeReservoir)+" litres")
Bravo vous êtes toujours vivant dans le désert, courage ! Vous êtes arrivé à la station n° : 4 Dans votre réservoir il reste : 12 litres