nombres premiers : Généralisation algorithmique du crible d'Eratostène.

Ludovic

Certains parlent de la recherche des nombres premiers sur le forum. Dans cette optique, je propose une généralisation du crible d'Eratostène avec l'algorithme suivant :

$\mathcal{P}:={2}$ ($\mathcal{P}$ désigne l'ensemble des nombres premiers calculés)
$A_1:=\{1\}$
$P:=2$ ($P$ désigne le produit des nombres premiers déjà calculer)

On construit $A_{n+1}$ de la façon suivante :
$A_{n+1}:=\emptyset$
$p:=min(P+1,A_n \backslash \{1\})$ ($p$ est le $n+1$ème nombre premier).
$\mathcal{P}:=\mathcal{P} \cup \{p\}$

$a$ variant dans $A_n$
$k$ variant de $0$ à $p-1$
si $ p \not{|} a+k*P$ alors $A_{n+1}:=A_{n+1} \cup \{a+k*P\}$
fin des deux boucles
$P:=P*p$

Au début de la construction de $A_{n+1}$, $\mathcal{P}$ contient les $n$ premiers nombres premiers, tous les nombres premiers s'écrivent sous la forme $a+kP$ (et il y en a une infinité de cette forme) où $a$ est un élément de $A_n$. A la fin de la boucle, on a la même propriété mais au rang $n+1$.

Qu'en pensez-vous ?

borde

Quelques questions à brûle-pourpoint :

1. Je n'ai pas vu l'initialisation de $n$, ni son incrémentation. Je suppose que $n=1$ au départ, puis est incrémenté de $1$ à chaque passage de la première boucle, non ? Si c'est le cas, quelle est la première valeur de $p$ avec $n=1$ ?

2. Etes-vous sûr d'avoir, à chaque étape, le fait que $\gcd(a,P) =1$ ? Sinon, vous risquez d'avoir autre chose que des nombres premiers dans les quantités $a + kP$ (théorème de Dirichlet).

Borde.

Ludovic

1) J'ai consruit $A_1$. Je donne la méthode pour construire $A_{n+1}$ à partir de $A_n$. Que veux-tu de plus?

2) Pour bien comprendre ce que l'algorithme fait, il ne faut pas oublier le titre du sujet. Il s'agit de généraliser le crible.

On commence par éliminer les nombres pairs, puis les multiple de 3, de 5....

Pour ça, on dit que les nombres impairs sont de la forme $2n+1$.
Le prochain nombre premier est $2*1+1=3$.
Tous les nombres premiers s'écrivent alors :

$2(3n)+1 = 6n+1$
$2*(3n+1)+1=6n+3$
$2*(3n+2)+1=6n+5$

$1,3,5$ sont les $a+kP$ de l'algorithme.

Il faut ensuite éliminer les multiples de $3$. C'est à dire les $6n+3$ (multiple de $3$ impair). etc, etc...

borde

<!--latex-->Il me semble que c'est un algorithme mettant en oeuvre le crible d'Erathostène, d'une façon un peu différente de la méthode classique...Il faudrait l'essayer pour voir.
<BR>
<BR>Borde.<BR>

Ludovic

Le principe du crible est d'éliminer tous les multiples des nombres premiers que l'on a déjà calculés. La limite de la méthode est qu'on l'applique à un nombre fini de nombres. Ici on peut calculer tous les nombres premiers avec le même principe. Cette méthode n'est absolument pas efficace. Elle a pour seul intérêt de montrer que l'on peut calculer tous les nombres premiers avec la méthode du crible.

borde

Le crible d'Erathostène se "théorise" à l'aide de la {\it formule de Legendre} (1808) : si $N_m(x)$ désigne le nombre d'entiers $n \leq x$ tels que $\gcd(m,n)=1$, alors ce crible s'écrit : $$N_m(x) = \sum_{d|m} \mu(d) \left [\frac {x}{d} \right ]$$ où, comme d'habitude, $\mu$ désigne la fonction de Möbius et $[x]$ est la partie entière de $x$.

Lorsqu'on prend $m = \displaystyle {\prod_{p \leq \sqrt x} p}$, seuls sont comptés dans $N_m(x)$ le nombre $1$ et les nombres premiers de l'intervalle $]\sqrt x \, ; \, x]$ et ainsi $N_m(x) = \pi(x) - \pi (\sqrt x) + 1$. L'estimation dans la formule de Legendre de $\displaystyle {\left [\frac {x}{d} \right ]}$ par $\frac {x}{d} + O(1)$ donne alors : $$\pi(x) - \pi (\sqrt x) + 1 = x \prod_{p \leq \sqrt x} \left (1 - \frac {1}{p} \right ) + O(2^{\pi(\sqrt x)})$$ et l'on s'aperçoit (en utilisant le théorème de Mertens), que le terme d'erreur est alors d'une taille déraisonnable devant le terme principal : c'est pour cette raison essentielle que le "crible d'Erathostène" n'est "absolument pas efficace". Cependant, une modification de la formule de Legendre, en utilisant un paramètre $t$ tel que $1 \leq t \leq x$ et en majorant $\pi(x) - \pi(t) + 1$ par le nombre des entiers $n \leq x$ n'ayant aucun facteur premier $\leq y$ donne avec les mêmes calculs : $$\pi(x) \ll x \prod_{p \leq y} \left (1 - 1/p \right ) + O(2^y) \ll \frac {x}{\ln y} + O(2^y) \ll \frac {x}{\ln \ln x}$$ ce qui est certes loin du TNP, mais qui améliore grandement le calcul direct précédent. Cette idée simple est à la base de ce que l'on appelle maintenant les {\it méthodes de cribles}.

Tout cela pour dire que, même si, en apparence, une méthode n'aboutit pas, elle reste en général génératrice de la (ou des) bonnes idées qui permettent de conclure. On utilise toujours des arguments de type "Erathostène", surtout pour les premiers termes d'un calcul sommatoire; premettant ainsi d'évacuer de la somme les termes non prépondérants.

Borde.

borde

C'est $1 \leq y \leq x$ qu'il faut lire (j'espère qu'AD pourra corriger...).

Borde.

borde

Revoici le texte correct (c'est moi qui suis désolé) :


Le crible d'Erathostène se "théorise" à l'aide de la {\it formule de Legendre} (1808) : si $N_m(x)$ désigne le nombre d'entiers $n \leq x$ tels que $\gcd(m,n)=1$, alors ce crible s'écrit : $$N_m(x) = \sum_{d|m} \mu(d) \left [\frac {x}{d} \right ]$$ où, comme d'habitude, $\mu$ désigne la fonction de Möbius et $[x]$ est la partie entière de $x$.\\
\\
Lorsqu'on prend $m = \displaystyle {\prod_{p \leq \sqrt x} p}$, seuls sont comptés dans $N_m(x)$ le nombre $1$ et les nombres premiers de l'intervalle $]\sqrt x \, ; \, x]$ et ainsi $N_m(x) = \pi(x) - \pi (\sqrt x) + 1$. L'estimation dans la formule de Legendre de $\displaystyle {\left [\frac {x}{d} \right ]}$ par $\frac {x}{d} + O(1)$ donne alors : $$\pi(x) - \pi (\sqrt x) + 1 = x \prod_{p \leq \sqrt x} \left (1 - \frac {1}{p} \right ) + O(2^{\pi(\sqrt x)})$$ et l'on s'aperçoit (en utilisant le théorème de Mertens), que le terme d'erreur est alors d'une taille déraisonnable devant le terme principal : c'est pour cette raison essentielle que le "crible d'Erathostène" n'est "absolument pas efficace". Cependant, une modification de la formule de Legendre, en utilisant un paramètre $y$ tel que $1 \leq y \leq x$ et en majorant $\pi(x) - \pi(y) + 1$ par le nombre des entiers $n \leq x$ n'ayant aucun facteur premier $\leq y$, donne avec les mêmes calculs : $$\pi(x) \ll x \prod_{p \leq y} \left (1 - \frac {1}{p} \right ) + 2^y \ll \frac {x}{\ln y} + 2^y \ll \frac {x}{\ln \ln x}$$ en choisissant $y = \ln x$, ce qui est certes loin du TNP, mais qui améliore grandement le calcul direct précédent. Cette idée simple est à la base de ce que l'on appelle maintenant les {\it méthodes de cribles}.\\
\\
Tout cela pour dire que, même si, en apparence, une méthode n'aboutit pas, elle reste en général génératrice de la (ou des) bonnes idées qui permettent de conclure. On utilise toujours des arguments de type "Erathostène", surtout pour les premiers termes d'un calcul sommatoire, premettant ainsi d'évacuer de la somme les termes non prépondérants.\\
\\
Borde.