Inscription / Connexion Nouveau Sujet
Suite de syracuse programmation
Salut,
On connait tous la suite de syracuse : , on définie
, et ensuite si
est pair alors
, sinon
On définit le temps de vol : c'est le plus petit indice n tel que
On définit l'altitude maximale : c'est la valeur maximale de la suite.
Je voulais donc créer un petit programme qui calculait tout pour moi mais je n'y arrive pas il retourne rien...
Notez que les fonctions log_vol(n) et voir_vol(n) sont des fonctions qui devaient m'aider pour créer le graphique du vol du log d'un entier n, mais le problème n'est pas là.. même quand je fais un simple
print( vol(5))
import numpy as np
import matplotlib.pyplot as plt
from math import *
def v(n):
if n % 2 ==0:
return n // 2
return 3*2+1
def vol(n):
res = [n]
while n > 1:
n = v(n)
res.append(n)
return res
def temps_vol(n):
return len(vol(n))-1
def altitude(n):
return max(vol(n))
def log_vol(n):
""" Logarithme du vol de n"""
res = [log(n)]
while n > 1:
n = v(n)
res.append(log(n))
return res
def voir_vol(n):
""" Graphe du logarithme du vol de n"""
plage_x = log_vol(n)
plt.plot(plage_x, marker=".", markersize=5)
plt.grid()
plt.title("Logarithme du vol de n = " + str(n))
plt.show()
Je me suis trompé en recopiant l'énoncé de la suite de Syracuse, c'est bien quand est pair que
et quand
est impair que
Ensuite, je dois ajouter une fonction qui pour un argument n calcule l'entier ayant le plus grand temps de vol. Calculer pour n=1000 et n=10000.
Je réponds alors :
def valuemaxtempsdevol(n):
""" Entier plus petit que n ayant le plus grand temps de vol"""
vmax, champ = 0, 1
for i in range(2 ,n+1):
if temps_vol(i) > vmax:
vmax = temps_vol(i)
champ = i
return champ
et je trouve valuemaxtempsdevol(1000)=871 et valuemaxtempsdevol(10000)=6171
avec temps_vol(871)=178 et temps_vol(6171)=261.
C'est la prochaine question que je comprends pas.
Ecrire une fonction classe_vol(n) calculant la liste triée de tous les entiers dont le temps de vol est exactement n.
On pourra remarquer (justifier) que pour tout entier n ∈ N∗, alors:
• si n = 4 [6], alors les antécédents de n par la fonction v sont m=2n et m=n−13
•• sinon, le seul antécédent de n par la fonction v est m=2n .
On écrira une version itérative et on pourra écrire aussi une version récursive de cette fonction classe_vol(n).
Vérifier par exemple que classe_vol(15) = [22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768].
Après reflexion, je crois avoir trouvé :
def classe_vol(n):
""" Liste triée des entiers de temps de vol n """
res = [1]
for i in range(n):
t = []
for v in res:
if (v % 6 == 4) and (v > 4):
t.append((v-1) // 3)
t.append(2*v)
res = list(t)
res.sort()
return resçane m'indique pas d'où sortent les 2 ppts, mais bon ça fonctionne.
Si jamais des gens veulent jeter un coup d'œil, voici mon code qui fonctionne parfaitement 
Il reste néanmoins des amélioration à faire, par exemple j'ai une erreur console quand je rentre des valeurs non entières pour n ou fonction.
Néanmoins, en me creusant la tête j'ai trouvé une approximation de TV(n), même si trouver k sans calculer de limite (que je ne sais pas faire) est un peu compliqué.
En gros, il permet d'approximer le nombre d'entiers dont le temps est égal à n.
L'approximation repose sur l'affirmation que , mais je ne saurai comment le démontrer...
Si quelqu'un à une idée je suis preneur.
Voici le programme :
import numpy as np
import matplotlib.pyplot as plt
from math import *
def v(n):
if n % 2 ==0:
return n // 2
return 3*n+1
def vol(n):
""""vol de n(liste)"""
res = [n]
while n > 1:
n = v(n)
res.append(n)
return res
def temps_vol(n):
""" temps de vol de n"""
return len(vol(n))-1
def altitude(n):
""" altitude de n """
return max(vol(n))
def log_vol(n):
""" Logarithme du vol de n"""
res = [log(n)]
while n > 1:
n = v(n)
res.append(log(n))
return res
def voir_vol(n):
""" Graphe du logarithme du vol de n"""
plage_x = log_vol(n)
plt.plot(plage_x, marker=".", markersize=5)
plt.grid()
plt.title("Logarithme du vol de n = " + str(n))
plt.show()
def valuemaxtempsdevol(n):
""" Entier plus petit que n ayant le plus grand temps de vol"""
vmax, champ = 0, 1
for i in range(2 ,n+1):
if temps_vol(i) > vmax:
vmax = temps_vol(i)
champ = i
return champ
def classe_vol(n):
""" Liste triée des entiers de temps de vol n """
res = [1]
for i in range(n):
t = []
for v in res:
if (v % 6 == 4) and (v > 4):
t.append((v-1) // 3)
t.append(2*v)
res = list(t)
res.sort()
return res
def suite_TV(n):
"""Liste des TV(i+1)/TV(i) avec TV(i) = cardinal{k /i sachant que temps_vol(k}=i """
res, TV = [1], [1]
for i in range(n + 1):
t = []
for v in res:
if (v % 6 == 4) and (v > 4):
t.append((v-1) // 3)
t.append(2*v)
res = list(t)
TV.append(len(res))
plage_x = [TV[i+1] / TV[i] for i in range(n)]
return plage_x
## On va tendre vers c = environ 1.263..., on peut alors chercher Tv(n) qui est environ égale à k*c^n
## on trouve avec la fonction classe_vol que k est environ égale à 0.664 (en resolvant l'équation kc^n=TV(n) avec n=28 ==> k approx= 460/1.263^28) et alors TV(n) environ égale à 0.664*c^n.
def approxtv(n):
c = 1.2636004154018214
print(int(0.664*(c**n)))
print("Bienvenue dans le programme sur la suite de Syracuse ! :")
print("Ce programme est constitué de 5 fonction : vol(n), temps_vol(n), altitude(n), voir_vol(n) et valuemaxtempsdevol(n), classe_vol, suite_TV, tv(n)")
print("Elles retournent respectivement, le vol d'un nombre n, le nombre d'étapes pour atteindre 1, la valeure maximale du vol, le grpahe du log du vol de n et enfin l'entier inférieur à n ayant le plus grand temps de vol,puis la listé triée des entiers de temps de vol n, puis la liste des Tv(i+1)/Tv(i) avec TV(n) le nombre d'entiers dont le temps de vol est égale à n ")
print("tv(n)=kc^n reste une approximation du nombre dont le temps de vol est égal à n, pour être plus précis mais beaucup moins efficace il faudrait regarder la taille de la liste générée par classe_vol(n) ")
print("la fonction suite_tv nous permet de trouver c, et n'est pas utile dans à part pour trouver approxtv(n)")
print("Choississez votre fonction :")
fonction = int(input("votre fonction ?(1.2.3.4.5.6.7.8)"))
n = int(input("choisissez n (n appartient à N >1"))
if fonction == 1:
print("Le vol de", n, "est de :", vol(n))
elif fonction == 2:
print("Le temps de vol de", n, "est de", temps_vol(n))
elif fonction == 3:
print("L'altitude de ", n, "est de", altitude(n))
elif fonction == 4:
print("Le graphe du vol de", log(n), "est")
elif fonction == 5:
print("L'entier plus petit que", n, "ayant le plus grand temps de vol est", valuemaxtempsdevol(n))
elif fonction == 6:
print("La liste triée des entiers de temps de vol", n, "est", classe_vol(n), "avec un nombre TV(n) égale à :", len(classe_vol(n)))
elif fonction == 7:
print("La liste des TV(i+1/Tv(i) avec TV(i)=card{k/temps_vol(k)=i}", suite_TV(n))
elif fonction == 8:
print("Le nombre d'entiers dont le temps de vol est égal à", n, "est approximativement égale à", approxtv(n))
Reprenons. Je vais essayer de formaliser tout ça.
Soit la suite définie par et si
est pair alors
sinon
.
On définit alors le temps de vol de , qui est le nombre d'itérations par la suite
pour que
.
On définit aussi valuemaxtempsdevol(n) qui calcule l'entier plus petit que ayant le plus grand temps de vol.
Ensuite, on écrit une fonction classe_vol(n) qui donne les entiers ayant un temps de vol égal à n.
Par exemple, on a classe_vol(19)=258 puisqu'il y a 258 entiers qui ont un temps de vol de 19 itérations.
Voici ces entiers : [9, 56, 58, 60, 61, 352, 360, 362, 368, 369, 372, 373, 401, 402, 403, 2176, 2208, 2216, 2218, 2240, 2256, 2260, 2261, 2274, 2275, 2400, 2408, 2410, 2416, 2417, 2420, 2421, 12288, 13312, 13568, 13632, 13648, 13652, 13653, 14464, 14496, 14504, 14506, 14528, 14544, 14548, 14549, 14562, 14563, 81920, 86016, 87040, 87296, 87360, 87376, 87380, 87381, 524288]
Ensuite, on définit une fonction qui donne une approximation du nombre d'entiers ayant un temps de vol égal à n.
On affirme que .
Pour trouver , on cherche le taux d'accroissement entre
qui devrait tendre vers
. On note alors
.
Avec ma fonction je trouve . Ensuite, j'utilise simplement l'égalité avec une valeur n tel que classe_vol(n) est connue. Ici 19. On écrit alors :
. En résolvant pour les plus hautes valeurs possible de classe_vol(n), ou trouve
.
On obtient alors ainsi avec
.
Maintenant que l'exercice est fini, je me pose 3 questions :
* comment peut-on montrer que
Je pense qu'il faut faire un calcul de limite, mais aucune idée de comment commencer ?
* peut-on exprimer sous la forme
,
* comment pouvons-nous affirmer que (à part en testant des valeurs).
Merci.
Un peu des 2, conjecture pour la forme approximative de TV(n) et résultat connu pour le calcul sur les modules :
Ecrire une fonction classe_vol(n) calculant la liste triée de tous les entiers dont le temps de vol est exactement n.
On pourra remarquer (justifier) que pour tout entier n ∈ N∗, alors:
• si n = 4 [6], alors les antécédents de n par la fonction v sont m=2n et m=n−13
•• sinon, le seul antécédent de n par la fonction v est m=2n .
Mais je me doute bien que ça doit exister, sachant que ce que je fais est plutôt trivial. Mais bon, impossible de trouver :/
salut
tu peux essayer ca sur excel vba :
Sub syracus()
u = 95
Do
If u Mod 2 <> 0 Then
v = 3 * u + 1
w = w & " " & v
u = v
Else
v = 0.5 * u
w = w & " " & v
u = v
End If
n = n + 1
Loop Until v = 1
MsgBox n 'temps de vol
MsgBox w 'retourne les elements de la suite.
t = Split(LTrim(w), " ") 'convertie w en tableau
For i = 0 To UBound(t) - 1
For j = i + 1 To UBound(t)
If Val(t(i)) > Val(t(j)) Then
a = t(i)
b = t(j)
t(j) = a
t(i) = b
End If
Next
Next
MsgBox t(UBound(t)) 'valeur maximale de la suite
End Sub
Annuler
connectez vous