Bibm@th

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

#1 15-11-2016 17:23:20

Toulgoat
Invité

Nombres premiers

Bonjour,
À chaque itération du crible d'Eratosthène,
combien obtient-on de nombres premiers?

#2 15-11-2016 18:33:59

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : Nombres premiers

Bonjour,

Qu'est-ce que tu appelles itération du crible d'Eratosthène ?
On parle couramment d'itération en informatique.
Tu veux dire si on programme une boucle de calcul de l'algorithme édifiant le crible ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 16-11-2016 13:23:53

Toulgoat
Invité

Re : Nombres premiers

Ma question est mal posée
Est-ce que quand on retire les multiples de 2 sauf 2 aux entiers naturels on obtient à cette itération uniquement que 2 est premier
Et au moment où on retire les multiples de 3 sauf 3 on obtient uniquement 3 premier
Et à 5 on obtient 5 premier
Etc etc

#4 16-11-2016 15:37:09

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : Nombres premiers

Salut,

La réponse n'est pas la même si c'est via papier/crayon ou via un logiciel écrit pour.
Alors si je ne m'abuse :
* si tu raies tous les multiples de 2 qui lui sont supérieurs, il ne restera que des impairs, dont 3 qui par définition n'est pas multiple de 2 et et est donc premier (parce que c'est le début...). Il reste donc 3,5,7,9,11,13,15,17,19,21,23
* tu raies ensuite tous les multiples impairs de 3. Il reste 5,7,11,13,17,19,23.... Jusque-là, grâce aux tables de multiplication, tu sais qu'ils sont tous premiers...
La machine, elle, ne le sait pas... donc avec un programme (naïf) recréant ce crible, il lui faut faire des tests de divisibilité : la seule certitude pour une machine c'est que 3 est premier...
Mais la reproduction du crible, si on ne veut pas perde du temps en calculs inutiles (et donc coûteux) en temps est de, programmer finaud en faisant des sauts...
J'en ai plusieurs versions...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 23-11-2016 10:06:39

Toulgoat
Invité

Re : Nombres premiers

Pour être plus précis je me dis qu'à l'itération 3 par exemple on sait que
les nombres situés entre 3 et 3x3 (c'est àdire 5 et 7) seront premiers car
ils ne sont pas pas divisibles par 2 ni 3
Et qu'à l'itération 5 on sait que les nombres situés entre 5 et 5x5 seront premiers.
Et que donc il est possible de "prédire" le nombre de nombres premiers créés à chaque itération.
Est-ce que ce que je raconte est vrai?

#6 23-11-2016 11:26:49

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Nombres premiers

Bonjour,

Tu as raison. Quand on a réalise la $n$-ième itération du crible, on a trouvé tous les nombres premiers inférieurs ou égaux à $p_n^2$, où $p_n$ est le $n$-ième nombre premier. Le nombre de nombres premiers créé à chaque itération est donc égal à
$\pi(p_{n+1}^2)-\pi(p_n^2)$, où $\pi(k)$ est le nombre de nombres premiers inférieurs ou égaux à $k$. En utilisant ensuite une approximation de $\pi(x)$ et de $p_n$, on peut espérer trouver une estimation de ce que tu veux...

F.

Hors ligne

#7 23-11-2016 13:30:03

Toulgoat
Invité

Re : Nombres premiers

D'abord merci pour vos réponses !
On peut ne trouver qu'une approximation ?
Je pose la question par ce que je vois que la fonction pi donne tous les
nombres premiers jusqu'à la valeur sans faire d'erreur...

#8 23-11-2016 14:59:53

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Nombres premiers

D'accord mais que vaut cette fonction en 1000 par exemple ?
Je parlais d'approcher cette fonction par des fonctions classiques (polynôme logarithme...) pour avoir des valeurs numériques effectives...

Hors ligne

#9 23-11-2016 15:11:25

Toulgoat
Invité

Re : Nombres premiers

Oui je crois comprendre mais je me suis arrêté au bac alors...
Tu penses qu'il est possible de trouver une formule?

#10 23-11-2016 15:14:01

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Nombres premiers

S'il te donne la formule, tu peux aller revendiquer la médaille Fields !!

Dernière modification par Yassine (23-11-2016 15:14:11)


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#11 23-11-2016 16:05:53

Toulgoat
Invité

Re : Nombres premiers

Pour quelle raison ?
Elle servirait à quoi à part prouver qu'il existe une infinité de nombres premiers ?

#12 23-11-2016 16:37:56

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Nombres premiers

Il existe une multitudes de démonstration de l'infinitude des nombres premiers.
Ce que tu demandes ici, c'est de savoir comment il sont répartis parmi les nombres entiers.
Si tu prends les deux ensembles $\{0,2,4, \cdots\}$ et $\{0, 2, 2^1, 2^{2^2}, 2^{2^{2^2}}, \cdots\}$, ils sont tous les deux infinis, pour autant, cette seule information est insuffisante pour nous rendre compte de la "vraie" nature de ces deux ensemble.

La caractérisation de la distribution des nombres premiers fait partie des problèmes ouverts en théorie des nombres.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#13 24-11-2016 13:31:02

Toulgoat
Invité

Re : Nombres premiers

Ok ok merci pour tout :-)

#14 25-11-2016 14:47:58

Toulgoat
Invité

Re : Nombres premiers

Re-bonjour !
Une autre question :
Est-ce que la raréfaction des nombres premiers:
Si on enlève les multiples de 2 ce qui reste a pour densité 1/2
Si ensuite on enlève les multiples de 3 ce qui reste à pour densité (1-1/2)(1-1/3)
Si ensuite on enlève les multiples de 5 ce qui reste à pour densité (1-1/2)(1-1/3)(1-1/5)
Si ensuite on enlève les multiples de 7 ce qui reste à pour densité (1-1/2)(1-1/3)(1-1/5)(1-1/7)
Si ensuite on enlève les multiples de 11 ce qui reste à pour densité (1-1/2)(1-1/3)(1-1/5)(1-1/7)(1-1/11)
est une preuve qu'il existe une infinité de nombres premiers ?
Étant donné qu'on utilise le premier nombre qu'il reste comme multiple suivant ?

#15 25-11-2016 21:40:56

Toulgoat
Invité

Re : Nombres premiers

Personne ?
Peut-être que je ne suis pas clair ?

#16 26-11-2016 11:16:33

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Nombres premiers

Bonjour,
Admettons que ta densité est correcte (je pense qu'elle l'est).
Si on note $p_k$ le $k$-ième nombre premier ($p_1=2$) et $E_k(n)$ le nombre d'entiers $\le n$ qui restent après la $k$-ième étape du crible d’Ératosthène. On dit alors que $\displaystyle d_k = \lim_{n \to \infty}\frac{E_k(n)}{n} = \Pi_{l=1}^k (1-\frac{1}{p_l})$.
En quoi est-ce que ça implique que le crible ne s'arrêtera jamais ?
On pourrait très bien arriver à une étape $K$ où on ne tombe plus sur aucun nombre premier, et l'ensemble qui reste après $K$ étapes aurait une densité $d_K$.

Dernière modification par Yassine (26-11-2016 14:55:32)


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#17 26-11-2016 17:38:58

Toulgoat
Invité

Re : Nombres premiers

j'avais pensé que:
la densité 1/2 correspond aux nombres impairs,

que la densité (1-1/2)(1-1/3) correspond aux deux nombres 5 et 7 par exemple divisé par la période (11-7) et finalement 1/3
(les multiples de 2 sur la première ligne, les multiples de 3 sur la deuxième ligne, les nombres qu'il reste en bas):

░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓
░░░░▓░▓░░░▓░▓░░░▓░▓░░░▓░
         5 7    11 13    17 19   23 25


que la densité (1-1/2)(1-1/3)(1-1/5) correspond aux huit nombres 7 11 13 17 19 23 29 et 31 par exemple divisé par la période (37-7) et finalement 8/30

░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░
░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░░▓░
░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░░░░▓░
░░░░░░▓░░░▓░▓░░░▓░▓░░░▓░░░░░▓░▓░░░░░▓░░░▓░▓░░░▓░▓░░░▓░░░░░▓░▓░░░░░▓░░░▓░▓░░░▓░▓░░░▓░░░░░▓░▓
             7      11 13  17 19  23        29 31         37    41 43  47 49 53         59  61                                                             
etc...

Et que par conséquent, puisque
- aucune densité ne peut être nulle, et que
- on prend le premier nombre de cette densité pour l'itération suivante (qui devient premier),
alors il existe une infinité de nombres premiers,

mon raisonnement est-il trop hâtif ?

#18 26-11-2016 17:49:14

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Nombres premiers

Je ne suis pas sûr de tout comprendre.
Que veut dire :

Toulgoat a écrit :

on prend le premier nombre de cette densité pour l'itération suivante (qui devient premier)

Pourrais-u décrire formellement ce que tu entends par "densité" ? et comment on "prend un nombre dans une densité" ?

La définition que je connais est celle que j'ai donnée : Si $A$ est un sous-ensemble de $\mathbb{N}$ et qu'on note $A(n)$ le nombre d'éléments de $A$ qui sont $\le n$, alors la densité de $A$ est donnée par $\displaystyle \lim_{n \to \infty} \frac{A(n)}{n}$.

Et que veut dire "qui devient premier" ?


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#19 26-11-2016 20:45:47

Toulgoat
Invité

Re : Nombres premiers

Je suis désolé je n'ai qu'un baccalauréat électrotechnique et je ne pense pas pouvoir l'écrire formellement,
je vais par contre essayer de l'exprimer autrement :
La densité est pour moi la quantité de nombres qu'il reste sur le produit des nombres premiers qui ont déjà servi lors des itérations précédentes
À la densité suivante, donc l'itération suivante, puisqu'on est sûr qu'il y a un nombre, alors on est sûr qu'il y a une infinité de nombres premiers.
C'est mieux comme ça ?

#20 27-11-2016 10:23:55

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Nombres premiers

Bonjour,

Toulgoat a écrit :

La densité est pour moi la quantité de nombres qu'il reste sur le produit des nombres premiers qui ont déjà servi lors des itérations précédentes

Cette définition ne me semble pas correcte à plus d'un titre.
Quand on dit "la quantité de nombres qu'il reste" : on suppose qu'on est parti avec un certain ensemble d'entiers, disons $A$, qu'on a enlevé les multiple du nombre premier $p$ et qu'on compte ce qui reste. Donc, premier question, quel est l'ensemble de départ ? Est-ce $\mathbb{N}$ tout entier ?
Dans ce cas, le définition que tu donnes est inapplicable : il reste toujours une quantité infinie de nombres. Divisée par n'importe quel nombre positif, cette quantité reste infinie.
Si maintenant on part au départ avec une partie finie de $\mathbb{N}$, alors la quantité qui reste fait intervenir le nombre d'éléments initial. Par exemple, si on part des $100$ premiers entiers et qu'on enlève les multiples de $2$, il restera $100/2$ éléments, si on divise ensuite par le produit des nombres premiers utilisés, soit $2$, on trouve $100/4$, chiffre qui n'a rien à voir avec $1-1/2$.

La densité est une notion qui mesure la rareté des éléments d'un ensemble infinis, comparés au entiers naturels. Les nombres pairs ne sont pas rares, on tombe sur un nombre pair une fois sur deux. La densité est de $1/2$ (avec la définition formelle que j'ai donnée). Les nombres premiers à l'inverse sont de plus en plus rares. Leur densité est nulle (avec la notation de Fred, $\displaystyle \lim_{n \to \infty} \frac{\pi(n)}{n}=0$).

Autres point, tu parles du produit des nombres premiers utilisés. La formule que tu donnes est beaucoup plus compliqué. Prends par exemple $(1-1/2)(1-1/3)(1-1/5)$, si on la développe, on trouve $1-1/2-1/3-1/5 + 1/2*1/3 + 1/2*1/5 + 1/3*1/5 - 1/2*1/3*1/5$.
Je ne suis pas sûr de voir comment tu arrives à cette formule (qui est juste) avec la définition que tu donnes ?


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#21 27-11-2016 11:30:47

Toulgoat
Invité

Re : Nombres premiers

Tout d'abord merci pour ces réponses toujours constructives et ouvertes au dialogue
Je peux déjà essayer de répondre à la dernière question
(1-(1/2))(1-(1/3))(1-(1/5)
= (1/2)(2/3)(4/5)
=8/30
Est-ce correct ?
Je réfléchis au reste qui est plus compliqué pour moi

#22 27-11-2016 12:21:55

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Nombres premiers

Oui, le calcul est correct, mais il ne correspond pas à la définition que tu donnes : tu dis, il faut diviser la quantité qui reste par le produit des nombres premiers déjà utilisés.
A l'étape 3, les nombres premiers utilisés sont $2$, $3$, et $5$, leur produit est bien $30$, mais à quoi correspond $8$ ? Quel est cet ensemble de nombres qui restent qui a une quantité de $8$ ?


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#23 27-11-2016 13:52:22

Toulgoat
Invité

Re : Nombres premiers

L'ensemble le de nombres qui restent qui a une quantité de 8 sont les nombres:
07   11 13 17 19 23   29 31 sur la période de 07 à 37 exclu
37   41 43 47 49 53   59 61 sur la période de 37 à 67 exclu
Etc
Comme sur ma deuxième représentation où apparait la quantité de nombres qui se répète.

#24 27-11-2016 14:26:13

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Nombres premiers

Bonjour,
Désolé, je ne comprends pas.
Je te demande un ensemble tu me donne une série de nombres groupés par 8. Pourquoi ce groupement ?
Quel est LE ensemble (c'est moche, mais c'est pour insister) dont la taille fait 8. Comment on le détermine ? A quoi correspondent ces bornes 7 à 37 et 37 à 67,
Qu'est-ce que tu appelles "période" ?
Que veut dire "la quantité de nombres qui se répète" ? Qu'est-ce qui se répète ?


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#25 27-11-2016 16:30:32

Toulgoat
Invité

Re : Nombres premiers

Si tu écris sur une ligne les entiers naturels
et sous cette ligne les multiples de 2
(en plaçant les multiples de 2 sous les multiples de 2 de la première ligne)
Et sous cette ligne les multiples de 3
(même chose)
Il reste combien de nombres si on soustrait les lignes 2 et 3 de la première ligne?
Comment peut-on calculer cet ensemble ?
Quel motif apparaît ?
Quelle est sa période et pourquoi ?
Ce sont les questions que je me suis posées qui m'ont amenées à mes conclusions.

Pied de page des forums