leg,
il faut prendre S(1)=4,
et on applique la formule qui donne le (n+1)terme en fonction du nieme, c'est a dire S(n+1)=S(n)²-2 et ainsi jusqu'a ce que l'on atteigne ( pour l'indice ) la valeur p-1
ainsi pour 2^7-1
S(1)=4
s(2)=4²-2
s(3)=......
......
S(6)=0 modulo 127 ;6 est bien egal a 7-1 . voila
Pole cette suite est bien la suite de Perrin.
Bon, comme les choses deviennent claires, et en me basant sur les données de leg et les explications de pole, voici ce que leg semble attendre :
U0=3
U1=0
U2=2
U3=3
U4=2
---
U5=U4+U0=5
U6=U5+U1=5
U7=U6+U2=7
U8=U7+U3=10
U9=U8+U4=12
U10=U9+U5=17
U11=U10+U6=22
U12=U11+U7=29
U13=U12+U8=39
U14=U13+U9=51
U15=U14+U10=68
U16=U15+U11=90
U17=U16+U12=119
U18=U17+U13=158
U19=U18+U14=209
U20=U19+U15=277
U21=U20+U16=367
U22=U21+U17=486
U23=U22+U18=644
U24=U23+U19=853
U25=U24+U20=1130
U26=U25+U21=1497
U27=U26+U22=1983
U28=U27+U23=2627
U29=U28+U24=3480
U30=U29+U25=4610
U31=U30+U26=6107
U32=U31+U27=8090
U33=U32+U28=10717
U34=U33+U29=14197
U35=U34+U30=18807
U36=U35+U31=24914
U37=U36+U32=33004
U38=U37+U33=43721
U39=U38+U34=57918
U40=U39+U35=76725
U41=U40+U36=101639
U42=U41+U37=134643
U43=U42+U38=178364
U44=U43+U39=236282
U45=U44+U40=313007
U46=U45+U41=414646
U47=U46+U42=549289
U48=U47+U43=727653
U49=U48+U44=963935
U50=U49+U45=1276942
U51=U50+U46=1691588
U52=U51+U47=2240877
U53=U52+U48=2968530
U54=U53+U49=3932465
U55=U54+U50=5209407
U56=U55+U51=6900995
U57=U56+U52=9141872
U58=U57+U53=12110402
U59=U58+U54=16042867
U60=U59+U55=21252274
U61=U60+U56=28153269
U62=U61+U57=37295141
U63=U62+U58=49405543
U64=U63+U59=65448410
U65=U64+U60=86700684
U66=U65+U61=114853953
U67=U66+U62=152149094
U68=U67+U63=201554637
U69=U68+U64=267003047
U70=U69+U65=353703731
U71=U70+U66=468557684
U72=U71+U67=620706778
U73=U72+U68=822261415
U74=U73+U69=1089264462
U75=U74+U70=1442968193
U76=U75+U71=1911525877
Est ce cela ??
leg,
quand on effectue les calculs de la suite de lucas ,on les fait modulo le nombre premier,; par exemple pour 127
ainsi pour 14²-2=194=67 mod 127 et on reprends 67 que l'on eleve au carré =>
67²-2=42 mod 127 et on reprend 42 que l'on eleve au carré etc...
donc on n'atteint pas de nombres gigantesques par rapport a Mp (le maximum est (Mp-1)²)
je pense que la constante de votre suite est le plus petit nombre de Pisot-Vijayaraghavan , soit la valeur suivante : 1. 32471795724474602.....(voir le site de Plouffe ou elle figure)
il suffit donc d'elever cette constante a la puissance n pour obtenir une valeur approchée de Un.
ce qui suppose pour U(n) grand, de connaitre un tres grand nombre de decimales
oui sph, "mais a priori cette suite serait connu, mais elle ne semble pas avoir été étudié"
mais ce qu'il faut cest connaissant l'exposé P, je connais la valeur de U pour p mais comment aller directement a la valeur de U pour 2^p - 1 car il n'y aurait plus qu'a diviser U par 2^p -1.
pour tigli ta réponse #121 j'avais controlé 3 fois : s(1) = 4, S(2) = 14, S(3) = 194
S(4) = 194² -2 =37634 ; s(5) = 37634² - 2 = 1416317954 = 111(127);
S6 = 1416317954² - 2 = 2005956546822749114 / 127 =
15794933439549182
ce qui est étonnant c'est d'avoir trouver avec s(1) = 7 en quatre opérations et un nombre plus petit ..! "coup de bol"
mais je ne vois pas en quoi ce test est performant vu la taille du nombre pour Mn = 127? comme je l'ai dit plus haut car si pour 2^p -1 avec p = 23 j'ai 22 operations mais la taille s(22)² ... cela veut dire que pour P= 30 000 000 ce test est infaisable ou comme le dit pole on reduit en base 2, 10 ou autre, je n'en sais rien...
question: si cette suite de perrin est connu comment ou pourquoi on n'en parle pas ..? et l'a t'on étudiée pour ces nombres de Mersenne?
tigli je vien de croisé ta réponse ok, pour la méthode de calcul de lucas je me disait aussi que sa cloche..
tigli pourquoi n'a t'on pas caculer cette constante comme Pi par ex avec 20million de décimales ce qui n'est pas important aevc l'informatique
car alors c'est facile de trouver la valeur a 1 ou 2 pres, de 1.342....^p = 7 million de chiffres on devrait avoir le résultat + ou - 1 non ? car il suffit que le nombre de décimales soit juste et = au nombre a trouver ....!
Juste comme ca mais je trouve reellement paradoxal l'age de leg et de pole !!!
Car leg : j'ai beau etre tres tres concentré, quand je te lis, je ne comprend jamais ce que tu veux dire.
Et pour pole : a 12 ans, on ne connais pas ce que tu connais.
Donc, a moins d'etre dans un cauchemard, je me demande si ce n'est pas pole qui a 57 ans et leg 12...
Je dis juste ca comme ca hein !!!
Re : nombre de Mersenne
c'est normal sph moi je commence cela ne fait que 7 ans que je m'itérresse au math. j'ai arrété a 13 ans .....je galoppe pour rattraper.. mais tu connais le dicton... même si je cour vite..c'est le pardoxe du temps perdu iiiiii.
Voilà (cela fait il avancer quelque chose ?) :
U6/U5=1.000000
U7/U6=1.400000
U8/U7=1.428571
U9/U8=1.200000
U10/U9=1.416667
U11/U10=1.294118
U12/U11=1.318182
U13/U12=1.344828
U14/U13=1.307692
U15/U14=1.333333
U16/U15=1.323529
U17/U16=1.322222
U18/U17=1.327731
U19/U18=1.322785
U20/U19=1.325359
U21/U20=1.324910
U22/U21=1.324251
U23/U22=1.325103
U24/U23=1.324534
U25/U24=1.324736
U26/U25=1.324779
U27/U26=1.324649
U28/U27=1.324760
U29/U28=1.324705
U30/U29=1.324713
U31/U30=1.324729
U32/U31=1.324709
U33/U32=1.324722
U34/U33=1.324718
U35/U34=1.324716
U36/U35=1.324720
U37/U36=1.324717
U38/U37=1.324718
U39/U38=1.324718
U40/U39=1.324718
U41/U40=1.324718
U42/U41=1.324718
U43/U42=1.324718
U44/U43=1.324718
U45/U44=1.324718
U46/U45=1.324718
U47/U46=1.324718
U48/U47=1.324718
U49/U48=1.324718
U50/U49=1.324718
U51/U50=1.324718
U52/U51=1.324718
U53/U52=1.324718
U54/U53=1.324718
U55/U54=1.324718
U56/U55=1.324718
U57/U56=1.324718
U58/U57=1.324718
U59/U58=1.324718
U60/U59=1.324718
U61/U60=1.324718
U62/U61=1.324718
U63/U62=1.324718
U64/U63=1.324718
U65/U64=1.324718
U66/U65=1.324718
U67/U66=1.324718
U68/U67=1.324718
U69/U68=1.324718
U70/U69=1.324718
U71/U70=1.324718
U72/U71=1.324718
U73/U72=1.324718
U74/U73=1.324718
U75/U74=1.324718
U76/U75=1.324718
Si cela est utile, je suis pret a coder ca en ASM pour obtenir des résultats tres pointus et pour de tres grands nombres.
Désolé, fallait que je la relève celle-là !Envoyé par leg
C'est pas une perle du bac ?
PS : calculez l'unique solution réelle de l'équation x3 = x+1
Dernière modification par g_h ; 29/08/2005 à 23h41.
x3 =x+1Désolé, fallait que je la relève celle-là !
C'est pas une perle du bac ?
PS : calculez l'unique solution réelle de l'équation x3 = x+1
x*x*x=x+1
x*x*x-x=1
Hmmm, leg, c'est un travail pour ta constante exponentielle ca (du moment que ca augmente...
!!)
Avec la formule de Cardan : http://www.bibmath.net/dico/index.ph.../c/cardan.html
Ce qui vaut ce vers quoi votre suite tend.
(et maintenant ... ?)
Trop tard pour éditer, je voulais bien sur dire "ce vers quoi Un+1/Un tend quand n tend vers l'infini."
leg,
c'est bien la valeur (plus petit nombre de Pisot-Vijayaragahavan) que j'ai donné, qui est la racine reelle de l'equation caracteristique x³-x-1. Sur le site de Plouffe il y a la formule et la valeur de la constante .
arf leg,
je n'avais pas lu votre dernier post d'hiers soir.
1, la constante sur le site de plouffe est calculee a 50000 digits.
2,imaginez vous la grandeur des nombres que cela ferait manipuler ?
3, de plus cela necessiterait d'elever la constante a la puissance Mp ce qui necessite rapidement un nombre colossal d'operations ,alors que le test de lucas ne necessite qu'un nombre d'operations proportionnel a p , ce qui est beaucoup plus rapide pour les grands nombres. donc pas d'espoir de calculer plus vite avec cette suite.(dont la propriété qui plus est , n'est pas demontrée )
Même en calculant avec le nombre de ta formule^n, on arrivera à des nombres bien trop grands.
On demande LEG au bureau des pleurs... Ou est il ? Je suis IMPATIENT de voir quelle direction il va prendre !
Bon, quant à moi, je crois avoir trouvé quelque chose d'interessant mais nous en reparlerons en temps voulu...
Re : nombre de Mersenne
La suite Un de leg est définie par la relation de récurrence
Un+1-Un=Un-4
Son équation caractéristique est donc
X^5-X^4-1 = 0
Celle ci se factorise en
(X^2-X+1)(X^3-X-1)=0
Il y a donc 4 racines complexes conjuguées deux à deux et une racine réelle.
Les racines complexes sont -j et -j^2 où j est la racine cubique de l'unité, et deux autres nombres dont l'expression exacte est trop horrible pour que je l'écrive ici. Une valeur approchée est
-0.662359+0.56228i et -0.662359+0.56228i.
La racine réelle est le nombre de Pisot cité plus haut dont une valeur approchée est 1.324718
Appelons C1 à C4 les racines complexes ci dessus et R1 la racine réelle.
Les suites Un s'écrivent alors sous la forme :
aC1^n+bC2^n+cC3^n+dC4^n+eR1^n où a b c d e sont déterminées en fonction des valeurs initiales de la suite.
Comme le module des éléments complexes C1 à C4 est inférieur ou égal à 1, la suite Un est approximativement égale à R1^n pour n suffisamment grand.
Cela explique que le rapport Un+1/Un tende vers 1.324718
Voilà voilà
Si tu parle de i, c'est plutôt sqrt(-1)
Ericc,
la suite de leg (de Perrin) est definie par une relation de recurrence plus simple soit :
U(n)=U(n-2)+U(n-3) ; l'equation caracteristique est donc x³-x-1
d'ou constante de Pisot etc...
aucun nombre de la forme 2p -1 p impair n est divisible par 3 7 11 13 17 19
c est pour faire avance le shmiliblic
ceux divisible par 23 on p multiple de 11
Sachant queSi tu parle de i, c'est plutôt sqrt(-1), je pense que ce qu'il entend par racine cubique de l'unité, c'est plutôt
Cette "racine cubique de l'unité" sert beaucoup pour résoudre les équations du 3ème degré, notamment avec la méthode de Cardan (la seule que je connais)
(zut, j'ai oublié de virer les "i" du sinus et du cosinus... !)
Salut,
[MODE=HS]Mais attention, elle ne donne qu'une solution parmi les trois (complexes). Je le rappelle à tout hasard.Cette "racine cubique de l'unité" sert beaucoup pour résoudre les équations du 3ème degré, notamment avec la méthode de Cardan (la seule que je connais[/MODE]
Cordialement.
Oui c'est bien ce nombre là. Il y a 3 racines cubiques de l'unité :
1 c'est évident
j =-1/2+isqrt(3)/2
j^2=conjugué de j = -1/2-isqrt(3)/2.
J'avais vu la suite de degré 5 dans un post de leg, d'où ma remarque. Mais en fait je ne comprends goutte à ce qui se dit sur ce fil. Cela ressemble plus à de la pataphysique qu'à des maths pour moi. Mais ça a l'air fun...
[mode HS aussiSalut,
[MODE=HS]Mais attention, elle ne donne qu'une solution parmi les trois (complexes). Je le rappelle à tout hasard.
Cordialement.]
Si tu parles de la méthode de Cardan, tu te trompes, elle donne bien les 3 solutions complexes : une fois qu'on a trouvé une solution S au trinôme à résoudre, il faut ensuite calculer les 3 racines cubiques de S ( s^{1/3}, s^{1/3}*j, s^{1/3}*j² ) ce qui nous donne par la suite les 3 solutions complexes du polynôme du 3ème degré.
(peut-être que tu parlais de la "formule de Cardan" qui elle ne donne qu'une solution, mais ce n'est pas la même chose, la "méthode de Cardan" est une méthode générale de résolution)
PS : j'avoue ne pas comprendre grand chose à ce fil, mais c'est vrai que c'est... fun
cricri,
vous vous etes trompé pour 7
7 divise 2^9 -1
7 divise 2^3-1donc il divise 2^(3a)-1 avec a =1,2,3,4, etc...
c'est ce que vous avez constaté pour 23 qui divise 2^11-1
donc il divise les 2^11a-1 avec a = 1,2,3,4,....
bon courage
bonsoir tout le monde et surtout sph, qui doit bien se fractaliser
en tout les cas, je vois que ceux qui regardent en douce attende la bonne grosse bulle pour intervenir ce qui est trés bien ainsi !
tigli je m'etait rendu compte hier soir que d'élever cette constante a la puissance 2^p -1 serait inutile en effet; de plus les décimales sont variables ce qui la rend inutitle pour ce genre de teste.
ainsi que ce que m'a confirmé cricri en utilisant Mn comme exposant et en supposant qu'il soit premier, donc si il ne divise pas
2 ^(Mn - 1) - 1 c'est que Mn est composé.
mais lorsque j'ai demandé une explication sur le test de lucas
(tigli m'a tres bien expliqué son fonctionnement et merci)
mon erreur pour Mn = 127 il n'y a aucune remarque..??? ni de la part de Sph .
pourtant regardez ce que j'ai fait;
je test M127 , S(1) = 4 ..etc j'arrive a S(6) et ça ne marche pas
"j'ai tapé un mauvais chiffre en plus a deux reprises tant mieux"
j'ai donc remplacé la valeur de S(1) = 7 , S(2) = 7² - 2 = 47
S(3) = 47² -2 = 2207 = 48(127)
S(4) = 48² - 2 =2302 = 16(127)
S(5) = 16² - 2 = 254 = 0(127) ???
ets ce le test de lucas qui déraille ou il y a une bonne explication
car si je prend S(1) = 4
S(2) =4² -2 = 14 " = 0(7) ce qui est normal"
S(3) = 14² - 2 = 194 = 67 (127)
S(4) = 67² - 2 = 4487 = o (7) et = 42 (127) et Où 42 est divisible par 3 !
S(5) = 42² - 2 = 1762 = 111(127)
S(6) = 111² - 2 =0(127)
la seule explication que j'ai trouvé l'exposant 3 me donne Mn = 7,puis 2^Mn - 1 me donne 127 , alors ce qui me ferait raccourcir le test de lucas si 7 divise un reste modulo 127 . quetion: peut ont faire de même pour les autres Mn ou est ce une propriété de ce test
ou c'est l'exeption qui confirme la régle ..
je n'ai pas fait l'essai avec 31
2^ 5 -1 = 31, 2 ^ (2^5 - 1) = Mn premier
est ce que 31 divise un reste modulo Mn ou si S(1)=31
shp a ton programme ... A +
j'espère que les bons vont trouver une bonne réponse merci d'avance.
n=2^b-1 a=nombre dont on veut savoir si la suite commençant par s(1)=a a un 0.
x^2=a+2 mod n. a forme un suite ayant un 0=x forme un suite ayant un 0 et ((a+2)/n)(symbole de Legendre)=1.
Il ne reste plus qu'à utiliser récursivement.
Exemples :
n=127 a=7 (a+2)/n=1
x=3 car 3^2=a+2
a=3 Or 3 marche donc 7 marche aussi
Voilà.
merci pole .
pour être plus précis est ce le fait de remplacer S(1) = 4 par 7 qui marche ou, le fait de diviser par 7 S(3), s(4) ...s(n) le modulo de Mn en exemple:
il me faut d'abord le modulo de Mn
Mn = 127,
S(3) = 194² - 2=67(127)
et c'est a partir de là, seulement! que je remplace Mn 127 par Mn 7, d'où
S(4) = 67² - 2 = 0 (7) ; donc 2^7 - 1 = premier!
A) cette propriété est elle utilisé dans les test de lucas
b) pour 2^5 -1; 2^(2^5 - 1) - 1 = premier =2147483647
le nombre de test = 31 -1= 30 au maxi si j'utilise Mn =214..47 comme modulo
si j'utilise 31comme modulo j'attend le premier x modulo 214...47 et je recontinue modulo 31....
c) comme pour Mn 127 je remplace S(1) par 31 et je test modulo Mn 214...47 ou 31?
je n'ai pas de programme qui me permet de faire rapidement ces essais
afin de comparrer le nombre d'operations pour tester 2^31 - 1
aurais tu la gentillesse de le faire dans la mesure du possible ou quelqu'un d'autre
avant de continuer plus loin sur cette idée merci..
sph pourrais tu ensuite si ça marche, faire un petit prog dans ce sens ??
