SalutEnvoyé par robert et ses amis
salut,
tu veux n tqet
Si c'est ça, le mieux serait de passer au log :
en clair n est la partie entière de
une fois que tu as ce n, tu trouves facilement ce que tu cherches, c'est
excuse ma question niaise, mais: Pourquoi, quelle utilité a le logarithme pour ca?
merci! (meme si c'est des maths basiques, je prend!)
manu
bon déjà, on voit qu'il suffit de prendre la partie entière de
La solution itérative que tu proposes risque de devenir très longue pour des grands nombres, l'intérêt véritable est ici : en prenant le logarithme, le temps de calcul reste raisonable même pour des grands nombres.
Voui, il m'a bien semblé que utiliser ca est un raccourci, mais ma question etait plutot: qu'est-ce que fait le logarithme comme operation sur les grands nombres?
Il utilise des divisions.
n=ln en base a de b
ex a=multiplicateur=3, b=nb que tu as donné=17
17/3=5.xxx log:=1
5/3=1.xxx log:=2
Comme tu veux le < n tel que a^n>=b, on ajoute 1 (log:=3).
Et on calcule 3^3 mod 17.
3=101 en base 2
Pour le calcul, on utilise 3 colonnes :
3 3 1
Pour passer à la suivante, on met au carré mod 17 la 1er, on divise par 2 la 2ème (on prend le quotient), et si le nb dans (l'ancienne) 2ème colonne est impair, on multiplie le nb de la 3ème par le nb de la 1er mod 17.
On s'arrête quand il y a 0 dans la 2ème colonne.
3 3 1
9 1 3
x 0 10
Le résultat est dans la 3ème colonne.
Complexité : log en base a de b divisions pour la 1ère opération, 2*log(log en base a de b)+1 multiplication et les divisions au maximum.
Mais je ne vois pas à quoi ça sert pour prouver la primalité des Mn.
(Tu peux dire l'algo?)
bonjour ,pole tu as raison car sph cherche a travailler sur la différence entre par ex: 3^n et 3^(n-1) regarde déjà ce que cela donne pour 2^13 -1 =8191
lnb/lna; soit 3^8 et 3^9, difference > 8191 (environ 11726,)
"je ne vois pas du tout l'interêt"
le problème c'est : je pense qu'il est difficile de savoir si : 2^p-1 à plusieur ADN cela revien pratiquement a se poser la même question, y'a t'il des diviseurs.
Mais quelle est le rapport entre les diviseurs et les log?
bonjour pole il n'y a aucun rapport,
je pense que sph, est dans une impasse, ou alors il a une autre idée afin de savoir ou connaître si 2^p -1 a un ou + , ADN = P . car tout réside dans cette propriété 2^p-1 n'a qu'un ADN = p, alors 2^p-1 est premier! ce qui est simple en apparence. mais avec de grands nombres cela nécéssite un base de donnée importante avec les ADN correspondant a P .
mais ce qu'il faudrait analyser c'est l'adn d'un nombre :
supposons que n soit premier P, son adn est (p-1)/2 par ex 8191
adn = 4095.4096.4095 or 4095 est divisible par 5 soit l'adn de 11 = 5.6.5
4095/5= 819 qui est divisible par 3 = 273 peut on dire que si 8191 n'est premier alors il est divisible par 11, au minimum ?
autre exemple
2047 = 1023.1024.1023
1023 est divisible par 11 soit l'adn de 23 = 11.12.11 et effectivement 2047 est divisible par 23 = 89 soit l'adn de 89 = 44.45.44 et 1023 =11(44) c'est peur être de ce côté qu'il faut chercher...car en définitive si on regarde (2^23-1) = adn = 4194303.4194304.4194303 qui est divisible par 23soit l'ADN de L'exposant mais qui donne: 23.24.23 soit 47 qui est un nombre premier! et qui divise 2^23 -1.
Comment tu associes un adn à 3 nb?
Ce qui dserait bien, c'est que SPH nous donne ses idées.
Oui, mais il a pas l'air decidé a... c'est peut-etre le mot "donné" qui fait peur??
pole , dés l'instant ou un nombre P divise 2^p-1 c'est qu'il a obligatoirement l'ADN de l'exposant par ex: 2^11-1= 2047
si 23 divise 2047 c'est tout simplement que 23 = ADN de 11 soit adn mais comme c'est un cribleur de MERSENNE son ADN = OOOOOXOOOO et non 00000x00000 = adn de 11, [ça je sais que tu là compris mais regarde ce qui se passe et que l'on a pas fait attention sur l'autre fil nommbre de Mersenne ]
j'avais fait la remarque en relation avec le petit théorème de fermat que:
l'exposant p divise toujours ((2^p-1) -1) / 2, or ce que j'ai pris pour une banalité c'est en fait plus fin car les diviseurs de ce nombre , 11, ce sont les ADN qui divisent 1023 c'est a dire l'adn de 2047 =(1023.1024.1023) et l'adn de 23 qui divise 2047 n'est autre que 11.12.11 et l'adn de 89 qui divise 2047 = 44.45.44, les diviseurs de 2^(p-1) -1 sont 3,11 et 31 ce qui te donne 11+1=12 , (11+31+3)= 45 ,et analyse les exmple du post#128 je pense que tout cela ce tient.
car pour diviser 2^13-1 , le seul candidat possible aurait été 7 puisque ADN de 13 = OOOOOOXOOOOOO où X=7 or 7 ne divise pas 4095 ! en connaissant les diviseurs de
[((2^p-1) -1) / 2]on arrive pratiquement a connaître l'ADN d'un diviseur de 2^p-1
pour 2^29 - 1 premier diviseur 233 ,ADN = 14.15.14 et son adn = 116.117.116
diviseurs [2^(p-1).. ]3,5,29,43,113,127, (3+113)=116 = adn du diviseur de Mersenne
M29 ...voilà quelque piste a analiyser..
rectification pour 7 qui divise bien 4095, mais l'ADN aurait donné 7.8.7, soit 15 qui ne peut diviser 8191..pas plus que 13 ou 39 aucun ADN ne donne un premier.
Ce que je ne comprend pas , c'est 2047 =(1023.1024.1023).
On le connaît parfaitement : que des 0 sauf au numéro (p-1)/2 où c'est X.
J'ai l'impression que Leg omet (ou peut-etre confonds) l'ADN et l'ADN de mersenne, qui sont 2 choses bien diffrentes...
pas du tout je ne confond pas les deux.
adn= 1,3,5.....x =000....x soit 222x222
ADN = 2^1-1 . 2^3 -1.....X soit 1, 7 , 31....= O X O où 7 = adn de 3, même nombre de symboles,d'où dans ce cas précis, on est modulo 2, est X + 2 = 2^9 -1 alors l'expoasant 3 divisera tous les exposant multiple de cet ADN est 7 divisera les résultats c'est a dire 3 divise 9 et 7 divise 511. , et bien sûr pour 2^5-1 ADN de 31=
O O X O O nous donnera modulo (2*5) ,31divisera (2^15 -1) d'accord! mais l' adn du nomdre P = 31 est bien: 15.16.15. où 15 correspond bien à :30/2 soit
2^(p-1) - 1 = 16-1 =15 symboles ....or 3 divise bien ce dernier nombre, mais il ne faut pas voir 3 en tant que nombre mais en tan qu'adn 3.4.3 soit l'adn de 7, et 7 ne divise pas 2^5-1 le seule qui aurait été probable comme facteur P, de là on remarque que L' ADN par exemple de 31 = 5 = O O X O O nous donne aussi un potentiel adn pouvant diviser le nombre de Mersenne = 31 il s'agit donc de 5.6.5 soit 11 car si 5 divise la première partie de l'adn c'est a dire 15 cela "revien" a faire le constat suivant :
15.16.15. est 'il divisible par 5.6.5 (les deux adn)
pole: 1023.1024.1023 c'est facile a voir 1023 symboles
11=adn = 5.6.5= 00000x00000= 222221122222=135791197531etc etc, donc pour résumé 5.6.5 ok
voila pourquoi je vous ai mis ces exmples sur les post ci dessus afin d'analyser mathématiquement ces différentes propriétés.
pour 2^11 - 1= 2047, ADN de 2047= 5.6.5, adn du nombre 2047 = 1023.1024.1023.
2^(p-1)-1 = 1023, l'ADN de l'exposant 11 divise l'adn de 2047 mais cet ADN peut aussi ce voir comme adn de 23 =11.12.11 alors, est ce que 23 divise 2^11-1? oui !voilà pourquoi les premiers candidats pouvants diviser un mersenne se trouve bien de ce côté.
Ha, sorry, j'avais pas vu que le file avait progressé.
Tout d'abord, j'ai fait une petite pause car je devais etudier completement autre chose. Mais me revoila.
Je dois étudier quelque chose pour exposer ce que je pense. Par exemple, y a t'il une utilité a garder les ADN de mersenne donnant des non premiers ?
exemple :
7 [3] (X=2)
23 [11] (X=6)
71 [35] (X=18)
89 [11] (X=6)
127 [7] (X=4)
161 [33] (X=17)
217 [15] (X=8)
223 [37] (X=19)
337 [21] (X=11)
Ca reduirait encore bien la liste des nombres utiles pour cribler...
Egalement, voici une liste de cribleur avec a la fin de chaque ligne un mersenne premier et entre crochet le symbole du cribleur sur lequel ce mersenne tombe.
Exemple :
31 est un mersenne premier.
Qui pouvait l'eliminer ?
Reponse : tout cribleur inferieur a lui, donc 7 et 23 (en fait, tout cribleur inferieur ou egale a sa racine mais j'ai voulu voir coment reagissait globalement tous les cribleurs inferieurs)
J'ai donc codé ca sous cette forme :
CRIBLEUR[ADN] (X=xieme symbole) MERSENNE{Symbole touché}
Le cribleur 7 laisse passer le mersenne 31 puisque le 7 crible au symbole 2 ("X=2") alors que le symbole conserné pour le mersenne 31 est le symbole 1 ("31{1}") :
7 [3] (X=2) 13{1}
---
7 [3] (X=2) 17{0}
---
7 [3] (X=2) 19{1}
---
7 [3] (X=2) 31{1}
23 [11] (X=6) 31{5}
---
7 [3] (X=2) 61{1}
23 [11] (X=6) 61{9}
---
7 [3] (X=2) 89{0}
23 [11] (X=6) 89{1}
71 [35] (X=18) 89{10}
---
7 [3] (X=2) 107{0}
23 [11] (X=6) 107{10}
71 [35] (X=18) 107{19}
89 [11] (X=6) 107{10}
---
7 [3] (X=2) 127{1}
23 [11] (X=6) 127{9}
71 [35] (X=18) 127{29}
89 [11] (X=6) 127{9}
---
7 [3] (X=2) 521{0}
23 [11] (X=6) 521{8}
71 [35] (X=18) 521{16}
89 [11] (X=6) 521{8}
127 [7] (X=4) 521{2}
161 [33] (X=17) 521{30}
217 [15] (X=8) 521{6}
223 [37] (X=19) 521{2}
337 [21] (X=11) 521{9}
343 [147] (X=74) 521{114}
511 [9] (X=5) 521{0}
---
7 [3] (X=2) 607{1}
23 [11] (X=6) 607{7}
71 [35] (X=18) 607{24}
89 [11] (X=6) 607{7}
127 [7] (X=4) 607{3}
161 [33] (X=17) 607{7}
217 [15] (X=8) 607{4}
223 [37] (X=19) 607{8}
337 [21] (X=11) 607{10}
343 [147] (X=74) 607{10}
511 [9] (X=5) 607{7}
Ha oui voila, je sais où j'en etait avant de faire une pause. Et justement, vous remarquerez quelque chose de faux dans le post precedent. Quand le teste un mersenne (31 par exemple). Je dis qu'il faut tester jusqu'a sa racine. Et l'erreur que je commais est que M(31) a sa racine non pas a 23 mais a un nombre de 3 chiffres.
Voila pourquoi j'avais programmé quelque chose qui ne peux plus preter a confusion. Ce type de liste :
7 [3] (X=2) _2^31-1_{1}
23 [11] (X=6) _2^31-1_{5}
31 [5] (X=3) _2^31-1_{1}
47 [23] (X=12) _2^31-1_{16}
71 [35] (X=18) _2^31-1_{16}
73 [9] (X=5) _2^31-1_{7}
79 [39] (X=20) _2^31-1_{16}
89 [11] (X=6) _2^31-1_{5}
103 [51] (X=26) _2^31-1_{16}
127 [7] (X=4) _2^31-1_{2}
151 [15] (X=8) _2^31-1_{1}
167 [83] (X=42) _2^31-1_{16}
191 [95] (X=48) _2^31-1_{16}
199 [99] (X=50) _2^31-1_{16}
223 [37] (X=19) _2^31-1_{16}
233 [29] (X=15) _2^31-1_{16}
239 [119] (X=60) _2^31-1_{16}
263 [131] (X=66) _2^31-1_{16}
271 [135] (X=68) _2^31-1_{16}
311 [155] (X=78) _2^31-1_{16}
337 [21] (X=11) _2^31-1_{16}
359 [179] (X=90) _2^31-1_{16}
367 [183] (X=92) _2^31-1_{16}
383 [191] (X=96) _2^31-1_{16}
431 [43] (X=22) _2^31-1_{16}
439 [73] (X=37) _2^31-1_{16}
463 [231] (X=116) _2^31-1_{16}
479 [239] (X=120) _2^31-1_{16}
487 [243] (X=122) _2^31-1_{16}
...etc...etc...etc....
Ca parait bizzare tous ces {16} mais c'est logique. L'ADN est deja un tel concentré de nombre (puisqu'il represente des puissances !) qu'on arrive vite à en etre au debut d'ADNs sans meme avoir bouclé.
Vous voulez une bonne nouvelle ? ok : J'ai verifié, les ADN ayant un nombre de symboles non premiers sont INUTILES (ex: 71[35] qui ne sert a rien puisque 31[5] est là) !! Resultat, on peux reduire grandement la liste des cribleurs. Egalement, tous les doublons peuvent etre viré. On gardera par exemple 23[11] mais ce n'est pas la peine de garder aussi 89|11].
Derniere chose : vous avez remarqué que le symbole criblé est parfois pair, parfois impair ? Peut etre y a t'il quelque chose a fouiller de ce coté...
Allez, pour la route, voici les meme cribleurs pour un mersenne élevé (on va dire "M(19937)") :
7 [3] (X=2) _2^19937-1_{0}
23 [11] (X=6) _2^19937-1_{3}
31 [5] (X=3) _2^19937-1_{4}
47 [23] (X=12) _2^19937-1_{10}
71 [35] (X=18) _2^19937-1_{29}
73 [9] (X=5) _2^19937-1_{6}
79 [39] (X=20) _2^19937-1_{24}
89 [11] (X=6) _2^19937-1_{3}
103 [51] (X=26) _2^19937-1_{24}
127 [7] (X=4) _2^19937-1_{1}
151 [15] (X=8) _2^19937-1_{9}
167 [83] (X=42) _2^19937-1_{9}
191 [95] (X=48) _2^19937-1_{89}
199 [99] (X=50) _2^19937-1_{69}
223 [37] (X=19) _2^19937-1_{16}
233 [29] (X=15) _2^19937-1_{22}
239 [119] (X=60) _2^19937-1_{92}
263 [131] (X=66) _2^19937-1_{13}
271 [135] (X=68) _2^19937-1_{114}
311 [155] (X=78) _2^19937-1_{49}
337 [21] (X=11) _2^19937-1_{15}
359 [179] (X=90) _2^19937-1_{124}
367 [183] (X=92) _2^19937-1_{87}
383 [191] (X=96) _2^19937-1_{37}
431 [43] (X=22) _2^19937-1_{36}
439 [73] (X=37) _2^19937-1_{41}
463 [231] (X=116) _2^19937-1_{36}
479 [239] (X=120) _2^19937-1_{170}
487 [243] (X=122) _2^19937-1_{6}
ps: je rapelle que {0} veux dire "DERNIER SYMBOLE"
Dernière modification par SPH ; 06/10/2005 à 15h18.
sph , tu fais une érreur pour 89 , car il peut cribler tout comme 23 un autre mersenne .
mais moi je supprime les deux pas pour la même raison.
suppose que 23 = ADN 5.6.5 (adn 11) si tu le garde tu suppose donc qu'il existe un autre Mersenne avec l'ADN = 5.6.5, ce qui est idiot, comment 23 pourrait avoir un autre ADN? ou alors tu admets que cette propriété d' ADN ne veut rient dire, et qu'un nombre premier P, par exemple 23 pourrait cribler plusieur fois ?
il ne faut pas oublier que chaque mersenne composé élimine les multiple de l'ADN de mersenne donc aussi ses diviseurs si tu préfères les facteur premiers qui sont intervenus puisque les ADN mersenne sont des puissances lorsque tu élimines par ex
l'exposant 11 tu élimines tous ses multiples 2^11-1, et les modulos 22, c'est a dire 2^33,2^55 etc..etc
de plus la taille d'un ADN est limité a la moitié du nombre pour 23 je ne peux pas dépasser 11.12.11, soit 11 symboles avant X !
moi je conclu que l'on peut supprimer tous les ADN qui ont déjà servi ! ou alors que l'on montre un contre exemple!
par contre une propriété qui apparait, 89 ADN = adn . 11 il se peut que
p = ADN = 89.90.89 c'est a dire 179 divise un mersenne comme l'a fait 23,
23 ADN = adn.11 ; et :23.24.23 = ADN de 47 divise un mersenne ect ect
dans l'exemple cité, pour 89 a la condition bien sûr, que 179 est un ADN de mersenne = OOO..X..OOO inferieur à 89.90.89qui est son adn donc c'est vite limité.
Leg, je te met au defis de trouver un quelconque nombre pouvant etre criblé par 89[11] mais pas par 23[11]...
Si 23[11] crible un nombre, c'est que TOUT ADN[11] le crible aussi puisque c'est le meme ADN !
Donc, quitte a avoir un echantillon, autant prendre le premier mais jamais les autres.
Entre parenthese, je precise que le % gagné en ne prenant pas les copies est ridicule : 4% quand j'ai testé M(19937) sur la fourchette de NP allant de 3 a 379999.
Par contre, ne pas prendre les ADN non premier m'a fait gagner...60.19% ! rien que ca !!!
sph; tu ne m'a pas compris 89[11] ne crible que 2^11-1 et rien d'autre c'est évident! relis ce que j'ai mis plus haut ,et je te dis que si 23[11] crible un autre mersenne que 2^11-1, je mange une tonne de bananes car cette propriété des nombre de mersenne que sont les ADN ne voudrait rien dire!!!
et je pensais vraiment que tu n'utilisais pas les ADN non premier car pour moi cela me parraissait aussi évident ; c'est bien pour cela que je dis que tu peux suprimer tous les ADN qui ont déjà servi a cribler un mersenne. ne vien pas me dire que tu pense serieusement que 23[11] peut cribler un autre mersenne > 2^11-1 ou encore mieux qu'il existe 23[ADN] different de OOOOOXOOOOO un cribleur de mersenne ne peut avoir qu'un ADN!!!
23[11] crible les puissances 11; 33; 55; 77; 99;....
YA PU QU'A !
le premier test a faire c'est déjà avec l'exposant par exemple (23*2) +1 = 47; 47 a t'il un ADN qui ne peut être que 11.12.11. ce qui est inutile de chercher; car la division du résultat par 47 est plus rapide!
Leg voulait dire pour les exposants premiers. S'il y en a un, je mange une autre tonne de banane.
Pour les ADN non premier, ça ne sert à rien : il faut quand même les tester.
L'ADn ne sert qu'à trouver les cribleurs. Sinon, diviser est plus rapide.
c'est exact pole, mais j'ai l'impréssion que SPH n'a pas pris compte des propriétés de l' ADN, car sinon je ne vois pas pourquoi il me sort des exemples qui non rien a voir avec des mersennes exposant P , il n'a pas l'air d'avoir compris que l'ADN permet ensuite de savoir, que l'exposant par exemple 11 va diviser tous les exposants + modulo 22 exposant 33,55,etc etc ..et évidement 23[11] divise les résultats de
2^(11+22)-1 ce qu'on lui a déjà expliqué.
ce qui nous intérresse ce sont justement:
a) les nouveau cribleurs de Mersennes,
b) quel est le moyen rapide de savoir qu'il existe et dans quelle limite maxi, peut se trouver un cribleur de mersenne en connaissant l'exposant P qui transmet par conséquent son ADN a un cribleur probable si on sait qu'il n'y en a pas alors ce nombre Mersenne est premier!
Haaa, voila ce que j'aime entendre. Ce sont en effet des questions essentielles. Actu, je manque d'energie pour m'y pencher mais il y a des domaines vierges a exploiter.
ps : leg, tu saurais programmer, tu pourrais avancer bien plus vite...
c'est vrai sph , mais cela ne m'interresse vraiment pas . moi c'est l'analyse des entiers naturels, leur comportement dans une suite , dans les différences.. ect ect.
ce qu'il faut arriver a définir c'est la limite maximun dans laquelle se trouve le nombre P qui a comme ADN, celui de l'exposant
par ex si tu prends 2^41-1
on sait que si il y a un NP qui le divise ,alors il a comme ADN 20.21.20 soit 21 operation par nombre P > 83, mais 41 divise la partie avant X de l'adn de ce nombre P
par exemple p = 13367, adn = 6683.6684.6683 et 41 divise 6683 par obligation.ce qui nous donne 163 , or sur ces 163 partie d'adn plus de la moitié ne sont pas des NP.
par ex :41*3=123 ce qui donne 123.124.123. = 247, puis 41*4 =..(164+165)= 329
donc on progresse du modulo 82 entre chaque entier,
et on sait que 2^(41+82)-1 est divisible par Np mais aussi par (2^41-1) !
question est-il plus facile de trouver Np divisant ce nombre composé [2^(41+82)-1]
ou du moins, ce nombre a t'il plusieurs facteur P ? la clef des Mersenne se trouve là!!!
2^(41+82)-1 est divisible par 7 : 2^(41+82)-1=2^(41*3)-1.
Là où les ADN peuvent être intéressant, c'est pour GIMPS. On peut prendre un P, calculer la longueur de son ADN, et regarder s'il rentre dans la liste des exposants potentiels.
Mais je ne vois pas le rapport entre les log et les ADN. Ni comment tu peux aller presqu'aussi vite que prime95.
la propriété la plus interressante que j'ai trouvé c'est ceci:
on suppose que Mn est composé, par exemple 2^11-1 = N
N divise un autre "mersenne" qui est obligatoirement composé en l'occurence 2^33-1
il existe aussi P = ADN de 11 soit un ADN = 5.6.5, qui divise ce même nombre 2^33-1
ce qui nous donne : (2^33-1) /N = Y et (Y - N) = ((2^p -1 )/2) ; où P divise 2^11 -1.
2^11-1 = 2047 = N
2^33-1 = 8589934591
((8589934591/N) = Y = 4196353 et Y - N = 4195306
P = 23
2^23 -1 =8388607; 8388607/2 = 4195303.5
autrement dit: (((y - N) -2) * 2)= R et R - 1 = 2^p -1 = Mn
si p ne divise pas 2^11 - 1; il aurait été un nombre Premier
ce qui donne environ 8 opérations plus bien sûr R a diviser par 2,
( P fois)
à controler!
