Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
139 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Crible nombres premiers

Envoyé par Julien vivier 
Crible nombres premiers
il y a six mois
Bonjour
Je me pose une question, j'ai eu une idée de crible. À la manière du crible d’Ératosthène, il permet d'éliminer les nombres non premiers.

Je me doute que ça doit déjà exister, mais je ne trouve nul part sur le net mention de ce crible.
Est-ce que quelqu'un a déjà vu un crible de ce genre.
Mon idée est développée dans le PDF ci-joint.
Merci pour le temps que vous me consacrerez.

PS : je m'excuse d'avance si je pose une question déjà posée mille fois.
Julien V



Edité 1 fois. La dernière correction date de il y a six mois et a été effectuée par AD.
Pièces jointes:
ouvrir | télécharger - formule nombres premiers 2.pdf (1.4 MB)
Re: Crible nombres premiers
il y a six mois
J'ai l'impression que c'est juste une illustration visuelle du fait que $n$ est premier si et seulement s'il n'a aucun diviseur premier strictement plus petit que lui-même.

Pour comparaison, le crible d'Ératosthène développe la même idée, mais en se restreignant aux premiers plus petit que la racine de $n$.



Edité 1 fois. La dernière correction date de il y a six mois et a été effectuée par Poirot.
Re: Crible nombres premiers
il y a six mois
Merci pour la réponse.
je n'ai pas l'impression que le crible d'Eratostène permet de faire simplement les prédictions suivantes :

2*3*5*7=210 donc sur les 20 nombres qui entourent 210 seuls 2 peuvent être premier 209 et 211

2*3*7=42 donc sur les 20 nombres qui entourent 42 seuls 4 peuvent être premiers 41, 43, 47 et 37

cordialement,

Julien V
Re: Crible nombres premiers
il y a six mois
Le crible d'Eratostène ne permet pas de faire des prédictions ; il permet d'affirmer des vérités. C'est quand même beaucoup mieux, non ? Le crible d'Eratostène a 2 gros avantages sur ta méthode :
- le crible d'Eratostène est plus simple.
- il est plus efficace, puisqu'il conduit à des conclusions certaines, alors que ton outil conduit à des suppositions.

En plus, tu réduis l'efficacité de ton outil ... sans raison.
Prenons par exemple 630 = 2*3²*5*7. 630 étant un multiple de 2, 3, 5 et 7, on sait que tous les nombres de la forme 630+2k ou 630+3k ou 630+5k ou 630+7k ne peuvent pas être premiers. C'est l'idée même du Crible d'Eratostène. Donc parmi les 100 nombres entre 631 et 730, les seuls qui peuvent être premiers sont 631 641 643 647 649 653 659 661 667 671 673 677 683 ...
Je ne sais pas pourquoi tu restreins l'idée aux nombres de la forme 2*3*5*7 ... ( en retirant donc 2*3²*5*7 ou 2*3*5²*7 ou 2²*3²*5*7² ... ) ni pourquoi tu te restreins aux 20 nombres qui précèdent ou qui suivent ton nombre 2*3*5*7.

Pour moi, la vraie question intéressante est : quel est ton âge. Si tu es au collège, c'est un beau travail, c'est bien, continue à t'intéresser à ces questions. Mais si tu es plus âgé, alors pose toi les bonnes questions.
Re: Crible nombres premiers
il y a six mois
D'accord Lourran j'ai compris, je ne suis pas fait pour les maths, je n'y toucherai plus, c'est promis winking smiley

Malgré tout, merci pour les remarques constructives que tu as fait.

Il est effectivement possible que je me sois perdu à courir après des chimères.
Re: Crible nombres premiers
il y a six mois
Bonjour Julien,

Ce n'est pas parce que tu as une idée de recherche que tu cours après une chimère.
On ne trouve pas d'emblée tout de suite.
Ce qui compte n'est pas forcément de comparer ce qu'on fait à des critères de rapidité ou d'efficacité.
Le meilleur, c'est de trouver des rapports nouveaux entre les nombres : tu ne peux faire de la recherche et de
l'applicatif en même temps.

Dans ta primorielle 2x3x5x7, tu dis avoir éliminé 5 pour trouver 42 = 2x3x7
et dans 42 + 10 et 42 - 10 seuls 42 - 1 , 42 + 1 , 42 -5 et 42 + 5 peuvent être premiers.
( Et ils le sont : 41 , 43 , 37 et 47 ).

Réécris :

2x3x7 + 5 = 47 et, pourquoi se restreindre, porte 5 à la puissance
2x3x7 + 5x5 = 67 (premier ) => arrives-tu à expliquer cela dans tes portions de cercles en rotation ?
2x3x7 + 5x5x5 = 167 ( premier )

2x3x7 - 5 = 37 ( premier )
2x3x7 - 5x5 = 17 ( premier )
[ 2x3x7 - 5x5x5 ] = [ - 83 ] = 83 ( premier ) , les crochets [ ] sont le signe de la valeur absolue

Dans ta primorielle de 7, 2x3x5x7, tu as retiré le facteur 5. Soit. Retire le facteur 7 plutôt que le facteur 5 et oublie tes
10 entiers avant ou après 30 = 2x3x5 mais redis que 30 - 1 , 30 + 1 , 30 - 7 et 30 + 7 peuvent être premiers.
( Et ils le sont : 29 , 31 , 23 et 37 ) et porte le facteur 7 à la puissance.

2x3x5 + 7x7 = 79 ( premier ) => arrives-tu à expliquer cela dans tes portions de cercles en rotation ?
2x3x5 + 7x7x7 = 373 ( premier )

[ 2x3x5 - 7x7 ] = [ - 19 ] = 19 ( premier )
[ 2x3x5 - 7x7x7 ] = [ - 313 ] = 313 ( premier )

Etudions ta primorielle de 7 privée du facteur 3 => 2x5x7 = 70 ( là, on ne soustrait pas 1, car 70 est de la forme 3k + 1 et 70 - 1 serait un multiple de 3 ), mais 70 + 1 , 70 + 3 et 70 - 3 peuvent être premiers.
( Et ils le sont : 71 , 73 et 67 ). Porte le facteur 3 à la puissance.

2x5x7 + 3x3 = 79 ( premier ) => il faudrait que tu arrives à expliquer cela avec tes portions de cercles en rotation.
2x5x7 + 3x3x3 = 97 ( premier )
2x5x7 + 3x3x3x3 = 151 ( premier )

2x5x7 - 3x3 = 61 ( premier )
2x5x7 - 3x3x3 = 43 ( premier )
[ 2x5x7 - 3x3x3x3 ] = [ - 11 ] ( premier )

Etudions ta primorielle de 7 privée du facteur 2 => 3x5x7 = 105. 105 - 2 et 105 + 2 peuvent être premiers.
( Et ils le sont : 103 et 107 ) P£orte le facteur 2 à la puissance.

3x5x7 + 2x2 = 109 ( premier )
3x5x7 + 2x2x2 = 113 ( premier )
3x5x7 + 2x2x2x2 = 121 = 11x11 composé => ça serait super que tu l'expliques avec tes portions de cercles en rotation.
3x5x7 + 2x2x2x2x2 = 137 ( premier )
3x5x7 + 2x2x2x2x2x2 = 169 = 13x13 composé ( à expliquer )

3x5x7 - 2x2 = 101 ( premier )
3x5x7 - 2x2x2 = 97 ( premier )
3x5x7 - 2x2x2x2 = 89 ( premier )
3x5x7 - 2x2x2x2x2 = 73 ( premier )
3x5x7 - 2x2x2x2x2x2 = 41 ( premier )
[ 3x5x7 - 2x2x2x2x2x2x2 ] = [ - 23 ] = 23 ( premier )
[ 3x5x7 - 2x2x2x2x2x2x2x2 ] = [ - 151 ] ( premier )
[ 3x5x7 - 2x2x2x2x2x2x2x2x2 ] = [ - 407 ] = 407 = 11x37 composé ( nous verrons plus bas ce qu'il faut en dire )

Tu as étudié avec tes portions de cercles en rotation la factorielle de 7 => 2x3x5x7, mais tu aurais pu débuter par
celle de 5 => 2x3x5 = 30 en retirant 3 , 5 ou 2.

Je développe en commençant par retirer 5. 2x3 - 1 , 6 + 1 , 6 - 5 et 6 + 5 peuvent être premiers.
( Et ils le sont : 5 , 7 , 1 et 11 ) 1 est accepté premier, car il n'est pas un nombre composé. On porte 5 à la puissance.

2x3 + 5x5 = 31 ( premier )
2x3 + 5x5x5 = 131 ( premier )
2x3 + 5x5x5x5 = 631 ( premier )
2x3 + 5x5x5x5x5 = 3.131 = 31x101 composé ( voir plus bas )

[ 2x3 - 5x5 ] = [ - 19 ] = 19 premier
[ 2x3 - 5x5x5 ] = [ - 119 ] = 119 = 7x17 composé ( voir plus bas )

Gardons la primorielle de 5 = 2x3x5, en retirant 3 ( pas question de soustraire 1, car 10 est de la forme 3k + 1 ).
Donc, 2x5 + 1 , 10 - 3 et 10 + 3 peuvent être premiers.
( Et ils le sont. ) Portons 3 à la puissance.

2x5 + 3x3 = 19 ( premier )
2x5 + 3x3x3 = 37 ( premier )
2x5 + 3x3x3x3 = 91 = 7x13 ( à voir )

2x5- 3x3 = 1 ( accepté premier )
[ 2x5 - 3x3x3 ] = [ - 17 ] = 17 ( premier )
[ 2x5 - 3x3x3x3 ] = [ - 71 ] = 71 ( premier )

Primorielle de 5 en retirant 2. 3x5 = 15. 15 - 2 et 15 + 2 peuvent être premiers.
( Et ils le sont : 13 et 17 ). Portons 2 à la puissance.

3x5 + 2x2 = 19 ( premier )
3x5 + 2x2x2 = 23 ( premier )
3x5 + 2x2x2x2 = 31 ( premier )
3x5 + 2x2x2x2x2 = 47 ( premier )
3x5 + 2x2x2x2x2x2 = 79 ( premier )
3x5 + 2x2x2x2x2x2x2 = 143 = 11x13 composé ( à voir )

3x5 - 2x2 = 11 ( premier )
3x5 - 2x2x2 = 7 ( premier )
[ 3x5 - 2x2x2x2 ] = [ - 1 ] = 1 ( accepté premier )
[ 3x5 - 2x2x2x2x2 ] = [ - 17 ] = 17 ( premier )
[ 3x5 - 2x2x2x2x2x2 ] = [ - 49 ] = 49 = 7x7 composé ( à voir ).

Julien, il faut que tu trouves pourquoi les rotations de tes cercles concentriques donnent par fois des nombres composés.

Tu ne travailles pas pour rien. Avec tes portions de cercles concentriques, dont le fonctionnement est pour toi un crible, tu es peut-être en train d'illustrer le fonctionnement de mon premier théorème de génération de nombres premiers.

Sa description se trouve dans mon article Nouveau crible de nombres premier ( SHTAM page 3 ) à la dernière page, la page 6.

La grande ressemblance avec ton fonctionnement est la suivante :

Toi, tu prends une primorielle de 7 par exemple, 2x3x5x7,
moi je prends la suite S4 des 4 premiers nombres premiers, S4 = ( 2, 3, 5, 7 ) et si 7 = p, je nomme p' le nombre premier immédiatement supérieur à p ( ici, p' = 11 ).

Les nombres de S4 sont répartis dans un doublet A et B de telle sorte que A et B soient premiers entre eux.
Prenons A = 3x5x7 et B = 2
Pour [ A +/- B ] le premier nombre composé possible est 11m et m ne peut être égal ni à 2, ni à 3, ni à 5, ni à 7, donc sa
première valeur possible est 11 => 11m = 11x11 = 11² ou p'²

Théorème : les valeurs du doublet [ A +/- B ] sont obligatoirement des nombres premiers s'ils sont strictement inférieurs à p'².

Nous avons développé plus haut :

3x5x7 + 2 = 107 premier car < 11² = 121
...
3x5x7 + 2x2x2x2 = 105 + 16 = 121 composé = 11² = p'² manque de chance, on tombe pile sur la borne.

Pour les valeurs q = [ A +/- B ], telles que q sont supérieures à p'², q peut être soit premier, soit composé.

Julien, tu as choisi de retirer 5 de ta primorielle de 7 donnant ainsi

2x3x7 +/- 5 <= je t'ai dit que tu pouvais porter 5 à la puissance, mais tu peux le faire pour 2, 3 et 7.

[ 2x2x2x3x7 +/- 5x5x5 ] donne

168 + 125 = 293 ( on ne peut rien affirmer avec certitude, car 293 >11², mais il est premier.

168 - 125 = 43 premier car < 11²

Je ne sais comment fonctionnent tes rotations pour ces cas => c'est ce qu'il te faut étudier.

Pour ta primorielle de 7, tu aurais pu retirer 5 et 7 donnant ainsi 2x3 - 1, 6 +1, 6 + 5x7 et [ 6 - 35 ] peuvent être premiers.
( Et ils le sont : 5, 7, 41 et 29 ). Pour la mise en puissance :

2x2x3x3 + 5x7 = 36 + 35 = 71 premier car < 11²
etc...

Julien, je vois dans ton crible peut-être le détail du fonctionnement de mon théorème de génération de nombres premiers : il y a de la ressemblance dans tes expressions et dans les miennes.

C'est passionnant, je t'encourage vivement à continuer à chercher.

Bon travail !

Gonzague de VILLEMAGNE
Re: Crible nombres premiers
il y a six mois
Tout ça se résume de la façon suivante :
On prend un nombre P qui n'a comme diviseurs premiers que a,b,c,d...
On prend un autre nombre Q, qui n'a comme diviseurs premiers que e,f,g,h ...
On s'assure qu'il n'y a aucun nombre commun entre a,b,c,d.... et e,f,g,h ...
Alors, on a la certitude que P+Q ne sera divisible par aucun des nombres a,b,c,d.... , ni e,f,g,h ....
Et idem P-Q.

Démontrer cette propriété, ça ferait un exercice faisable par un lycéen.

Par exemple, on a l'assurance que $3^7*11*13^3*19*101^4 + 2^5*5*7*17*23^4 $ n'est divisible ni par 2, ni par 3, ni par 5, ni par 7, ni par 11, ni par 13, ni par 17, ni par 19, ni par 23 ni par 101.

Mais ce nombre est peut-être divisible par 29, ou 31 ...
Re: Crible nombres premiers
il y a six mois
Bonjour Lourrran,

Tu résumes un peu vite, sans t'attacher aux conditions du théorème : tu dis quelque chose qui n'est pas faux,
mais non dans l'esprit de celui-ci.

Je te reprends :

On prend une suite Sn des n premiers nombres premiers,
par exemple,
S5 = ( 2, 3, 5, 7, 11 )
On nomme p le plus grand nombres premier de cette suite ascendante et saturée,
et p' le nombre immédiatement supérieur à p.
Ici p = 11 et p' = 13

Choisissons P et Q doublet dans lequel on distribuera, en les multipliant entre eux, les n nombres premiers de la suite Sn de sorte que P et
Q soient premiers entre eux.

Par exemple :
P = 2x3x11
Q = 5x7

q = [ P +/- Q ] = 2x3x11 +/- 5x7

q1 = 66 + 35 = 101 < p'² = 13² = 169 => 101 est premier puisqu'il ne peut être multiple de 2, 3, 5, 7 ou 11

tout au mieux, le premier nombre composé ( non multiple de 2, 3, 5, 7 ou 11 ) est p'.m et m non multiple de 2, 3, 5,
7 ou 11 => ce premier nombre composé ne peut que valoir p'.p' = p'², ici 13²

Le théorème dit que q = [ P +/- Q ], selon les conditions énoncées ci-dessus, ne peut pas donner de nombres composés si q < p'²
Autrement dit, les valeurs ainsi trouvées sont des nombres premiers.

Il est possible que q excède p'² => il est alors soit premier, soit composé, mais on n'a pas de certitude.

Ce théorème de génération de nombres premiers met en relation particulière les premiers nombres premiers avec
d'autres qui leurs sont supérieurs, mais dans une certaine limite.

S1 = ( 2 ) et p' = 3 => q = [ P +/- Q ] criblera pour ] 2 , 3²-1 ].......( ici P = 2 et Q = 1 )

2 + 1 = 3
2 - 1 = 1
2x2 + 1 = 5
2x2 - 1 = 3
2x2x2 - 1 = 7
2x2x2x2 + 1 = 9 = 3x3 = 3² = p'² <= borne atteinte ( ou dépassée ) implique que l'on n'a plus du "premier" à 100%

S2 = ( 2, 3 ) et p' = 5 => q = [ P + Q ] criblera pour ] 3 , 5²-1 ]

2 + 3 = 5
[ 2 - 3 ] = [ - 1 ] = 1
2x2 + 3 = 7
2x2 - 3 = 1
2x2x2 + 3 = 11
2x2x2 - 3 = 5
2x2x2x2 + 3 = 19
2x2x2x2 - 3 = 13
2x2x2x2x2 - 3x3 = 23
2x2x2 + 3x3 = 17
2x3x3 + 1 = 19
2x3x3 - 1 = 17
[ 2x2x2x2x2x2 - 3x3x3x3 ] = [ - 17 ] = 17

Etc... pour Sn, q = [ P +/- Q ] criblera pour ] p , p'²-1 ]

Cordialement,

Gonzague de VILLEMAGNE
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 140 678, Messages: 1 375 818, Utilisateurs: 25 642.
Notre dernier utilisateur inscrit Cépafo.


Ce forum
Discussions: 454, Messages: 12 512.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page