A propos de nombres premiers

[fweil]

@Ollivier

Je veux bien un zeste plus précis sur ton explication ... je suis pas forcément des plus vifs d'esprit ! Mais ça m'intéresse bigrement ^^

Entre temps je prépare quelques menues retouches sur le package et je publierai une 7.2 d'ici peu. J'ai en particulier, pour la partie perfs, intégré quelques éléments supplémentaires de simplification, dont une écriture optimisée de calcul de modulo via FPU tout à fait ravissante.

[Ollivier]

Le but est de trouver les nombres pairs, triples, quintuples, septuples, etc... (Respectivement les multiples de 2, 3, 5, 7, etc...)

Voyons où sont les pairs dans n :

n = x : parité
=============
n = 1 : non
n = 2 : oui
n = 3 : non
n = 4 : oui
etc...

On peut interpréter la succession de "non/oui" comme suit :

1010101010101010 etc...

en légendant 1 = non et 0 = oui

Là, on a étudié les nombres pairs dans la suite naturelle n, et on peut conclure que ça s'alterne. On constate que l'état 0 qui indique un "oui" pour la parité implique que le nombre n concerné est pair donc formellement non-premier. Ça s'apparente au crible.

Continuons avec les triples... Si, dans une suite naturelle n, zéro (0) représente les triples et un (1) représente les nombres non triples, ça donne :

110 110 110 110 etc... (j'ai mis des espaces parce que sinon, ça pique les yeux)

Toujours dans les triples, "sophistiquons". Admettons maintenant que zéro (0) reste toujours la représentation, mais que un (1) ou deux (2) représente un nombre non triple. Résultat ordonné décroissant:
210 210 210 210 etc...

Continuons sur le même principe avec 5 :
43210 43210 43210 etc...

Avec 7 :
6543210 6543210 etc...

On peut continuer ainsi à l'infini, mais bon!

Maintenant, regroupons :
1010101010101010 anti-crible des *2
210 210 210 210 anti-crible des *3
43210 43210 43210 anti-crible des *5
6543210 6543210 anti-crible des *7

Ensuite, tassons :

Code : Tout sélectionner

1010101010101010
210210210210
432104321043210
65432106543210

Voilà fweil : ce tas balisé est le "négatif" du crible d'Erathostène.

Les SIMD (Une instruction pour plusieurs données) pourraient s'inscrire ainsi :

Code : Tout sélectionner

101010(1)010101010
210210(2)10210
432104(3)21043210
654321(0)6543210

Ici, la SIMD (qui calcule par paquet de 4 variables) traite les valeurs 1, 2, 3, 0. Il y a juste à soustraire pour balayer le crible. Quand un "zéro" est détecté on réinitialise le nombre premier correspondant à la place de zéro.

N'hésite pas si tu vois un souci!

[SPH]

Super

Mais j'ai deccroché a la fin. Ici precisement :

Les SIMD (Une instruction pour plusieurs données) pourraient s'inscrire ainsi :

[JohnJohnsonSHERMAN]

C'est quoi un nombre premier?

(je suis déja dehors me cherchez pas surtout... )


PS : Je sais quand même ce que c'est...

[Zorro]

un bon site pour verifier qu'un nombre est premier :
http://www.nombres-premiers.fr/1001797.html

[Ollivier]

Code : Tout sélectionner

;***************************************************************

Normal, je me goure de sigle, en me reportant à de vieilles documentations : je ne suis pas à la page!

Heureusement, fweil a évoqué le bon terme pour bien débuter l'étude des instructions à multiples opérandes. : AVX

A la base, une instruction ASM de calcul, c'est un seul calcul. Mais ça a évolué : une instruction de calcul SSE c'est quatre calculs simultanés.

Au lieu de faire juste x = (x - 1), certaines instructions permettent de faire :
x0 = (x0 - 1)
x1 = (x1 - 1)
x2 = (x2 - 1)
x3 = (x3 - 1)
... en une seule instruction.

Il me semble avoir posté un code qui mettait un texte en majuscule il y a 5 ou 6 ans avec ce genre d'instruction. Si tu peux me le retrouver, ce serait cool.

Aussi,

Code : Tout sélectionner

101010(1)010101010
210210(2)10210
432104(3)21043210
654321(0)6543210

n'est pas stockée dans ce sens mais dans ce sens :

Code : Tout sélectionner

1246
0135
1024
0213
1102
0041
----v---- 
1230
----v----
0126
1015
0204
1143 <<< 11ème ligne sans zéros
etc...

Le process prend les nombre 4 par 4 de haut en bas. On remarque qu'excepté l'intrus "un" (1), c'est la 11ème ligne qui ne contient pas de zéros (0). On peut donc conclure qu'avec 4 colonnes représentant les 4 premiers "nombres premiers" 2, 3, 5 et 7, on débusque le "nombre premier" qui les suit : 11 (onze).

Le process rajoutera alors une 5ème colonne pour permettre l'ajout de la suite :
10. 9. 8. 7. 6. 5. 4. 3. 2. 1. 0. 10. 9. 8. 7. 6. 5. 4. 3. 2. 1. 0. 10. 9. 8. 7. 6. 5. 4. 3. 2. 1. 0. etc...

et... Ainsi de suite!

Quand le nombre de colonnes n'est pas multiples de 4, par exemple avec la prise en compte du "11"

On va entrer, calculer et sortir, 8 nombres avec 3 inutilisés. :
(c2, c3, c5, c7) - (c11, 0, 0, 0)

On verra par la suite comment "anticiper" ces colonnes inutilisées.

a marche?!?

[Ollivier]

@SPH

J'ai trouvé mon sujet !
Exemple d'utilisation SSE : Mettre des minuscules en majuscule.

[fweil]

Ollivier,

Il me semble avoir bien compris ce que tu expliqes et j'ai l'impression que ça revient à faire ce que fait l'algo que j'ai proposé ? L'argumentation est équivalente si je ne me trompe pas :

Je prends une liste de nombres, admettons de 1 à 30 pour faire léger :

A B C D E F G
Liste états t0 t1 t2 t3 t4
Poids du
compteur 2 3 5 7
1 1 1 1 1 1
2 1 1 1 1 1
3 1 1 1 1 1
4 1 0 0 0 0
5 1 1 1 1 1
6 1 0 0 0 0
7 1 1 1 1 1
8 1 0 0 0 0
9 1 1 0 0 0
10 1 0 0 0 0
11 1 1 1 1 1
12 1 0 0 0 0
13 1 1 1 1 1
14 1 0 0 0 0
15 1 1 0 0 0
16 1 0 0 0 0
17 1 1 1 1 1
18 1 0 0 0 0
19 1 1 1 1 1
20 1 0 0 0 0
21 1 1 0 0 0
22 1 0 0 0 0
23 1 1 1 1 1
24 1 0 0 0 0
25 1 1 1 0 0
26 1 0 0 0 0
27 1 1 0 0 0
28 1 0 0 0 0
29 1 1 1 1 1
30 1 0 0 0 0

Voilà qui représente strictement le fonctionnement d'un crible d'Erathostène (j'espère que l'édition sort bien sur vos navigateurs ?).

J'ai bricolé ça dans Excel avec une formule générale pour les cellules d'état de la liste :

Cadré à partir de la ligne 1 d'une feuille, dans la cellule C3 on a : =SI($A3>C$2;SI(B3=1;SI(MOD($A3;C$2)=0;0;1);0);B3)

Et on fait copier / coller à droite et vers le bas pour tout le bloc.

La formule est pas pertinente pour faire un prog, mais pour Excel ça permet de bien voir le fonctionnement.

A partir de là je n'ai qu'une liste et je vais étape après étape cocher les les cellules multiples de ... 2 en premier, puis 3, puis 5 etc ... en cherchant les multiples des premiers inférieurs ou égaux à la racine de la valeur max de la plage.

Je me contrefiche de savoir ce qu'il y a dans une cellule, mais si je la pointe je mets un 0. Toutes les cellules étant à 1 au départ, ce qui restera en dernier ce seront les premiers (ça me rappelle quelque chose c'est bizarre ^^).

Comme la première étape est traitée en partant avec un pointeur qui saute de 2 en 2, elle me coûte n / 2 écritures à 0.

La seconde étape saute de 3 en 3, ça me coûte n / 3 écritures à 0 ...

Et quand j'aurai accompli n / 2 + n / 3 + n / 5 + n / 7 + n / 11 + n / 13 + n / 17 ..... écritures à 0 je n'aurai plus qu'à compter les zéros (ça c'est une poursuite triviale). A les compter, les imprimer ou mesurer les écarts, c'est un autre sujet. Appellons cette série N_OPER

L'intérêt de la chose c'est que j'ai une liste (tableau à une dimension) que je pointe N_OPER fois et je sais que N_OPER tend vers 3 et quelque chose lorsque n tend vers 1e18.

En fait ce calcul est une discussion autour de la série harmonique H(n) qui tend vers l'infini mais dont on peut obtenir une valeur intermédiaire pour un n donné, dont on démontre que sa valeur croit de Ln(10) quand n croît d'un facteur 10, et sur la série des inverses des nombres premiers qui tend vers Ln(H(n)) - Ln(2) ... qui croît donc aussi en Ln(10) quand n croît d'un facteur 10.

(faudra que je relise et corrige mes commentaires dans le code d'ailleurs qui doivent être un poil trop poétiques et hasardeux).

De fait, il me semble qu'il doit être assez poilu d'envisager une solution plus économique que celle que j'effectue et qui répond stricto-sensu au crible d'Erathostène, puisque je n'utilise qu'un pointeur dans un tableau à une dimension, que je marque uniquement les étapes de ce pointeur dans sa course respectivement pour chaque poids de compteur, les compteurs successifs étant les premiers potentiellement diviseurs entiers de la valeur courante de n.

Dans ton approche, Ollivier, tu envisages un deuxième tableau à une dimension pour gérer les compteurs, en fait, si je te comprends bien c'est de cela que tu parles.

Et dans le code que j'ai présenté, je construis avant de passer au crible, une table Primes() qui contient la liste des permiers jusqu'à sqr(n) !

Donc on a bien la même analyse ?

Et je pense que c'est la meilleure analyse possible pour un test de primalité performant correspondant à l'étude d'une portée longue (tout ceci ne se discute pas avec les mêmes arguments si le but est de tester la primalité d'une valeur n unique).

On a les clefs du problème bien posées, et on utilise une table unaire pour les entiers à tester et une seconde table unaire pour les diviseurs. Ces diviseurs sont limités à la portion congrue (premiers de 1 à sqr(n)). Et la table des entiers est parcourue avec la plus grande économie possible d'opérations.

Le problème posé au départ étant de tester la primalité des nombres exprimés en arithmétique entière sur 64 bits, pour simplifier jusqu'à 1e18 (oui bon on va dire ça comme ça), la portée de la seconde table est au maximum utile de 1e9 pour la valeur max (plus grand nombre premier servant de diviseur 1e9 = sqr(1e18)). Or la quantité de nombres premiers inférieurs ou égaux à 1e9 est de l'ordre de 1e9 / (Ln(1e9) - 1), ce qui représente un nombre ma fois compatible avec les ressources d'un PC. Cette valeur est voisine de 50M ... soit une table de premiers calculés et stockés pendant le calcul de 400MB en mémoire vive, ce qui est presque raisonnable, et uniquement nécessaire pour tester des nombres jusqu'à 1e18.

Voili, voilà ... et si je ne t'ai pas assez bien lu et compris, Ollivier, je ferai amende honorable très vite. Mais je crois bien qu'on voit les choses de la même manière.

Pour ce qui est des SIMD / AVX, je commence à reprendre un peu quelques tests de code FASM sous PureBasic avant de tenter quelque chose. J'ai besoin de vérifier différents aspects et les résultats effectifs en termes de performances et de gestion d'algorithme.

En fait ce que je ne sais pas certifier c'est la manière de bien agencer des instructions AVX pour être certain du nombre de cycles CPU qu'on obtient par instruction de calcul et par instructions de transfert mémoire / registres. Si j'arrive à prouver par des tests valables ce que je veux obtenir, je dois parvenir à injecter un bloc de 4 nombres di=(d1, d2, d3, d4) diviseurs d'un entier n et obtenir à l'étape suivante (nombre constant de cycles) les résultats de la division entière de n / di, ça c'est pour les modulos (puisque j'en utilise pour initialiser les compteurs du crible en début de page), d'une part, et d'autre part pour éventuellement améliorer, mais là je ne suis pas certain de mon coup, la partie crible elle-même.

J'imagine que si je me débrouille correctement je devrais pouvoir utiliser AVX pour faire avancer 4 compteurs en même temps, mais est-ce que le coût d'une séquence AVX ne va pas être prohibitif par rapport à une course de pointeur qui travaille de moins en moins au fur et à mesure que le compteur qu'il représente prend une valeur plus élevée ?

D'après quelques résultats que j'ai pu voir dans des échanges informels, parce que les gens donnent peu leurs preuves de recherche sur le sujet, les systèmes de calcul dits vectoriels (justement les clampins qui se sont paluchés des systèmes de test de primalité sur des calculateurs hypervitaminés en CPUs), les temps obtenus en quantités de premiers trouvés par unité de temps et par processeur sont pas vraiment top. Et mon but à moi est de permettre à des gens sur PC de faire le travail.

Si l'approche SoE (crible d'Erathostène) n'est pas probante pour le test de primalité, je ferai quand même un travail précis avec AVX pour démontrer l'intérêt de la vectorisation sur un test de primalité par divisions itératives. De fait j'ai déjà fait un bout de code dans lequel je vectorisais sur les diviseurs inférieurs à 256 sous forme de 8 diviseurs en parallèle sur des quads (64 bits = 8 x 8 bits), et ça je maîtrise bien la logique.

Mais je suis complètement tout vertaux idées, questions, suggestions et tout ce qu'on veut.

Ollivier, tu disais être intrigué par la question de la pagination des calculs ... c'est très simple et élémentaire en fait : si je dois traiter une plage 1-n, je la divise en en sous-plages, si possible de taille uniforme, et de manière à traiter les plages en continuité. J'obtiens un découpage 1_n1, n1+1_n2, n2+1_n3, .... np+1_n. Chaque plage peut-être traitée avec le crible sans faire de particularisme, à la seule condition d'initialiser les valeurs des compteurs correctement. Ca a fait l'objet d'une bonne prise de tête à l'origine, mais c'est simple.

Si je dois faire un crible avec des compteurs qui représentent l'état d'un pointeur de multiples de x, en partant sur la première page qui va de 1 à n1, mon compteur 5, par exemple, doit être initalisé de telle sorte qu'il ne marque pas 5, mais le premier multiple de 5 suivant, soit 2 x 5, et ensuite il est incrémenté du poids du compteur +5, et chaque case qu'il pointe est marquée pour annuler la propriété de candidat premier (en fait cela signifie que le nombre est composite). Ce compteur va faire avancer le pointeur jusqu'à atteindre la fin de la page, et on fait pareil pour tous les compteurs.

Lorsque je traite une page np+1_n, mon compteur 5 doit être initialisé de telle sorte qu'il apparaisse dans l'état où il serait si il avait avancé depuis le début de la plage (soit la valeur 1 par exemple). Pour cette page, mon début de comptage est fixé à la valeur np+1. La valeur du compteur 5 est (np+1) % 5 ... étonnant non ?

Et ça marche finement.

Au-delà de cette mécanique, le découpage en sous-plages (slices dans le programme) et en pages découle d'une logique plus proche du matériel utilisé. On doit s'arranger de toute évidence, et là c'est la pratique et l'expérience qui priment, pour obtenir des threads dans un nombre pertinent, qui vont être envoyés aux processeurs à une certaine candence, qui doivent permettre d'utiliser les ressources de manière sobre et efficace. Pour la sobriété de l'utilisation mémoire, on découpe les sous-plages en pages, et on fait en sorte que la taille de ces pages soient adaptées pour permettre au processeur de maximiser les échanges en mémoire cache ... sans avoir aucune maîtrise exacte de la chose. Mais de fait des pages trop grandes ralentissent considérablement le temps de calcul, ça je l'ai soigneusement vérifié. Donc j'en arrive à des pages du genre 100K mots de 64 bits qui me paraissent une bonne valeur repère. Et on met autant de pages que besoin dans une sous-plage, et autant de sous-plages que souhaité pour arbitrer correctement l'utilisation en multiprocesseur.

Sur le nombre de sous-plages (donc la liste des threads qui seront soumis aux processeurs), j'ai simplement remarqué que :

- un processeur est mieux utilisé si il a un thread en attente pendant qu'il en fait tourner un.
- un processeur est plus profitable au thread en cours sauf si il contient beaucoup de transferts externes (d'où une meilleure utilisation du processeur sur le thread en cours si il tourne comme un bourrin ssur des opérations registre / registre, le moins possible en échange mémoire / registre, et si c'est le cas autant que possible sur de la mémoire cache).
- un processeur adore avoir du boulot pour l'avenir (un thread en attente), et du coup il peut perdre un tout petit peu de souffle pour admirer ce qu'il aura à faire ensuite, il est donc préférable de ne pas lui en coller tout de suite pour trois siècles, sinon il va se croire titularisé et tourner à 32h par semaine (je plaisante).

L'arbitrage d'une file d'attente de threads pose deux problèmes: la file d'attente est bien gérée si les CPUs sont disponibles. Plus les CPUs sont occupés, moins la file est bien gérée, et plus sa gestion coûte. Plus les processeurs sont occupés, moins ils arrivent à désaturer la file. L'autre problème c'est qu'un thread représente un appel de ressources mémoire.

Dans mon programme, j'ai mis un mécanisme en place qui permet de limiter le nombre de threads en file d'attente de manière à ce que les CPUs supposent qu'il n'y a pas le feu au lac et qu'elles se contentent de faire dans l'industrie Shadock. Elles pompent, et elle voient que cela est bon.

Si le calcul a une grande portée (une plage très large de calcul), le nombre de thread monte, pour diviser le travail en lots raisonnablements petits. Mais les réglages que j'ai mis sont vraiment empiriques. Et lorsque je fais tourner le programme sur une machine j'ai certaines valeurs qui vont bien, et si je passe à une autre machine différente (en nombre de CPUs en taille de cache L1 / L2), les meilleures valeurs changent. Donc c'est un truc sur lequel je n'ai pas trouvé la panacée. Le mieux, si on doit se lancer dans un calcul de plusieurs jours / semaines ou mois CPU, c'est de faire quelques tests avec des plages réduites.

Pour vérifier mes réglages pour 1e15 (ce qui est une grande portée), je fais quelques tests sur des sous-plages genre 1e13 à 1e13+1e10, 1e14 à 1e14+1e10, 1e15 à 1e15+1e10. C'est assez rapide pour vérifier si la valeur des paramètres de taille min et max des pages et des sous-plages donne des résultats plutôt dans la moyenne ou pas.

Voilà pour les questions relatives au découpage. Ah oui, juste une virgule de plus sur ce point, puisque je cherche à trouver des écarts entre premiers, il faut juste penser à mémoriser les plus petit et plus grand premiers trouvés dans chaque page, pour pouvoir à la fin rapiécer (fusionner) le tout et ne pas oublier les écarts entre les pages, mais c'est un détail de finition.

[SPH]

Voici ce que j'ai pondu sur les nombres premiers il y a quelques annees (ca pourrait aider) :

Voici l'intégralité de ma réflexion qui apporte la preuve absolue que la lignée des Mersenne commencant a 2 est infinie !!


"LA CONJECTURE MAGNIFIQUE DE SPH"

Cette article parlera des nombres premiers et des nombres premiers de Mersenne.

Deux etant le seul chiffre pair premier, 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 (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 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 ADN vide 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 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=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 !
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 ?
OUI, et c'est même une CERTITUDE MATHEMATIQUE !
En voici la preuve :

Tous les cribleurs de mersenne criblent un 'n' multiple de 3.
23 [OOOOOXOOOOO] : Apres le crible de 2^11-1, on crible 2^33-1; 2^55-1; 2^77-1.....
31 [OOXOO] : Apres le crible de 2^5-1, on crible 2^15-1; 2^25-1; 2^35-1.....
47 [OOOOOOOOOOOXOOOOOOOOOOO] : Apres le crible de 2^23-1, on crible ici 2^69-1; 2^115-1; 2^161-1.....
Pourquoi écarter le premier crible me direz vous ?
En effet, pourquoi écarter 2^11-1 (pour le cribleur 23), 2^5-1 (pour le cribleur 31) et 2^23-1 (pour le cribleur 47) !!
Tout simplement parce que pour tester un éventuel mersenne premier de la lignée des mersenne de 2 (on va prendre par exemple le nombre 127), il faut cribler tous les nombres premiers cribleurs de mersenne jusqu'a la racine de 127. Hors, il n'y a que l'ADN de mersenne 7 pour voir si le 'X' de cet ADN crible 2^7-1 !
Regardons cela :
7[OXO] : 2^7-1 tombe sur le premier symbole !! 127 n'est donc pas criblé car le seul cribleur potentiel de 127.
Allons plus loin : peut il cribler le Mersenne de 127 ?????
Regardons où ce trouve 127 :
7[OXO] : 2^127-1 tombe encore sur le premier symbole !! LA BOUCLE EST BOUCLEE !!!!!!!
De tous les cribleurs de Mersenne, 7 etait le SEUL a pouvoir cribler 127.
Maintenant, si l'ADN de Mersenne de 127 ne crible pas 2^127-1 mais tombe sur le meme symbole, c'est que JAMAIS la lignée des mersennes qui a débuté à 2 ne pourra etre criblé :
127[OOOXOOO] BINGO !! 2^127-1 tombe aussi sur le premier symbole. DONC, comme pour son ainé '7' qui ne cesse de tomber sur le premier symbole, les suites tomberont aussi sur ce symbole qui ne crible pas !!!!!
La lignée des Mersenne Premiers ayant commencé par 2 est donc infinie !!
M(2)=3
M(3)=7
M(7)=127
M(127)=X
M(X)=Y
etc.......
J'ai donc trouvé des Mersennes avec un nombre de chiffre incommensurable !!!!!!!!

"FIN DE LA CONJECTURE MAGNIFIQUE DE SPH"


=====================


Prenez un mersenne a tester. Par exemple M(11)
Vous multipliez 11 par 2 et vous ajoutez 1. Cela donne 23. Si 23 est un nombre voisin de 8X, votre mersenne a pour cribleur la "branche des 2"; sinon, la "branche des 6" (je vais y revenir).
23 est voisin de 3*8=24 donc, les cribleurs de M(11) sont de la branche des 2.

Qu'est ce que ces histoires de branches ?
Les nombres sont a classer dans 4 branches :
8x+2 (conserne 50% des mersenne)
8x+4 (Inutile)
8x+6 (conserne 50% des mersenne)
8x+8 (conserne 100% des mersenne)

Voici les formules qui donnent les cribleurs d'un mersenne :
(8x+2)*np+1 et (8x+8)*np+1 : ces 2 branches concernent tous les mersennes issu de la branche des 2

Sinon :
(8x+6)*np+1 et (8x+8)*np+1 : ces 2 branches concernent tous les mersennes issu de la branche des 6

---

DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS :
DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS :
DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS : DERNIERE NEWS :

Il semblerait plus simplement qu'un mersenne non premier a pour facteur : 8x-1 et 8y+1

Pour tout M(m) non premier, il a pour facteur 2 nombres premiers; l'un de forme 8x-1 et l'autre de forme 8y+1. De plus, ces nombres premiers sont de forme mz+1.

exemple :
M(11) = 2047 = 23 * 89 = 11*2+1 * 11*8+1 = 3*8-1 * 11*8+1
M(23) = 8388607 = 47 * 178481 = 23*2+1 * 23*7760+1 = 6*8-1 * 22310*8+1
M(29) = 536870911 = 233 * 2304167 = 29*8+1 * 29*79454+1 = 288021*8-1 * 29*8+1
M(37) = 137438953471 = 223 * 616318177 = 37*6+1 * 37*16657248+1 = 28*8-1 * 77039772*8+1
M(41) = 2199023255551 = 13367 * 164511353 = 41*326+1 * 41*4012472+1 = 1671*8-1 * 20563919*8+1

Ces cribleurs de forme 8x-1 et 8y+1 que je nomme C- et C+ ont aussi une particularité.

Analyse de C- * C+ :
M(11) = 3*8-1 * 11*8+1 = 3C- * 11C+ => (3 * 11) Mod 11 = 0 => *3 => 3 Mod 3 = 0 => *1
M(23) = 6*8-1 * 22310*8+1 = 6C- * 22310C+ => (6 * 22310) Mod 23 = 0 => *5820 => 5820 Mod 3 = 0 => *1940
M(29) = 29*8+1 * 288021*8-1 = 288021C- * 29C+ => (29 * 288021) Mod 29 = 0 => *288021 => 288021 Mod 3 = 0 => *96007
M(37) = 28*8-1 * 77039772*8+1 = 28C- * 77039772C+ => (28 * 77039772) Mod 37 = 0 => *58300368 => 58300368 Mod 3 = 0 => *19433456
M(41) = 1671*8-1 * 20563919*8+1 = 1671C- * 20563919C+ => (1671 * 20563919) Mod 41 = 0 => *838105089 => 838105089 Mod 3 = 0 => *279368363

M(43) :
C+ = 2551071062
C- = 54
(C+ * C-) / 43 = 3203670636
3203670636 / 3 = 1067890212

M(47) :
C+ = 7482852422
C- = 294
(C+ * C-) / 47 = 46807630044
46807630044 / 3 = 15602543348

Analyse des facteurs :
M(11) = (3 * 11) = 3 * 11 = 11 * 3 = 33
M(23) = (6 * 22310) = 2*3 * 2*5*23*97 = 23 * 5820 = 133860
M(29) = (29 * 288021) = 29 * 3*19*31*163 = 29 * 288021 = 8352609
M(37) = (28 * 77039772) = 2*2*7 * 2*2*3*37*167*1039 = 37 * 58300368 = 2157113616
M(41) = (1671 * 20563919) = 3*557 * 41*59*8501 = 41 * 838105089 = 34362308649


Examen d'un nombre pour savoir s'il crible :
23 : milieu 12 => 1; 4; 16; 18; 3; 12; 2; 8; 9; 13; 6; 1 : len_ADN = 11
89 : milieu 45 => 1; 4; 16; 64; 78; 45; 2; 8; 32; 39; 67; 1 : Len_ADN 11
La longueur de l'ADN (11) indique que nos nombres (23 et 89) criblent M(11)
Donc, pour chercher qui crible N, il faut que (N+1)/2 tombe au milieu de l'ADN du nombre testé.
Pour 11, (N-1)/2 = 5
On fait 4^5 et on cherche un modulo :
4^5 Mod 23 = 12; soit (23+1)/2
4^5 Mod 89 = 45; soit (89+1)/2

Pour 23 :
(23-1)/2 = 11
4^11 Mod 47 = 24
4^11 Mod 178481 = 89241

Pour 47 :
(47-1)/2 = 23
4^23 Mod x = ((x+1)/2)
x = 2351

A congru B mod C = A-B multiple de C

===

M(NP) non premier si :
(C- * C+) Mod NP = 0

Poussons la réflexion plus loin :
M(NP) non premier (?) si :
(un quelconque C- * un quelconque C+) Mod NP = 0


pair*pair=pair
pair*impair=pair
impair*impair=impair

Donc, à priori, on a juste besoin de tous les C- et C+ impair qui finissent aussi par 5 !




*********

(ax-b)*(ay+b)= a²xy+abx-aby-b²
(8x-1)*(8y+1)= 8*8*xy + 8x - 8y - 1
x=3
y=11
(8*3-1)*(8*11+1)
8*8*3*11 + 8*3 - 8*11 - 1
64*33 + 24 - 88 -1
2112 -65
2047

=====================

Reflexion :
11 nC nM 37 nC nM 41 nC nM
(11-1)/2=5 np 18 nnp 20 nnp
11*2-1=21 nnp 73 np 81 nnp
11*2+1=23 np 75 nnp 83 np
23 = C- et pas M
89 = C+ et M

13 nC M 17 nC M 19 nC M 29 nC M
(13-1)/2=6 nnp 8 nnp 9 nnp 14 nnp
13*2-1=25 nnp 33 nnp 37 np 57 nnp
13*2+1=27 nnp 35 nnp 39 nnp 59 np


23 C M 31 C M
11 np 15 nnp
45 nnp 61 np
47 np 63 nnp


=====================

Sur 1908 Mersennes non premiers (exemple : 11),
506 finissent par 1 (26,51%)
269 finissent par 3 (14,09%)
562 finissent par 7 (29,45%)
543 finissent par 9 (28,45%)

Il semblerait que :
C+ ne peux pas finir pas 3 ou par 8
2711 nombres
168 fin 0 : 6.1969%
503 fin 1 : 18.5540%
177 fin 2 : 6.5289%
155 fin 4 : 5.7174%
500 fin 5 : 18.4433%
176 fin 6 : 6.4920%
529 fin 7 : 19.5130%
503 fin 9 : 18.5540%

C- ne peux pas finir par 2 ou par 7
16422 nombres
2040 fin 0 : 12.4223%
2068 fin 1 : 12.5928%
2036 fin 3 : 12.3980%
2068 fin 4 : 12.5928%
2057 fin 5 : 12.5258%
2053 fin 6 : 12.5015%
2051 fin 8 : 12.4893%
2049 fin 9 : 12.4771%

Un C+ ne finissant jamais par 3 et 8 ne peux pas se multiplier avec un C- ne finissant jamais par 2 et 7
liste des combinaisons impossible et analyse du chiffre de fin :
8*3+1 * 8*2-1 => fin 5
8*3+1 * 8*7-1 => fin 5
8*8+1 * 8*2-1 => fin 5
8*8+1 * 8*7-1 => fin 5
Les C+ finissant par 0; 2; 4 et 6 sont rare. Ils finissent par :
8*0+1 => fin 1
8*2+1 => fin 7
8*4+1 => fin 3
8*6+1 => fin 9
Les C+ finissant par 1; 5; 7 et 9 sont courants. Ils finissent par :
8*1+1 => fin 9
8*5+1 => fin 1
8*7+1 => fin 7
8*9+1 => fin 3



=====================

M(2) = 3 = 2^1 + 1
M(3) = 7 = 2^2 + 3 * 1
M(4) = 15 = 2^3 + 7
M(5) = 31 = 2^4 + 3 * 5
M(6) = 63 = 2^5 + 31
M(7) = 127 = 2^6 + 3 * 3 * 7
M(8) = 255 = 2^7 + 127
M(9) = 511 = 2^8 + 3 * 5 * 17
M(10) = 1023 = 2^9 + 7 * 73
M(11) = 2047 = 2^10 + 3 * 11 * 31
M(12) = 4095 = 2^11 + 23 * 89
M(13) = 8191 = 2^12 + 3 * 3 * 5 * 7 * 13
M(14) = 16383 = 2^13 + 8191
M(15) = 32767 = 2^14 + 3 * 43 * 127
M(16) = 65535 = 2^15 + 7 * 31 * 151
M(17) = 131071 = 2^16 + 3 * 5 * 17 * 257
M(18) = 262143 = 2^17 + 131071
M(19) = 524287 = 2^18 + 3 * 3 * 3 * 7 * 19 * 73
M(20) = 1048575 = 2^19 + 524287
M(21) = 2097151 = 2^20 + 3 * 5 * 5 * 11 * 31 * 41
M(22) = 4194303 = 2^21 + 7 * 7 * 127 * 337
M(23) = 8388607 = 2^22 + 3 * 23 * 89 * 683
M(24) = 16777215 = 2^23 + 47 * 178481
M(25) = 33554431 = 2^24 + 3 * 3 * 5 * 7 * 13 * 17 * 241
M(26) = 67108863 = 2^25 + 31 * 601 * 1801
M(27) = 134217727 = 2^26 + 3 * 2731 * 8191
M(28) = 268435455 = 2^27 + 7 * 73 * 262657
M(29) = 536870911 = 2^28 + 3 * 5 * 29 * 43 * 113 * 127
M(30) = 1073741823 = 2^29 + 233 * 1103 * 2089
M(31) = 2147483647 = 2^30 + 3 * 3 * 7 * 11 * 31 * 151 * 331
M(32) = 4294967295 = 2^31 + 2147483647
M(33) = 8589934591 = 2^32 + 3 * 5 * 17 * 257 * 65537
M(34) = 17179869183 = 2^33 + 7 * 23 * 89 * 599479
M(35) = 34359738367 = 2^34 + 3 * 43691 * 131071
M(36) = 68719476735 = 2^35 + 31 * 71 * 127 * 122921
M(37) = 137438953471 = 2^36 + 3 * 3 * 3 * 5 * 7 * 13 * 19 * 37 * 73 * 109
M(38) = 274877906943 = 2^37 + 223 * 616318177
M(39) = 549755813887 = 2^38 + 3 * 174763 * 524287
M(40) = 1099511627775 = 2^39 + 7 * 79 * 8191 * 121369
M(41) = 2199023255551 = 2^40 + 3 * 5 * 5 * 11 * 17 * 31 * 41 * 61681
M(42) = 4398046511103 = 2^41 + 13367 * 164511353
M(43) = 8796093022207 = 2^42 + 3 * 3 * 7 * 7 * 43 * 127 * 337 * 5419
M(44) = 17592186044415 = 2^43 + 431 * 9719 * 2099863
M(45) = 35184372088831 = 2^44 + 3 * 5 * 23 * 89 * 397 * 683 * 2113
M(46) = 70368744177663 = 2^45 + 7 * 31 * 73 * 151 * 631 * 23311
M(47) = 140737488355327 = 2^46 + 3 * 47 * 178481 * 2796203
M(48) = 281474976710655 = 2^47 + 2351 * 4513 * 13264529
M(49) = 562949953421311 = 2^48 + 3 * 3 * 5 * 7 * 13 * 17 * 97 * 241 * 257 * 673
M(50) = 1125899906842623 = 2^49 + 127 * 4432676798593
M(51) = 2251799813685247 = 2^50 + 3 * 11 * 31 * 251 * 601 * 1801 * 4051
M(52) = 4503599627370495 = 2^51 + 7 * 103 * 2143 * 11119 * 131071
M(53) = 9007199254740991 = 2^52 + 3 * 5 * 53 * 157 * 1613 * 2731 * 8191
M(54) = 18014398509481983 = 2^53 + 6361 * 69431 * 20394401
M(55) = 36028797018963967 = 2^54 + 3 * 3 * 3 * 3 * 7 * 19 * 73 * 87211 * 262657
M(56) = 72057594037927935 = 2^55 + 23 * 31 * 89 * 881 * 3191 * 201961
M(57) = 144115188075855871 = 2^56 + 3 * 5 * 17 * 29 * 43 * 113 * 127 * 15790321
M(58) = 288230376151711743 = 2^57 + 7 * 32377 * 524287 * 1212847
M(59) = 576460752303423487 = 2^58 + 3 * 59 * 233 * 1103 * 2089 * 3033169
M(60) = 1152921504606846975 = 2^59 + 179951 * 3203431780337
M(61) = 2305843009213693951 = 2^60 + 3 * 3 * 5 * 5 * 7 * 11 * 13 * 31 * 41 * 61 * 151 * 331 * 1321
M(62) = 4611686018427387903 = 2^61 + 2305843009213693951


==============

(21:35) gp > 2/2
%50 = 1
(21:35) gp > 6/3
%51 = 2
(21:35) gp > 14/4
%52 = 7/2
(21:36) gp > 30/5
%53 = 6
(21:36) gp > 62/6
%54 = 31/3
(21:36) gp > 126/7
%55 = 18
(21:36) gp > 254/8
%56 = 127/4
(21:36) gp > 510/9
%57 = 170/3
(21:36) gp > 1022/10
%58 = 511/5
(21:37) gp > 2046/11
%59 = 186
(21:37) gp > 4094/12
%60 = 2047/6
(21:37) gp > 8190/13
%61 = 630
(21:37) gp > 16382/14
%62 = 8191/7
(21:37) gp > 32766/15
%63 = 10922/5
(21:38) gp > 65534/16
%64 = 32767/8
(21:38) gp > 131070/17
%65 = 7710
(21:38) gp > 262142/18
%66 = 131071/9
(21:39) gp > 524286/19
%67 = 27594
(21:39) gp >

==============

(21:45) gp > (2^2-2)/2
%73 = 1
1
(21:46) gp > (2^3-2)/3
%74 = 2
2
(21:46) gp > (2^5-2)/5
%75 = 6
2*3
(21:46) gp > (2^7-2)/7
%76 = 18
2*3*3
(21:46) gp > (2^11-2)/11
%77 = 186
2*3*31
(21:46) gp > (2^13-2)/13
%78 = 630
2*3*3*5*7
(21:46) gp > (2^17-2)/17
%79 = 7710
2*3*5*257
(21:47) gp > (2^19-2)/19
%80 = 27594
2*3*3*3*7*73
(21:47) gp > (2^23-2)/23
%81 = 364722
2*3*89*683
(21:47) gp > (2^29-2)/29
%82 = 18512790
(21:47) gp > (2^31-2)/31
%83 = 69273666
(21:47) gp > (2^37-2)/37
%84 = 3714566310
(21:47) gp > (2^41-2)/41
%85 = 53634713550
(21:48) gp > (2^43-2)/43
%87 = 204560302842
(21:48) gp > (2^47-2)/47
%88 = 2994414645858
(21:48) gp > (2^53-2)/53
%89 = 169947155749830
(21:49) gp > (2^59-2)/59
%90 = 9770521225481754
(21:49) gp > (2^61-2)/61
%91 = 37800705069076950
(21:49) gp >

=========


3^x en binaire :

1
11
1001
11011
1010001
11110011
1011011001
100010001011
1100110100001
100110011100011
1110011010101001
101011001111111011
10000001101111110001
110000101001111010011
10010001111101101111001
110110101111001001101011
10100100001101011101000001
111101100101000010111000011
10111000101111001000101001001
1000101010001101011001111011011

==================

----------

[Ollivier]

Il faut que je pionce une ou deux heures, sinon il va me rester des séquelles...

[fweil]

Je vais reprendre tout ça au calme, là je suis pas au calme. Pour l'utilisation des nombres de Mersenne, mon mathématicien commanditaire m'a dit, "mais pourquoi tu regardes pas les nombres de Mersenne ?".

J'ai regardé, mais je lui ai répondu que dans un premier temps il était fondamental d'être meilleur que les meilleurs sur le crible de base (Erathostène), et qu'ensuite ... j'y viendrai.

Donc, poussé par la horde des contemplateurs de la nature des nombres, je vais y venir.

Et ça me fait bien plaisir de ne pas me sentir tout seul à cogiter sur tout ça.

Merci à vous.

Au passage, j'ai commencé à poser quelques base pour les instructions AVX. Ce que j'aimerai c'est avoir tout compris dans les jours qui viennent. Comment faire une boite en AVX, si possible en tapant les registres Z (512 bits), dans laquelle injecter 8 quads et faire des choses en parallèle. Un des soucis qu'il y a est de transcender le fait que AVX raisonne plutôt en flottants qu'en entiers et que le coût de transformation est pas forcément bon marché.

Mais j'y réfléchis.

[fweil]

Ah voilà quelque chose qui commence à me causer bien :

Code : Tout sélectionner

Structure PACKED4D
  d0.d
  d1.d
  d2.d
  d3.d
EndStructure

Structure PACKED8D
  D4_0.PACKED4D
  D4_1.PACKED4D
EndStructure

  packed_in.PACKED8D
  packed_in\D4_0\d0 = 2
  packed_in\D4_0\d1 = 3
  packed_in\D4_0\d2 = 5
  packed_in\D4_0\d3 = 7
  packed_in\D4_1\d0 = 11
  packed_in\D4_1\d1 = 13
  packed_in\D4_1\d2 = 17
  packed_in\D4_1\d3 = 19
  *packed_in = @packed_in
  packed_out.PACKED8D
  *packed_out = @packed_out
  !  mov     rax, [p_packed_in]
  !  mov     rbx, [p_packed_out]
  !  vmovupd ymm0, [rax]
  !  vmovupd ymm1, [rax+32]
  !  vmulpd  ymm0, ymm0, ymm1
  !  vmovupd yword [rbx], ymm0
  !  vmovupd yword [rbx+32], ymm1
  
  Debug packed_out\D4_0\d0
  Debug packed_out\D4_0\d1
  Debug packed_out\D4_0\d2
  Debug packed_out\D4_0\d3
  Debug packed_out\D4_1\d0
  Debug packed_out\D4_1\d1
  Debug packed_out\D4_1\d2
  Debug packed_out\D4_1\d3
  
  CallDebugger
  
End

[Ollivier]

@SPH

Ton idée permet d'augmenter les chances de trouver si un très grand nombre est premier ou non.

Mais sur le principe de vérifier la plus grande quantité de nombres possiblement premiers consécutifs commençant par deux, ça n'est pas encore au point concrètement.

@fweil

Je suis bien content que tu trouves les points communs au crible d'Erathostène dans mes explications.
Bien content aussi de te voir évoquer le traitement des 512 bits. Cependant, je trouve judicieux de commencer par le traitement des 128 bits : c'est plus pédagogique et moins acrobatique !

Je suis désolé d'avoir manqué de transition entre ton algo qui use du SoE au sens strict du terme, et mon explication qui use un "négatif" du SoE. L'explication suivante, qu'il est évidemment possible de remettre en cause (j'en serai évidemment heureux) est que je me contrains à l'électronique : trouver l'inexistence d'un zéro (0) dans un bloc mémoire hors cache, si l'on néglige la poignée d'instrucrions machine de réglages préalables, ça se fait en une seule instruction : http://www.purebasic.fr/french/viewtopi ... =6&t=16276.

Il me vient un doute concernant la recherche des facteurs premiers : tu souhaites aussi ça, ou bien juste chercher les nombres premiers? Moi, je me focalise juste sur la recherche des nombres premiers, on est d'accord?

Je ne suis pas loin d'achever mon code explicatif pour Ar-S. Avec l'idée que cela va permettre de facilliter nos échanges d'explications...

[fweil]

@Ollivier, les composites ne sont pas dans mon champ d'étude. Ce sera peut-être le cas plus tard, mais là je veux juste me concentrer sur le test de primalité applicable sur des portées longues (plages d'analyse et non pas test sur un nombre aussi grand soit-il).

Le raisonnement auquel je me tiens consiste à trouver la meilleure manière, en faisant feu de tout bois, de tester la primalité vérifiée d'une plage de nombres entiers. Le test certifiant, est un test qui garantit que toutes les possibilités de diviseurs entiers ont été testées (ou à défaut que l'on a trouvé au moins un diviseur entier non 1 et inférieur à la valeur testée).

L'objectif concret est de parvenir à résoudre des plages jusqu'à 1e15 ou 1e16 dans un temps humain raisonnable, quitte à utiliser un nombre (raisonnable) de PC supérieur à 1, et en tout cas en s'assurant qu'on est capable quand on peut de solliciter au maximum les CPUs multiples d'une même machine (ce qui ajouté fait du calcul distribué, et du calcul multithread).

Et mon point de repère actuel en termes de performances est de faire tomber 1e12 en moins d'une heure sur un PC 4core 2,8GHz (repère déjà sensiblement dépassé aujourd'hui). La prochaine étape en ajoutant de la vectorisation de calcul serait d'arriver à tomber 1e13 en 2 ou 3h sur une machine de même niveau. Il peut aussi exister une étape supplémentaire ou divergente en regardant du côté des GPU, mais j'en suis pas encore là.

[Ollivier]

Hier soir, j'ai lu vos 2 messages (environ 1/4 d'heure chacun) et ça m'a mis une double baffe assez conséquente. Je dois avouer que j'ai vraiment bien dormi.

Bon, ben c'est une bonne nouvelle si l'on se tient aux seuls premiers.

En effet, le SoE regroupe tout : premiers et facteurs premiers avec leur puissance respective. Moi, j'ai négligé cette 2ème partie. C'est-à-dire que je m'en suis tenu au repère des premiers du SoE, et je me suis dit "quand la colonne en cours du SoE est achevée, quelle routine ASM est la mieux adaptée pour savoir si cette colonne révèle un nb 1er?"

Ma réponse technique fut celle-ci : compter une unité (un octet = 1, un mot = 1, un double-mot = 1, etc... je considère que ce sont des unités, qu'importe la taille en bits) et vérifier que le résultat du comptage vaut 1 est plus long à exécuter en temps processeur que de vérifier l'inexistence d'un 0 (une unité = 0) dans une plage mémoire fixée à la volée.

Je peux me tromper évidemment, par une mauvaise compréhension de ton algo, notamment. Cependant, comme cet routine ASM est là (j'ai mis le lien), et comme tu as déjà étudié pas mal de durées d'exécution, est-ce que tu peux vérifier que cette instruction est convenable en terme de rapidité?
C'est "REP SCASQ", j'en ai fait un ensemble de macros dans "Trucs et astuces" sous les noms de FindMemory...(). C'est déjà préréglé pour être prêt-à-l'emploi.

Et c'est la raison pour laquelle, j'ai pris le problème à l'envers en utilisant un "négatif" du SoE qui néglige les puissances des diviseurs premiers, plutôt que le SoE "normal".

Dans un SoE normal, les diviseurs sont à zéro quand le nombre est premier. Dans un des "négatif" du SoE (ce que j'ai appelé maladroitement un "anti-crible"), celui que je décris dans ce sujet, au contraire, tous les diviseurs sont déclarés non nuls dans la colonne d'un nombre premier. Là encore, c'est par contrainte électronique que j'utilise cette astuce, car l'algo SSE ne fait que des soustractions (pas de calculs de type multiplication, division ou modulo).

Mon algo principal alterne (1:) soustractions et (2:) recherche d'absence de zéros, avec (3:) prise en charge de la mise à jour le cas échéant.

Je vais vérifier (comme toi) si la décrémentation SSE existe (normalement oui). Dans, ce cas probable, ce sont 3 étapes extrêmement bien appréhendées par l'électronique (peu de cycles), et ça laisse la place à une optimisation mathématiques dont la limite n'a d'importance que via la mémoire de masse disponible (moi, j'opterai pour une moyenne de 200 giga de pré-calcul, je pense que ton problème à venir va être la transmission de données !)

Franchement, on parle d'un sujet qui nécessite une concentration impressionnante pour comprendre et se faire comprendre ! Mais je ne doute pas que nous ne parvenions pas à des résultats surprenants!