suite:
et dont le premier facteur P, divisant Mq -1 est la différence entre A et B
ce qui donne le Triplet pythagoricien:2047, 3696, et 4225 = Z
A = 56, B = 33
la seule relation que j'ai trouvé avec (8sx)² -(3qy)² = 2047 = X; pour cet exempleZ+1) / 2) - 2B = 2047. question connaissant X < Z , peut on truver ce dernier c'est a dire Z ????
car là, alors il sera aisé de dire que Mq-1 est composé!
bonsoir,
un nombre de mersenne ne peut être premier que si il n'existe pas un réel X >1 et un nombre Premier P; tel que X < racine carrée de (U/4) < P ! ou
P < racine carrée de (U/4) < X
avec U tel que U² - 4 = 2*2^q -1
Alors il existe A² - B² = 2^q -1 composé, avec A > U
autrement dit si il existe X * P = U/4 , alors il existe A et B
exmple pour 2^29 -1
(3qy) est divisible par 3 et 29 ,Y = 3085465 ; Y est divisible par les facteurs de:
2^28 -1 qui sont : 5.43.113.127
U = 32768 et U/4 =8192
P = 233
racine carée de 8192 = 90,50
A / U = X = 35,16
les nombres de Mersenne sont reliés par U
ex pour Mq , q = 19 , U = 1024 et racine carrée de U/4 = 22.6, il n'existe pas X et P donc A non plus Mq est premier
U*4 = Mq ,pour q = 23, U = 4096 racine carrée de U/4 = 32, X =21,78
U*8 = 32768 = Mq, pour q = 29
U*2 = 65536 = Mq pour q = 31 racine carrée de U/4 = 128 , il n'exiqste p
suite: il n'existe pas A/U = X car il n'existe pas X*P = U/4, 2^31 - 1 = prime
U * 8 = 524288, donne Mq pour q = 37 , P = 223
((U² - 2²) / 2) + 1 = 2^37 -1.
racine carrée de U/4 = 362,03
A/U = X = 587,76
note:
il existe aussi deux autres entier a et b obtenu avec u' et v' tel que (U + 2) / 2 = U' et u' - 2 = v'
u' et v' sont divisibles par les facteurs de (3qy) on constitue les deux entiers a et b, tel que a² - b² = (q y)
exemple
Mq, pour q = 23 ;
2^22 -1 = (3*23*89*683)
u'/3 = 683
v' = 23*89
b = 682
a = 1365 = (v'+ 683)/2
ce qui donnera:
A/a = (A/u)*3
donc A/(u/4) = (A/a) +(A/u) .
connaissant toutes ces informations, il est peut être possible en partant de la racine carrée de U/4, ("qui est réduite par rapport à la racine carrée de 2^q - 1") de trouver plus facilement le couple X et P , ou de savoir qu'un tel couple existe alors on sait que 2^q - 1 est composé, et si il est possible de savoir qu'un tel couple n'existe pas alors 2^q - 1 est premier!
ceci nous montre probablement, la raison du peu de Mersenne premier
car il y a beaucoup de possibilités de trouver X et P par rapport à cette racine carrée!
moi pour l'instant je ne peu aller plus loin, car limité .. afin que par d'autre méthode, on puisse se rapprocher suffisament du couple X et P
A +
post 242
lire: un nombre de Mersenne peut être premier (et non pas: ne peut être..)
....Je pense que M(M(127)) est premier.....
Moi aussi.
Mais as-tu des preuves?
Je crois qu'il faudra attendre très longtemps pour être sûr que M(M(127)) est premier.
Et bien, je viens d'etablir que la lignée des mersenne resultant du NP 2 donne infiniment des mersennes premiers. Sinon oui, cette nuit, j'ai eu cette preuve assez difficile a expliquer (mais possible a expliquer quand meme !).
M(2)=a
M(a)=b
M(b)=c
M(c)=d
M(d)=e
etc, etc, etc, a l'infini !
C'est la seule branche de mersenne infinie !!
Maintenant, je dois en rédiger clairement la preuve mais cette "conjecture" me parait établie...
bonjour sph
tu risque de tomber dans le cas des nombres de Fermat; je veux dire par là que ce n'est pas parceque 2^3 -1,2^7 -1,2^127-1 sont prime; que la suite l'est! il y a même 99,99% de chance que cela soit le contraire tantôt premier, tantôt composé; c'est oscillatoire .
les nombres premiers ne suivent pas un cycle déterminé lorsque n tend vers l'infini.
mais ils bouchent les vides, qui ne sont pas occupés par leurs produits composés! c'est pour cela que la courbe des n premiers est oscillatoire par rapport a zéro lorsque n tend vers l'infini!
tous ces nombres suivent la même courbe oscillatoire, Mersenne, Fermat, Catalan, premier jumeaux etc etc .
Ho non, ne t'inquiete pas, mes preuves sont solides. Il me faut rédiger un document clair mais pour moi, les choses semblent etablies.Envoyé par leg
alors cela serait une trés belle chose, que de l'établir. j'espère que tu as raison au moins pour ta volonté d'essayer.
A+
Juste une question car apres tant de jours de reflexion, je me met le doute :
Pour tester si X est un mersenne premier, on crible bien tous les NP jusqu'a racine de X ?
Pour 127, on crible jusqu'a ou ?
Je sais, c'est une question basique mais j'espere une reponse.
Ha ca y est, j'ai retrouvé mes esprits. ok ok
Tu n'as pas regarder la suite de Lucas?
Pour un gros ordi, il faudrait plus que l'âge de l'univers pour prouver la primalité d'un P de 50 chiffres.
Tu crois raisonnable de trouver la primalité des nb de >1 000 000 de chiffres avec la méthode des divisions?
Oh la, non,Pour tester si X est un mersenne premier, on crible bien tous les NP jusqu'a racine de X ?
Cette methode est totalement impratiquable pour des grands nombres (comme le dit Pole). Pour les nombres de Mersennes on utilise le test de lucas lehmer.
oui, ne vous inquietez pas...
J'ai commencé a rédiger un article complet qui explique de A a Z ce que je considere comme une certitude.
L'article sera pret dans quelques jours.
L'impatience me gagne
Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.
"LA CONJECTURE MAGNIFIQUE DE SPH" (Partie 1/2)
Cette article parlera des nombres premiers et des nombres premiers de Mersenne
Deux etant le seul chiffre pair, nous travailleront exclusivement avec les nombres impairs.
Qu'un nombre soit premier ou non, il éliminera toujours tous ses multiples.
Par exemple, "3" élimine 6; 9; 12; 15; 18; etc...
Etant donné que je vous avais promis que nous n'utiliserions que les nombres impairs, je reprend mon exemple :
"3" élimine 9 (3*3); 15 (3*5), 21 (3*7); etc...
Si on devais schématiser ce que le nombre "3" élimine, nous pourrions 'dessiner' ceci :
3 élimine : OXOOXOOXOOXOOXOOXOOXOOX......
Cette chaine représente pour chaque nombre impair (en partant de 1) un symbole : un 'O' pour dire qu'il entoure le nombre (il ne l'élimine pas) et une croix 'X' pour dire que notre nombre est éliminé (criblé).
Mieux, on sait qu'a intervale très régulier, notre "3" crible un nombre (ici, tous les nombres égaux à 3x avec x impair)
On pourrait donc par convention définir une mini chaine qui se répèterait a l'infini.
Cette technique que j'ai utilisé depuis le début, je l'ai appelé ADN.
Voici l'ADN de 3:
3[OXO]
Sous entendu, 3 crible le 3 (le 'X' de cette chaine : 'OXO'), puis le 9 (le 2eme 'X' de cette chaine 'OXOOXO'; donc, le 'X' de l'ADN de 3 en repartant au debut de chaine apres le dernier 'O').
Bref, pour tout nombre, on a autant de symbole avec un seul et unique 'X' qui se trouve toujours en plein milieu.
Au hazard, je suis certain de cet ADN : 11[OOOOOXOOOOO]
C'est valable pour les nombres premiers ou non. Mais comme vous le savez, si un nombre n'est pas premier, c'est inutile de voir ce qu'il crible car un précédent nombre premier aura fait le travaille. Exemple avec 3 et 9 :
3[OXO]
9[OOOOXOOOO]
Si on recopie l'ADN de 3 a la meme longueur que l'ADN de 9, on a :
3[OXOOXOOXO]
9[OOOOXOOOO]
On vois donc que le nombre '9' ne crible rien de nouveau par rapport au crible de '3'
Nous sommes donc pret à cribler des nombres; meme lointains. On va donc voir quel impact aura nos cribles sur des nombres de mersennes.
Un nombre de mersenne, c'est quoi ? C'est un nombre qui a ce format : (2^n)-1
D'une part, il faut que 'n' soit un nombre premier. D'autre part, il faut que le résultat de (2^n)-1 soit aussi un nombre premier !
(2^3)-1=7
'3' et '7' etant premiers, '3' est donc un nombre de Mersenne.
Mais saviez vous que certains nombres premiers n'ont JAMAIS aucune incidence dans le crible d'un quelconque nombre au format (2^n)-1 ?
(ps : je fais toujours référence a des nombres de mersenne qui ne sont jamais inferieur a 7)
En voici la preuve. Prenons le nombre premier '3' :
3[OXO]
Peut il cribler le '7' (un nombre de mersenne) ? non. Le 7 tombe sur le premier symbole.
Mersenne suivant : le 31 (et oui, rapellez vous que dans (2^n)-1, le 'n' est impair puisque 'n' DOIT etre premier pour valider l'une des 2 condition d'un mersenne premier) Le crible t'il ?
Non, car le 31 tombe aussi sur le premier symbole. On est donc CERTAIN que QUEL QUE SOIT 'n' (impair), on tombera TOUJOURS sur le premier symbole 'O'
Pour le nombre premier '5', c'est pareil :
5[OOXOO]
7 tombe sur le 4eme symbole ('O')
31 tombe le 1er symbole ('O')
127 tombe sur le 4eme symbole !! (comme pour le '7'). La boucle est bouclé : '5' n'aura jamais d'incidence sur les nombres au format (2^n)-1 (avec n impair, toujours !)
On sait donc que '511' tombera sur le symbole 1.
Le chiffre 7 par contre a une incidence :
7[OOOXOOO]
7 tombe sur le symbole 'X' (comment '7' pourrait il cribler '7' !! pas possible évidement mais on le note quand meme)
31: tombe sur le 2eme symbole
127 : tombe sur le 1eme symbole
511 : tombe sur 'X' (511 est donc éliminé par le nombre premier 7)
2047 : tombe sur le 2eme symbole
8191 : tombe sur le 1eme symbole
32767 : tombe sur 'X' (32767 est donc éliminé par le nombre premier 7)
On vois bien que les résultats se répètent donc, la boucle est bouclé...
Cette technique de l'ADN (en l'état actuel) a cependant un inconvégnent : il faut compter et faire des reports pour savoir sur quel symbole on tombera !
Alors, pourquoi ne pas construire un ADN qui s'adapterait directement aux nombres de mersenne (ce nouvel ADN, nous l'appellerons 'ADN de Mersenne')
Ca voudrait dire que le 3 et le 5 aurait un AND vide : [] ou [O] mais ca, on s'en fiche (seuls les ADN remplit nous interesseront)
Donc, au lieu de construire un ADN contenant des symboles qui font référence a des nombres, on utilisera plutot les memes symboles faisant reference à 'n' de l'expression (2^n)-1. Tout en utilisant toujours des nombres impairs et en commencant à 1, on aura :
7[OXO]
Le premier symbole nous dit que 7 ne crible pas 2^1-1
Le 2eme symbole nous indique qu'il crible 2^3-1
Le 3eme correspond à (2^5)-1
En bouclant, le symbole 1 correspond maintenant à (2^7)-1, etc...
Evidement, '7' ne peux pas cribler '7'. En fait, quand on crible un nombre, on peux s'arréter à sa racine. Par exemple, '17' pouvait éventuellement etre criblé par '3' car 3*3<17 mais il ne peux plus etre criblé par '5' et superieur car 5*5 crible à partir de 25 (>17 donc).
Comment savoir quels nombres premiers peuvent cribler un nombre de Mersenne ?
Simple : prenez un ADN de base (pas un ADN de mersenne)
11[OOOOOXOOOOO]
On a 11 symboles numéroté de 1 à 11.
Faites une marque sur le symbole 1 (ici, la marque sera symbolisé ici par # couvrant le symbole) :
11[#OOOOXOOOOO]
Multipliez ce nombre par 4 et marquez ce nouveau symbole :
11[#OO#OXOOOOO]
Multipliez encore (et toujours) par 4. Ca donne 16 mais comme on a 11 symbole, on rabat le reste de 16-11 au debut. On marque donc '5' :
11[#OO##XOOOOO]
Multipliez ce nombre (notre '5') par 4 (ca fait 20-11=9) et marquez ce nouveau symbole :
11[#OO##XOO#OO]
On continu (9*4=36. 11*3=33. 36-33=3) :
11[#O###XOO#OO]
puis (3*4=12. 12-11=1) :
11[#O###XOO#OO]
Et là, on a fini le test (que l'on appellera 'Test des cribleurs de Mersenne') car on viens à nouveau de marquer le symbole 1
Si notre symbole 'X' est rayé, c'est que le nombre premier (ici '11') est un cribleur de Mersenne (ici, '11' n'a JAMAIS d'incidence sur un Mersenne).
Je sais, c'est nouveau pour vous mais c'est précisement ce qui ce passe mathématiquement. Libre à vous de vérifier avec toutes les méthodes que vous voulez...
================
J'ouvre une parenthèse :
Saviez vous que cette technique permettait de voir si un nombre quelconque est premier ??
C'est même ainsi que l'on trouve la racine primitive modulo P (au dire de certains..) d'un nombre !!
Il faut procéder de la meme facon mais avec une multiplication par 2 (le 'X' on s'en fiche ici car pour prouver qu'il est premier, on n'en a pas besoin)
Par exemple :
13[OOOOOOOOOOOOO] (on a 13 symboles)
On applique donc la technique du *2:
13[#OOOOOOOOOOOO]
13[##OOOOOOOOOOO]
13[##O#OOOOOOOOO]
13[##O#OOO#OOOOO]
13[####OOO#OOOOO]
13[####O#O#OOOOO]
13[####O#O#OOO#O]
13[####O#O#OO##O]
13[####O#O#OO##O]
13[####O#O##O##O]
13[######O##O##O]
13[######O#####O]
13[############O]
13[############O] Ici on viens de recribler un symbole deja criblé (ici le 1) donc le test s'arrete.
Si tous les symboles excepté le 13 (car ici on testait '13') sont criblés, c'est que 13 est premier !!
(la racine primitive modulo P de 13 est donc le multiplicateur que l'on a utilisé; ici : 2)
Essayons 17 (car il y a un astucieux probleme) :
17[#OOOOOOOOOOOOOOOO]
17[##OOOOOOOOOOOOOOO]
17[##O#OOOOOOOOOOOOO]
17[##O#OOO#OOOOOOOOO]
17[##O#OOO#OOOOOOO#O]
17[##O#OOO#OOOOOO##O]
17[##O#OOO#OOOO#O##O]
17[##O#OOO##OOO#O##O]
17[##O#OOO##OOO#O##O] Double crible en 1
Si au moins un nombre (excepté le 17 car ici on test '17') n'est pas marqué, c'est qu'on n'a rien prouvé. Il faut donc recommencer le test mais avec un autre multiplicateur. Lequel ???
Et bien le test avec *2 etant fini, cela nous indique quels autres multiplicateurs nous devons essayer.
Ici, on a : 17[##O#OOO##OOO#O##O]
On doit donc essayer le '3' puis, si cela ne marche pas, on essayera le '5', puis le '6' puis le '7' puis 10; 11; 12 et 14 (mais jamais le 17 car on test le nombre '17')
Regardons donc ce que donne le multiplicateur '3' (1; 3; 9; 27; etc....) :
17[#OOOOOOOOOOOOOOOO]
17[#O#OOOOOOOOOOOOOO]
17[#O#OOOOO#OOOOOOOO]
17[#O#OOOOO##OOOOOOO]
17[#O#OOOOO##OO#OOOO]
17[#O#O#OOO##OO#OOOO]
17[#O#O#OOO##OO#O#OO]
17[#O#O#OOO###O#O#OO]
17[#O#O#OOO###O#O##O]
17[#O#O#OOO###O####O]
17[#O#O#OO####O####O]
17[#O#O#O#####O####O]
17[#O###O#####O####O]
17[#O###O##########O]
17[#####O##########O]
17[################O]
17[################O] Double crible sur 1
Bingo, tout est coché (sauf lui meme evidement) , donc '17' est premier
(la racine primitive modulo P de 17 est donc le multiplicateur que l'on a utilisé; ici : 3)
Essayont avec le non premier 9 :
9[#OOOOOOOO]
9[##OOOOOOO]
9[##O#OOOOO]
9[##O#OOO#O]
9[##O#OO##O]
9[##O##O##O]
9[##O##O##O] Double crible sur 1
On doit donc tester les multiplicateurs '3' et '6'
9[#OOOOOOOO]
9[#O#OOOOOO]
9[#O#OOOOO#] STOP : Le crible sur '9' me prouve que '9' n'est pas premier.
Je ferme la parenthèse sur ce test de primalité...
================
En faisant le Test des cribleurs de Mersenne sur un quelconque paquet de nombre premier, on se rend compte qu'environ 41% des nombres premiers sont des cribleurs de Mersenne (59% des nombres premiers n'internevant JAMAIS dans le crible des Mersenne).
En voici une courte liste (mais je vous encourage bien sûr à vérifier TOUT ce que je dis au fur et à mesure) :
7; 23; 31; 47; 71; 73; 79; 89; 103; 127; 151; 167; 191; 199; 223; 233; 239; 263; 271; 311; 337; 359; 367; 383
431; 439; 463; 479; 487; 503; 599; 601; 607; 631; 647; 719; 727; 743; 751; 823; 839; 863; 881; 887; 911; 919....
Quel aspect ont les ADN de mersenne ?
Réponse :
7 [OXO]
23 [OOOOOXOOOOO]
31 [OOXOO]
47 [OOOOOOOOOOOXOOOOOOOOOOO]
71 [OOOOOOOOOOOOOOOOOXOOOOOOOOOOOO OOOOO]
73 [OOOOXOOOO]
79 [OOOOOOOOOOOOOOOOOOOXOOOOOOOOOO OOOOOOOOO]
89 [OOOOOXOOOOO]
103 [OOOOOOOOOOOOOOOOOOOOOOOOOXOOOO OOOOOOOOOOOOOOOOOOOOO]
127 [OOOXOOO]
151 [OOOOOOOXOOOOOOO]
etc........ (contrairement à l'ADN d'un nombre, l'ADN de mersenne est très variable)
On se rapelle, un ADN de Mersenne se lit comme ca :
7 [OXO] = [2^1-1; 2^3-1; 2^5-1] puis ca boucle avec les puissances impaires suivantes...
Vous remarquerez que systématiquement, tous les ADN de mersenne sont constitué du même nombre de symboles 'O' avant qu'après le symbole 'X' !
Je ne sais pas si cette 'particularité' est déjà mathématiquement prouvée mais elle est SYSTEMATIQUE (j'attend bien sûr un quelconque contre exemple).
Cela voudrait dire qu'à 'interval' régulier, un cribleur de Mersenne agit.
Regardez bien les ADN de mersenne ci-dessus. Vous n'avez pas remarqué quelque chose de logique ??
Et oui, on vois qui sont les Mersenne Premiers :
7 [OXO] ici, le 3 est coché (2^3-1=1) !
31 [OOXOO] ici, le 5 est coché !
127 [OOOXOOO] ici, le 7 est coché !
Allez, pour le plaisir, je vous copie l'ADN de 8191 :
8191 :[OOOOOOXOOOOOO] 13, Bingo !
Par contre, autant il n'y a apparement jamais 2 ADN de mersenne premiers identiques, autant on peux rencontrer plusieurs ADN de mersenne non premier identiques.
Par exemple :
23 [OOOOOXOOOOO] 11 est premier, 23 aussi, mais 23 n'est en aucun cas un éventuel Mersenne
89 [OOOOOXOOOOO] 11 est premier, 89 aussi, mais 89 n'est en aucun cas un éventuel Mersenne
(Là encore, si il y a mathématiquement une incertitude, une erreur ou un quelconque contre exemple, n'HESITEZ PAS)
Nous voici donc à la dernière étape :
J'attire votre attention sur le fait que 2 est le PREMIER nombre premier.
Le 3 est un mersenne premier de 2 (2^2-1)
Le 7 est un mersenne premier de 3 (2^3-1)
Le 127 est également un mersenne premier (de 7)
Cela peut il continuer ?
.... A SUIVRE (en cours de rédaction)
Dernière modification par SPH ; 22/09/2005 à 23h00.
bonjour, je me suis amusé en modifiant WorkToDo.ini à lui faire essayer 2^6972593-1 (qui est premier découvert en 1990...)
il me dit au bout d'une heure que il a: "
factoring M6972593 to 2^61 is 21.21% complete Time: 235sec
"
qu'est-ce que veut dire le 2^61 ??
qu'il a fait 2^61 opérations ???
combien doit-il en réaliser EN TOUT ????
salut merci d'avance
il va passer ensuite au test de lucas et itérer les opérations de ce test = 6972593 -1, itérations
pas mal de temps en fonction des capacités de ton pc.
tu peux controler en regardant ce nombre d'itération le temps qu'il met, avec le pourcentage réalisé
bonsoir.
je n'ai pas tout compris...
il faudrait je pense que je comprenne grosso modo quel algorithme il utilise pour un grand nombre de mersenne comme celui la...
et enfin dernière question, quel temps ça prendrait de tester 2^(2^31-1)-1 ?? (Mn où n est un nombre de mersenne) ? (2^31 = 2milliards...)
je te l'ai dit au début : test de Lucas lhemer
le temps mis environ pour ta question peut être un mois, si il faut aller jusqu'à la fin des tests .
Je teste actuellement un mersenne de presque 38 millions. J'ai a peu pret 71 jours de calculs ! (j'en suis a 5.34%)
Je pense que pour un Mersenne de 2 milliards, tu en a LARGEMENT pour quelques années !!
On se revoit dans 4 ans ? lol, tu es sur que ton algo est plus rapide que prime95 ?
Et quelle chance as-tu que ce mersenne soit premier ?
SPH
Tu l'as choisis en fonction de quel critère ton exposant?
si ce n'est pas confidentiel...
et 5,34% cela te donne quel nombre d'itération ?
Justement, j'ai failli faire un post sur le choix du mersenne a tester.
Je souhaitais savoir si il y avait des criteres sûrs pour choisir un bon candidat. Mais je ne pense pas qu'il y ait un critere absolu qui caracterise tous les mersennes actuellement premiers.
Iteration : 2050000/379xxxxx
M(M(31)) n'est pas premier : il est divisible par 295257526636031.
Pour le vérifier?
Il faut calculer 2^k mod p. Si c'est égal à 1, M(k) est divisible par p.
Comment le calculer?
Comme prime95 (enfin je pense que c'est comme ça qu'il le font) :
Tester les p=2*k*i+1.
Pour les nombre de la forme M(M(x)), les plus petits au statut inconnu de primalité sont : 61,127.
(Il est possible d'aller sur www.mersenne.org à la page "autres projets" et de regarder à MM61)
A+
Bon, quelqu'un peut il me rapeller quelle methode utilise prime pour tester un nombre pour voir s'il crible un mersenne ?
J'ai reussi a diviser par 4 les nombres a tester et a etablir 2 operations (dont un modulo) pour savior si un premier elimine un mersenne.
Il ne fait pas comme ça.
Il fait plutôt ça :Après, il fait le test de Lucas-Lehmer.
Peux-tu décrire ton nouveau test?
A+
J'ai encore quelques reflexions a faire aboutir.
Mais pour donner un exemple, M(23) me demande 45591 nombres a cribler (et encore, 1/5eme de ces nombres finissent par 5, donc, inutine de les tester. Et le reste n'est pas entierement constitué de nombre premier ce qui reduit ENCORE les tests)
Pardon, pour M(23), je teste au mùaximum 18235 nombres (qui finissent par 1;3;7;9 mais si j'applique un test de primalité sur ces cribleurs du mersenne 23, cela reduirait le nombre de cribleur a tester*)
*A propos, je me demande s'il est avantageux de tester si un cribleur est premier car ce test peux etre plus long que la methode qui l'utilise pour voir si il crible le Mersenne...
