Nombres premiers (Page 3) / Café mathématique / Forum de mathématiques - Bibm@th.net

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#51 06-12-2016 15:36:46

ORU
Membre
Inscription : 29-11-2016
Messages : 67

Re : Nombres premiers

:-) Re Yoshi

"Pour les multiples de 7, à partir de 49, voilà la liste des sauts consécutifs à faire
(à partir du moment où les multiples de 2,3,5 sont supprimés
(...)
Je ne vois pas ce que ça t'apprend (ou t'apprendrai)..."

ça permet de s'apercevoir que pour les multiples de 7, à partir de 49 tu as une périodicité (tous les 30 (2*3*5) entiers) de tes sauts:
28, 14, 28, 14, 28, 42, 14, 42,
28, 14, 28, 14, 28, 42, 14, 42,
28, 14, 28, 14, 28, 42, 14, 42, etc

Pour 11 on effectue les sauts suivants (tous les 210 (2*3*5*7) entiers):

22, 44, 22, 44, 66, 22, 66, 44, 22, 44, 66, 66, 22, 66, 44, 22, 66, 44, 66, 88, 44, 22, 44, 22, 44, 88, 66, 44, 66, 22, 44, 66, 22, 66, 66, 44, 22, 44, 66, 22, 66, 44, 22, 44, 22, 110, 22, 110
22, 44, 22, 44, 66, 22, 66, 44, 22, 44, 66, 66, 22, 66, 44, 22, 66, 44, 66, 88, 44, 22, 44, 22, 44, 88, 66, 44, 66, 22, 44, 66, 22, 66, 66, 44, 22, 44, 66, 22, 66, 44, 22, 44, 22, 110, 22, 110...

Mais je ne sais pas si ça peut t'aider...

Hors ligne

#52 06-12-2016 16:06:34

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 151

Re : Nombres premiers

Saolut,

Merci, oui, c'est un point que je n'avais pas encore vu...
Donc, il y a bien - apparemment - périodicité.
Je n'avais vu pour 7,qu'il n'y avait que 3 longueurs de sauts différentes  14, 28, 42
Maintenant à l'intérieur d'un cycle, il faut que je me penche sur le pourquoi, par ex. pour 7 de la succession de ces sauts, afin de savoir qu'il y a 28, 14 deux fois et qu'après on passe à 42...
Pour 7, c'est  28, 14 mais pour 11, c'est 22, 44 ordre inverse...
Pour 11 j'avais vu 5 longueurs : 22, 44, 66, 88, 110

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#53 07-12-2016 10:10:52

ORU
Membre
Inscription : 29-11-2016
Messages : 67

Re : Nombres premiers

Rebonjour Yoshi :-)
j'ai quelque chose à te montrer:

0 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233343
    2   4   6   8  10  12  14  16  18  20  22  24  26  28  30  32  34  36
      3           9          15          21          27          33          39
          5                                      25                  35
              7                                                                49->


Pour peut-être t'aider à organiser tes sauts, tu peux constater qu'en effet tu ne retires pas tous les multiples à chaque itération:
*2 tu rayes bien sûr tous les multiples,
*3 tu rayes les multiples de 3 sauf ceux qui sont multiples de 2
*5 tu rayes les multiples de 5 sauf ceux qui sont multiples de 2 ou/et 3
*7 tu rayes les multiples de 7 sauf ceux qui sont multiples de 2 ou/et 3 ou/et 5 etc

Et donc les périodes sont 2;  2*3;  2*3*5;  2*3*5*7 etc...

Pour le dire autrement: à chaque itération tu utilises la même série de chiffre à laquelle tu retires les multiples:

la première série de nombres est
s1= 2  3  4  5  6  7  8  9... tu multiplies chaque nombre de s1 par 2 (pour savoir quels nombres sont à rayer) et tu obtiens
s2= 2  4  6  8  10  12... tu fais s1-s2 et tu obtiens
s3= 3  5  7  9  11  13  15  17  19... tu multiplies cette série par 3 (pour savoir quels nombres sont à rayer) et tu obtiens
s4= 3  9  15  21  27  33  39 ... tu fais s3-s4 et tu obtiens
s5= 5  7  11  13  17  19  23... tu multiplies cette série par 5 (pour savoir quels nombres sont à rayer) et tu obtiens
s6= 25  35  65  85  95...

J'espère que ça pourra t'aider :-)

Dernière modification par ORU (09-12-2016 14:20:36)

Hors ligne

#54 07-12-2016 21:16:01

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 151

Re : Nombres premiers

Salut,

je pense...
Mais j'ai fait un constat curieux...
Dans l'ordre :
nombre premier     saut maxi      Coefficient multiplicateur
5                             20                         4  = 5-1
7                             42                         6  = 7-1
11                         110                        10  = 11-1
13                         182                        14  =  13+1  ?!
17                         374                        22  = 17+5  !!!!
19                         494                        26  = 19+7
23                         782                        34  = 23+11
29                         986                         34 = 29+5
31                       1054                         34 = 31+3
37                       1332                         36 = 37-1
41                       1886                         46 = 41+5
43                       1978                         46 = 43+3
47                       2162                         46 = 47-1
53                       2544                         48 = 53-5
59                       2478                         42 = 59-17       
61                       2562                         42 = 61-19
67                       3216                         48 = 67-19

Ce n'est pas faute d'avoir poussé les calculs : le dernier nombre de la liste des 6k+5 et 6k+7 est quand même 60 000 007

Je vais voir demain si Python veut bien aller plus loin et que temps de calcul soit acceptable : là j'ai une bonne minute de délai, ensuite une ligne toutes les 10 s...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#55 08-12-2016 09:36:12

ORU
Membre
Inscription : 29-11-2016
Messages : 67

Re : Nombres premiers

Il me semble que c'est en rapport avec le fait qu'un nombre entier quelconque est entouré de deux premiers avec le même écart de part et d'autre.

Le graph est, il me semble:
(oui je sais j'ai considéré 1 comme nombre premier, mais c'est tellement plus vrai et plus pratique dans les graphes)

01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  16  17  18  19  20  21
1░░░▒▒░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░
2░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░
3░░░░░░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░
4░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░
5░░░░░░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░
6░ Pour 11 par exemple ░▒▒░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░
7░ on aura un nombre premier ░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
8░ si on lui ajoute ou ░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░
9░░░░░░░ retranche  6 ou 8 ░░░░░░░░░▒▒░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░
10░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░
11░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░
12░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░
13░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░
14░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░▒▒░░░░░░░░░░░░░░░░░
15░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░
16░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░
17░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░
18░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░
19░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
20░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░

Hors ligne

#56 08-12-2016 11:19:04

ORU
Membre
Inscription : 29-11-2016
Messages : 67

Re : Nombres premiers

... bon finalement je crois que ça n'est pas tout à fait approprié ^^

Hors ligne

#57 06-01-2017 17:48:09

LEG
Membre
Inscription : 19-09-2012
Messages : 81

Re : Nombres premiers

Bonjour à tous.
il me semble que vous chercher une formule qui en définitive est un cycle ...
1) il faut purement et simplement supprimer les multiples de 2, 3 et 5 , il ne reste donc que 26,66....%des entiers naturels.
Ceux qui restent sont 8 suites arithmétique de raison 30

2) le crible d'Eratosthène est modifié. mais quel intérêt de calculer P² + 2n pour marquer les multiples de P...? puisque dans ce cas il va falloir inscrire tous les nombres, donc prendre de la place ou de la mémoire...non?
Ex 2269²+(2*2269) = 5152899 vous allez compter tous les 5152899 ième nombre pour barrer les multiples de 2269...

alors qu'il suffit d'établir 8 tables de cribles ou sauts que l'on va dupliquer dans un tableau de 8 colonnes où les 26% d' entiers  seront représenté par des 1, chaque 1 marqué est transformé en 0 donc produit ...

chaque table de sauts représente huit 0 plus la dernière ligne sous la colonne du premier 0 , un par colonne et on réitère la table à partir de la dernière ligne qui contient le dernier 0 ...etc c'est à dire que l'on crible modulo Pi * 30 par colonne ("ou Famille"), où Pi est un nombre premiers inférieur à le racine carrée de N, fixée à cribler limite N = 100 000 000 000 par exemple ...

Ex : la Table de Pi = 7  noté T7

la table de sauts ou crible est {(12) ; 7; 4; 7; 4; 7; 13 ; 3} (12) représente l'écart entre 7 et son carré. c'est à dire 12 nombres dans c'est 8 familles.. En partant de 7 "que l'on peut vérifier en dessous"

7  ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31
37; 41 ; 43 ; 47 ; 49 ; 53 ; 59 ; 61

ce qui va donner :
ligne
   n°0 :  7  ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31
  N°1 :  1  ;  1   ; 1   ; 1   ;  1 ;  1  ;  1  ; 1
....................................................................
...................................................................
etc
n : 1  ;  1   ; 1   ; 1   ;  1 ;  1  ;  1  ; 1

donc en partant du carré de 7 , on marque 0, à la place du 1 sous 19, ligne N° 1, qui est bien à 12 nombres de 7 ...§ etc...etc.
à la fin on compte les 1 = premiers.
pour reconstruire un 1 est bien Ligne N° n * 30 + le premier terme de la ligne 0 qui est un nombre premier Pn.

on ré-indexe les tables de crible avec une table de différence D, qui est unique :
{ 48 ; 32 ; 16 ; 32 ; 16 ; 32 ; 48 ; 16}

ce qui donne pour Pi = 37

     {(12) ; 7; 4; 7; 4; 7; 13 ; 3}
+   
   { (48) ; 32 ; 16 ; 32 ; 16 ; 32 ; 48 ; 16}

le carré de 37 est bien à 60 nombres de 37...Ce qui implique que je vais compter 32 nombres à partir de ce carré  marqué (0), pour marquer le prochain multiple de 37...etc
ou je duplique la T37, en partant de la ligne N° n de ce carré et on rèitère... toutes les 37 lignes
ou par colonne, on marque modulo (37*30) sous le 0 = 37² ainsi que pour les autres de la tables...

Pour résumer il y a 8 tables de cribles unique  T 7 à T 31 , que l'on ré-indexe avec la table D,
En fonction du prochain 1 qui n'est pas marqué  donc prochain premier : ligne n  ; colone Pi. Principe Eratosthène...

EX : ligne N° 49 ; colonne P = 29 : 49*30 + 29 = 1499 .

il y a différentes façons de programmer  soit on fait le masque avec les 8 zéros plus le dernier qui se trouve Pi lignes en dessous du premier zéro de la colonne Pn  et on duplique ..

ou on marque les 8 zéros de la table de crible et on crible chaque colonne modulo (Pi * 30) jusqu'à la limite N fixée.

Mais il y a encore d'autre façon de cribler par famille, avec un groupe multiplicatif constitué des 8 premiers : [7 ; 31].

Bonne année 2017

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer

Les questions suivantes sont faites pour éviter le spam. Si vous voulez ne plus les avoir, inscrivez-vous!

Quel est le résultat de 38+97?

Quel est le 5 ième chiffre de 8250149?

Pied de page des forums

[ Générées en 0.030 secondes, 10 requêtes exécutées - Utilisation de la mémoire : 2.14 MiB (pic d'utilisation : 2.41 MiB) ]