>>> Ma conjecture sur les Mersenne !!

[SPH]

A Easythomas et aux autres, voici mon article corrigé, simplifié, clarifié.
Moi, je ne saurait pas le traduite en formule; alors, si quelqu'un peux...

"LA CONJECTURE MAGNIFIQUE DE SPH"

Cette article parlera des nombres premiers et des nombres premiers de Mersenne. 'Deux' étant 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 3; 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 3(3*1); 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 : oxooxooxooxooxooxooxo......
Cette chaine (en caractères minuscules) 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 petite 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 (en se repositionnant sur 'x' après une boucle).
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 auront 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 et, à part '2', il n'y a aucun autre nombre premier pair) 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'
Pourquoi en etre certain ?
Car un mersenne a un format 2^n-1 (avec 'n' impair)
Pour simplifier, s'il avait été au format 2^n, nous aurions eu cette suite : 2; 8; 32; 128; 512; 2048; 8192; etc....
Avec un ADN qui aurait été lui aussi pair; c'est à dire [2; 4; 6], on comprend que 2 et 8 tombent sur le premier symbole. Inutile de continuer car le prochain nombre tombera aussi sur le premier symbole. Ce prochain nombre fait en effet 2 fois plus de parcours que 8 par rapport à 2. Puis le prochain fera encore 2 fois plus de parcours que 32 par rapport a 8; etc.....
Voila ce qui explique cette régularité imperturbable.

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'
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' et pour le differencier, il sera en symboles majuscules)
Ca voudrait dire que le 3 et le 5 aurait un ADN vide mais ca, on s'en fiche (seuls les ADN remplit nous interesseront)
Donc, au lieu de construire un ADN avec des symboles faisant référence à des nombres, on prérèrera qu'ils fassent référence à '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...
Quand on crible un nombre pour voir s'il est premier, on peux seulement tester les nombres entre 2 et sa racine carré. 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 quel nombre premier peut cribler un nombre de Mersenne ?
D'abord, situons précisement où se trouvent les Mersenne.
TOUS les mersennes se trouve dans la derniere case d'un tableau carré dont le coté possede 2^n nombres (on bosse avec des nombres impairs a partir de 1).
En 'dessinant' ca, voila ce que ca donne :
Tableau de 2 cases de coté :
01 03
05 07

tableau de 4 cases de coté :
01 03 05 07
09 11 13 15
17 19 21 23
25 27 29 31

tableau de 8 cases de coté :
01 03 05 07 09 11 13 15
17 19 21 23 25 27 28 29
31 33 35 37 39 41 43 45
47 49 51 53 55 57 59 61
63 65 67 69 71 73 75 77
79 81 83 85 87 89 91 93
95 97 99 00 00 00 00 00
00 00 00 00 00 00 00 00

16 cases de coté, 32 cases de coté, 46 cases de coté, 128 cases de coté, 256 cases de coté, 512 cases de coté, etc.........

Voila pourquoi, on observe si l'ADN d'un nombre; par exemple 11
11[OOOOOXOOOOO]
n'a pas dans sa suite le 'X' correspondant a tous les emplacement des mersennes; soit : 4; 4*4; 4*4*4; 4*4*4*4; 4*4*4*4*4; etc...

Voilà comment ce test s'exprime : 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]
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 notre nombre premier (ici '11') est un cribleur de Mersenne (comme le 'x' est encore apparent, c'est que '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.
(Le crible prouve qu'un nombre n'est pas premier quans on crible le nombre lui meme ou quand on crible 2 fois un autre nombre que le 1)

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 n'a plus le même nombre de symboles que le nombre lui même)

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 suivantes...

Cet ADN montre 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=7) !
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 !
Il n'y a jamais 2 ADN de mersenne premiers identiques. Mais ce n'est pas le cas pour les ADN de mersenne non premier.
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
De plus, 23*89 donne 2047; un nombre de Mersenne non premier (ce nombre, c'est bien sûr 2^11-1)

J'invite chacun a donner son avis...
-----

[inviteb0cf188d]

... sinon demander l'avis de tony reix . je crois qu'il a participé au test du 42ème Mn.

Oui, j'ai fait la course pour vérifier que le candidat M42 était bien premier, en utilisant le programme GLucas (multi-threadé). En 5 jours de calcul, au lieu de 30 environ sur un PC rapide. Mais je ne suis pas mathématicien pour autant ... J'essaye d'apprendre en lisant et étudiant des bouquins ou sur le Web.
Par exemple, je vous recommande de regarder les pages de MathWorld ou les Prime Pages ou le Wiki du GIMPS. Egalement, vous pouvez (gratos !) avoir le chapitre prouvant le LLT du super livre de P. Ribenboim Little Book for Bigger Primes (Sample page). J'ai utilisé cette méthode pour prouver un test (pas plus rapide que le test de Pépin) de primalité des nombres de Fermat.
Mais il vous faut pouvoir lire de l'anglais (assez simple).
Et puis il vous faut savoir faire un peu de LaTeX pour présenter proprement vos idées.

Pour le test , il me semble me souvenir que les nombres de Mersenne passent ce test pour a=2.
Le problème de ce test, c'est que si le test passe pour a=2, 3, ... , cela ne prouve pas que p est premier. Seul le LLT le prouve rapidement. Il se pourrait bien (Cosgrave, mais ce n'est pas prouvé) que Mp est premier lorsque le test réussit avec a=3.

Pour appuyer ce qu'a dit "easythomas", oui, il vaut mieux prouver la méthode avant de se lancer dans le codage !
Et, au lieu d'écrire en C tout de suite, on peut expérimenter avec l'outil PARI/gp (Windows ET Linux). C'est beaucoup plus facile !
Par exemple, dans la directory examples de PARI, il y a le code PARI pour la méthode de factorisation Rho Pollard et la méthode de Brent.

Enfin, quelqu'un a exprimé une bonne idée (à mon avis, tout du moins) :
1) trouver une propriété (vérifiable plus rapidement que le LLT !) que possède BEAUCOUP (ou tous) de Mersenne premiers, et que possède PEU (ou pas du tout) de Mersenne composites,
2) chercher des candidats de Mersenne premiers grâce à cette propriété,
3) utiliser le LLT (avec prime95) pour vérifier/prouver la primalité des candidats.
(Cela fait un bout de temps que je cherche ...)

Donc : CONTINUEZ à avoir des idées !
Mais confrontez-les à la réalité en les prouvant et en vérifiant que cela va plus vite que les tests existants.

(En attendant, je n'ai toujours pas une idée claire des idées que vous manipulez dans ce thread ...)

OOoopppsss
SPH vient juste de publier son article juste avant moi. Je vais le lire.

Cordialement,
Tony

[SPH]

Enfin, quelqu'un a exprimé une bonne idée (à mon avis, tout du moins) :
1) trouver une propriété (vérifiable plus rapidement que le LLT !) que possède BEAUCOUP (ou tous) de Mersenne premiers, et que possède PEU (ou pas du tout) de Mersenne composites,
2) chercher des candidats de Mersenne premiers grâce à cette propriété,
3) utiliser le LLT (avec prime95) pour vérifier/prouver la primalité des candidats.
(Cela fait un bout de temps que je cherche ...)

Peut tu préciser qui c'est et quelles idées ont été exprimé ?

[invite3bc71fae]

Je n'ai pas tout lu, mais il y a toutes les caractéristiques d'un véritable travail d'expérimentation mathématique...

J'essaierai peut-être de voir comment ça peut se reformuler de manière plus conventionnelle ou si ta notation des nombres présente un intérêt majeur...

Bravo d'avoir obtenu quelque chose...

[invite3bc71fae]

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é...

Ca vient du fait que Z/pZ est un corps si et seulement si p est premier...

[invited6139184]

(En attendant, je n'ai toujours pas une idée claire des idées que vous manipulez dans ce thread ...)

En somme, SPH nous fait une sorte de "machine à tisser".

Il détecte un NP, puis il regarde son environnement immédiat( son ADN). Et Il le recopie à l'infini. Puis il prend le NP suivant et note son environnement et fait de-même ... Etc

Je vous dis, c'est ni plus ni moins qu'une machine de Jacquemard.

Enfin, c'est ce qu'il me semble !

[inviteeecca5b6]

Humhum...

Quand on regarde:

- Le nombre d'operations que tu fais pour savoir sur quel parti de l'ADN de tels nombre premier va tomber le nombre de mersenne,

- La taille de tes ADN qui sont a moitier aussi grands que tes nombres,

- Les nombreux tests que tu dois faire (par exemple, on sais que si ca tombe sur ca ou ca ou ca ou ca alors c'est possiblement un nombre premier... Et bien sur, plus le nombre est grand, plus il y a de ca ou ca, donc la complexite sera certainement pas lineaire, loin de la !)



Ben je me dis que t'as plus vite fait (pour les grands nombres) d'utiliser un simple cribleur.

Biensur pour les petites nombres, t'es etonne par la vitesse... t'as deja teste d'autres algorithmes ? Je me souviens d'un temps ou je faisais de petits programmes tout betes en pascal, et la primalite d'un nombre dans les 10^6 etait teste dans les 3~4 secondes. Alors aller 4 fois plus vite en assembleur, finalement rien d'etonnant...

[invite3dc2c2f6]

Salut
hé bien je trouve que la technique de sph est tres astucieuse, et se revelera tres performante; au lieu de manipuler des valeurs numeriques, nous avons la (a mon avis) un outil qui les represente: comme les nombres decrivent une quantité, son système decrit une propriété des nombres.
Or, cette propriété s'avere commune pour X nombres, avec un ADN (different de adn, si j'ai un peu compris son truc) variable en taille. A mon avis, ca vaut le coup si l'ADN d'un nombre comme 123456789123546789123456789789 123456 peut tenir sur 10 symboles.
En tout cas, le fait de considérer un rapport entre des nombres et rechercher comment il varie en fonction des qualités de ce nombre, je trouve ca tres amusant et fin.... mais bon, moi et les maths, ca fait trois.. non deux.
manu.

[SPH]

Bon,je ne sais pas si ca peut aider mais peut etre que 2^i+i-2 donne seulement des non premiers (j'ai essayé jusqu'à un résultat de 15 chiffres).
Sinon, pour les ADN, comme il y a autant de symboles que la valeur de 'X', on peut bien sûr remplacer notre orthographe :
7 [OXO]
23 [OOOOOXOOOOO]
31 [OOXOO]
47 [OOOOOOOOOOOXOOOOOOOOOOO]
par :
7 [3]
23 [11]
31 [5]
47 [23]
Peut etre qu'il y a une manip 'magique' qui nous échappe pour l'instant et qui permettrait avec une simple operation de trouver les mersenne.
Par exemple, 2[3] donne 7. Comme M(2)=3, on sait que 7 est premier. Maintenant, si on arrive a démontrer que les décallages de tous les autres ADN 'bouclent' avec la suite M(3); M(7); M(127), on pourrait etre certain (je pense) que M(M(127)) est premier.
Ouai, moi, je mise entre autre sur le 'bouclage' des ADN

[leg]

bonjours a tous . l'idée de SPH est qu'il a fait ressortir cette propriété , voir les post plus haut et notament, les justifications apportés gentilment par moma, qui on permis d'y voir plus clair qans la transmission de CET ADN au résultat de 2^P -1.
mais cet ADN se transmet aussi d'une autre façon ce qu' a expliqué SPH.
or c'est justement cette propriété qui fait un Mersenne premier. si il EXISTE P ou plusieur tel que P = le même ADN que le résultat de 2^P -1 , il ne peut être premier.
la formule que pole indique, ne peut être exploité, sous réserve:
4*23 -1)mod11)+1 = 4 ce qui revient si j'ai bien compris à, raccourcir le tableau de sph directement pour obtenir L' A D N .
4*23= 92; (92-1) / 11 = 3,.. et 3+1 =4.
on remarque aussi souvent que l'ADN de P est égale a (P -1)/2 exmple avec 23, 47 et d'autre .
mais il faut faire attention car dans la formule de pole si je prend 107 il correspond au même résultat que 23 ,
il ne divise pas 2^53 -1, mais il donne 2^107 -1 prime!
est de plus ce n'est pas un cribleur tel que défini par SPH .
donc cette formule n'en fait pas pour autant des cribleurs . qu'elle explication peut-on, en retirer ? puisque pour çetre un Mersenne cribleur avec le Même ADN que l'exposant il faut que X soit barré dans son tableau si j'ai bien tout compris.
autre remarque: il est vrai que de grands nombres peuvent se retrouver avec un petit ADN. et si il ne reste que ce grand nombre tel qu'il a divisé déjà 2^p -1 ;comme le fait
23 et 89 il a de grande chance d'être premier.
ce qui permet de constater que plusieur Premier ont le même ADN on peut dire des caractéristiques communes ! d'où l'ADN de 7 n'irra pas diviser l'ADN de 11 par exemple.

[leg]

sph , pour quoi tu as laissé ceci:
89 [OOOOOXOOOOO] 11 est premier, 89 aussi, mais 89 n'est en aucun cas un éventuel Mersenne
puisque 2^89 -1 est premier ?

[SPH]

sph , pour quoi tu as laissé ceci:
89 [OOOOOXOOOOO] 11 est premier, 89 aussi, mais 89 n'est en aucun cas un éventuel Mersenne
puisque 2^89 -1 est premier ?

Oui tiens, erreur de ma part. C'est parce que je pensais que les mersennes premiers ne rentraient pas dans la composition d'un nombre non premier.

[leg]

Pour le test , il me semble me souvenir que les nombres de Mersenne passent ce test pour a=2.
Le problème de ce test, c'est que si le test passe pour a=2, 3, ... , cela ne prouve pas que p est premier. Seul le LLT le prouve rapidement. Il se pourrait bien (Cosgrave, mais ce n'est pas prouvé) que Mp est premier lorsque le test réussit avec a=3.
Tony

bonjour tony:
étant donné que l'ADN de 2^p -1 = adn de l'exposant
exemple: 2^7 -1 = 127
adn de 7 = 000x000, mais ADN de 2^3-1 = 7 = O X O
d'où ADN de 127 = O O O X O O O;
puisque cela est = à :

(2^1-1) (2^3-1) (2^5-1) (2^7-1) (2^9-1)(2^11-1)(2^13-1)

pourrait-on ramplacer a par y et p par ADN reste a savoir qui est y,
tel que cela est la même correspondance que:

[leg]

suite: je pensais a:
2^23 -1 = Z alors si Z est premier 23^Z congrue 23(modulo Z); où 23 est l 'ADN de Z.

[inviteeecca5b6]

on remarque aussi souvent que l'ADN de P est égale a (P -1)/2 exmple avec 23, 47 et d'autre

Non seulement on le remarque souvent, mais en plus c'est a chaque fois le cas ! Enfin pour tout nombre impaire...


Je vais essayer de resumer:

Ce que SPH fait, c'est determiner si un Mersenne est premier ou non en utilisant seulement son "ADN".
Selon sa conjecture:
Si le X de l'ADN du nombre a tester tombe sur le ieme caractere d'un nombre de mersenne precedent, alors on sait si il est possiblement premier ou non.

Pour l'instant j'ai bon ?

En admettant que j'ai bon, je trouve que cette maniere de faire est extrement couteuse du a sa complexite et au nombre de test (if then else) qu'il faut faire pour les grands nombres.

Je pense vraiment qu'un simple algorithme consistant a diviser le nombre a tester par tout les premiers precedants est moins couteux, donc plus rapide pour les grands nombres.

Edit: et surtout j'ai remarque que tu avais besoin de TOUS les mersennes precedents, pas seulement jusqu'a la racine...

[leg]

Non seulement on le remarque souvent, mais en plus c'est a chaque fois le cas ! Enfin pour tout nombre impaire...
.

2^31-1= prime
ADN de 31 = 5 = O O X O O
désolé tu n'as pas compris son principe car ta solution serait 15 ce qui est faux!

[leg]

: et surtout j'ai remarque que tu avais besoin de TOUS les mersennes precedents, pas seulement jusqu'a la racine...

refaux désolé

[leg]

l'ADN = (4 n) congrue ((p-1)/2)+1 modulo P ;
mais a chaque fois n change puisqu'il s'agit du reste de (4 n) par Pe c'est donc le nombre d'opération qui te donne l'ADN des l'instant où:
(4 n)= ((p-1)/2)+1 (modulo P)
par ex pour 337 a la 11ème opération tu obtiens le résultat recherché ce qui fait que 337 = OOOOOOOOOOOXOOOOOOOOOOO= adn.11
sous réserve que je ne dise pas de blague .

[inviteeecca5b6]

2^31-1= prime
ADN de 31 = 5 = O O X O O
désolé tu n'as pas compris son principe car ta solution serait 15 ce qui est faux!

OK, on parlait pas du meme ADN...
Je parlais de l'ADN et toi de l'ADN de mersenne

[inviteeecca5b6]

Oups, j'ai lu entierement l'article de SPH, et en effet j'ai dit de grosses betises, veuillez m'en excuser...

[SPH]

Les NP savent dessiner. C'est fou tout ce qu'on peux decouvrir sur eux (Tableau de nombres premiers)
Mis bout à bout, ca represente peut etre la Joconde ?!!!?! .....

[inviteeecca5b6]

Ca c'est tres connu ! Dans ma jeunesse j'avais fait ca en pascal... Ca s'appelle comment deja ??

[leg]

Oui tiens, erreur de ma part. C'est parce que je pensais que les mersennes premiers ne rentraient pas dans la composition d'un nombre non premier.

ne confond pas: le résultat de 2^89-1= ADN.89 et non pas 11
sinon 7, 31 ne donnerait pas de Mn premier. quel nombre de mersenne = (2^p-1) < a la racine carrée de 2^31-1, a comme ADN 31? si il y en a deux tu aurais ADN31* ADN31= 2^31-1 sinon tout cela ne voudrait rien dire non?
quel est l'ADN de 233, 1103, 2089 ? si je t'ai suivi, ADN29
232/4=58, 58/2=29 il existe 4n=29(233)
il doit exister 4n=29(1103) ainsi que 4n=29(2089)

[SPH]

Ca c'est tres connu ! Dans ma jeunesse j'avais fait ca en pascal... Ca s'appelle comment deja ??

Ca s'appelle des fractals ou des courbes de mandelbrot (un truc comme ca) mais ca ne dependait pas des NP

[invite3d7be5ae]

Il ne marche pas chez moi. Qu'est-ce que ça donne? (Et comment tu le fais?)

[SPH]

Il ne marche pas chez moi. Qu'est-ce que ça donne? (Et comment tu le fais?)

je commence a un endroit de l'ecran a marqquer les nombres premiers puis je continu a aller a gauche.
Je regarde tous les nombres impairs a partir de 1 et je marque par un point ceux qui sont premiers.
dès que je rencontre un nombre premier, je tourne d'un quart de tour.

[SPH]

Allez voir la : LIEN
Il y a 2 images qui represente les traces laissé par les NP. L'un tourne de 1/4 a chaque rencontre d'un NP, et l'autre tourne d'1/8.

..... NON, je n'ai pas dit que les NP ont fabriqué les galaxies !!

[SPH]

Bon, j'ai juste une question mais qui merite avant tout un exemple :
prenons un nombre : le 17
prenons une position de départ : le 1
prenons un multiplicateur : le 3
Imaginons notre 17 comme etant une graduation de 1 a 17.
Y a t'il une operation mathematique simple qui donne instantanement le resultat suivant :
on multiplie le 1 par 3, puis le resultat obtenu par 3 (tjr 3), etc... jusqu'a depasser notre 17 (ca fera 1; 3; 9; 27). Le résultat immédiat que je cherche est la difference entre 27 et notre 17 (10 donc).
Je cherche donc un espece de modulo de depassement.
merci

[invite3dc2c2f6]

Salut
on peut essayer un algorithme:

DEBUT
ecrire "entrer borne max"; BMax
ecrire "entrer borne mini"; BMin
ecrire "entrer multiplicateur"; Mult

TantQue BMin<BMax Faire
BMin<-BMin*Mult
FinTantQue
BMin<-BMin*Mult /* pour avoir le resultat immediatement suivant */

Resultat<-BMin-BMax

Lire Resultat

FIN

Voila pour l'algo, je sais pas si ya des trucs en maths permettant cela immediatement; pitetre il faut voir du coté de la geometrie analytique, mais j'y connais rien^^
Manu

[invitebf65f07b]

Bon, j'ai juste une question mais qui merite avant tout un exemple :
prenons un nombre : le 17
prenons une position de départ : le 1
prenons un multiplicateur : le 3
Imaginons notre 17 comme etant une graduation de 1 a 17.
Y a t'il une operation mathematique simple qui donne instantanement le resultat suivant :
on multiplie le 1 par 3, puis le resultat obtenu par 3 (tjr 3), etc... jusqu'a depasser notre 17 (ca fera 1; 3; 9; 27). Le résultat immédiat que je cherche est la difference entre 27 et notre 17 (10 donc).
Je cherche donc un espece de modulo de depassement.
merci

salut,

tu veux n tq et puis calculer la valeur de ? (dans ton exemple, on aurait a=3 et b=17)

Si c'est ça, le mieux serait de passer au log : et
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 .