Fonction de compte des nombres premiers

En mathématiques, la fonction de compte des nombres premiers est la fonction comptant le nombre de nombres premiers inférieurs ou égaux à un nombre réel x. Elle est notée $\pi(x)\,$ (à ne pas confondre avec la constante π).

Les 60 premières valeurs de π(n)

Sommaire

1 Historique
2 Algorithmes d'évaluation de π(x)
3 Autres fonctions de compte des nombres premiers
4 Inégalités
5 L'hypothèse de Riemann
6 Relation avec les sommes de nombres premiers
7 Table de π(x), x / ln x, et Li(x)
8 Formules pour les fonctions de compte des nombres premiers
9 Notes et références
- 9.1 Notes
- 9.2 Références

Historique

Depuis Euclide, il est connu qu'il existe des nombres premiers en quantité infinie. Pour affiner la connaissance de ces nombres, la théorie des nombres s'est attelée à en déterminer le taux de croissance. À la fin du XVIII^e siècle, Gauss^[1] et Legendre^[2] ont conjecturé que cette quantité était proche de $x/\operatorname{ln}(x)$ .

De manière équivalente, on peut l'écrire

$\lim_{x\rightarrow +\infty}\frac{\pi(x)}{x/\operatorname{ln}(x)}=1$

Cette affirmation constitue le théorème des nombres premiers, prouvé indépendamment par Hadamard et de La Vallée Poussin, en 1896, grâce à la fonction zêta de Riemann. Une assertion équivalente est :

$\lim_{x\rightarrow +\infty}\pi(x) / \operatorname{li}(x)=1$ ,

où $\operatorname{li}\,$ est la fonction logarithme intégral.

Des estimateurs plus précis de $\pi(x)\,$ sont aujourd'hui connus. Par exemple:

$\pi(x) = \operatorname{li}(x) + O \left( x \exp \left( -\frac{\sqrt{\ln(x)}}{15} \right) \right)$ ,

Des preuves du théorème des nombres premiers n'utilisant pas l'analyse complexe furent proposées en 1948 par Atle Selberg et Paul Erdős.

Algorithmes d'évaluation de π(x)

Une façon simple de calculer $\pi(x)\,$ , si $x\,$ est un nombre petit, est d'utiliser le crible d'Ératosthène de manière à trouver tous les premiers inférieurs à $x\,$ et ensuite de les compter.

Une manière plus élaborée pour trouver $\pi(x)\,$ a été inventée par Legendre : étant donné $x\,$ , si $p_1\,$ , $p_2\,$ , …, $p_k\,$ sont des nombres premiers distincts, alors le nombre d'entiers inférieurs ou égaux à $x$ qui ne sont divisibles par aucun $p_i\,$ est

$\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots$ , (où $\lfloor\cdot\rfloor$ désigne la fonction Partie entière).

Ce nombre est donc égal à : $\pi(x)-\pi\left(\sqrt{x}\right)+1\,$ où les nombres $p_1\,$ , $p_2\,$ , …, $p_k\,$ sont les nombres premiers inférieurs ou égaux à la racine carrée de $x\,$ .

Dans une série d'articles publiés entre 1870 et 1885, Ernst Meissel (de) décrivit (et utilisa) une manière combinatoire pratique pour évaluer $\pi(x)\,$ . Soit $p_1\,$ , $p_2\,$ , …, $p_n\,$ les premiers $n\,$ nombres premiers et notons par $\Phi(m,n)\,$ le nombre de nombres naturels inférieurs à $m\,$ qui ne sont divisibles par aucun $p_i\,$ . Alors

$\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right),\,$

Soit un nombre naturel donné $m\,$ , si $n=\pi\left(\sqrt[3]{m}\right)\,$ et si $\mu=\pi\left(\sqrt{m}\right)-n\,$ , alors

$\pi(m)=\Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu}{2}-1-\sum_{k=1}^\mu\pi\left(\frac{m}{p_{n+k}}\right).\,$

En utilisant cette approche, Meissel calcula $\pi(x)\,$ , pour $x\,$ égal à 5x10⁵, 10⁶, 10⁷, et 10⁸.

En 1959, Derrick Lehmer étendit et simplifia la méthode de Meissel. Définissons, pour un réel $m$ et pour des nombres naturels $n$ , et $k$ , $P k (m, n)$ comme le nombre de nombres inférieurs à m avec exactement k facteurs premiers, tous plus grands que $p n$ . De plus, fixons $P_0(m,n)=1\,$ . Alors

$\Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n),\,$

où la somme actuelle possède seulement de manière finie plusieurs termes différents de zéro. Soit $y$ désignant un entier tel que $\sqrt[3]{m}\le y\le\sqrt{m}\,$ , et fixons $n=\pi(y)\,$ . Alors $P_1(m,n)=\pi(m)-n\,$ et $P_k(m,n)=0\,$ lorsque $k$ ≥ 3. Par conséquent

$\pi(m)=\Phi(m,n)+n-1-P_2(m,n)\,$ .

Le calcul de $P_2(m,n)\,$ peut être obtenu de cette manière :

$P_2(m,n)=\sum_{y<p\le\sqrt{m}}\left(\pi\left(\frac mp\right)-\pi(p)+1\right).\,$

D'un autre côté, le calcul de $Φ(m, n)$ peut être fait en utilisant les règles suivantes :

$\Phi(m,0)=\lfloor m\rfloor;\,$
$\Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right).\,$

En utilisant cette méthode et un IBM 701, Lehmer a été capable de calculer $\pi\left(10^{10}\right)$ .

Le mathématicien chinois Hwang Cheng, dans une conférence sur les fonctions de nombres premiers à l'université de Bordeaux, utilisa les identités suivantes^[3] :

$e^{(a-1)\Theta}f(x)=f(ax)\,$

$J(x)=\sum_{n=1}^{\infty}\frac{\pi(x^{1/n})}{n}\,$

et en notant $x=e^t\,$ , en appliquant la transformée de Laplace aux deux côtés et en appliquant une somme géométrique sur $e^{n\Theta}\,$ , on obtient l'expression :

$\frac{1}{2{\pi}i}\int_{c-i\infty}^{c+i\infty}g(s)t^{s}=\pi(t)$

$(1-e^{\Theta})\frac{ln\zeta(s)}{s}=g(s)$

$\Theta(s)=s\frac{d}{ds}.$

Autres fonctions de compte des nombres premiers

D'autres fonctions de compte des nombres premiers sont aussi utilisées car elles sont plus pratiques pour travailler. Une d'elles est la fonction de compte des nombres premiers de Riemann, notée $\Pi(x)\,$ ou $J(x)\,$ . Celle-ci possède des sauts de 1/n pour les puissances de nombres premiers pⁿ, qui prennent une valeur à mi-chemin entre les deux côtés des discontinuités. Elle peut être aussi définie comme une transformation de Mellin inverse. Formellement, nous pouvons définir J par

$J(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg)$

où p est un nombre premier.

Nous pouvons aussi écrire

$J(x) = \sum_{n=1}^\infty \frac1n \pi(x^{1/n})$ et

$\ln( \zeta (s))=s\int_{0}^{\infty}dxJ(x) x^{-s+1}$

et en connaissant la relation entre la fonction log de la fonction Riemann et la fonction de von Mangoldt $\Lambda\,$ , et la formule de Perron, nous avons :

$J(x)= \sum_{2}^{x} \frac{ \Lambda (n)}{ln(n)}$

excepté où se trouvent les discontinuités aux puissances de nombres premiers, et ainsi, $\pi(x)\,$ peut être retrouvé à partir de J par l'inversion de Möbius.

La fonction de Tchebychev pèse les nombres premiers ou les puissances de nombres premiers pⁿ par ln p:

$\theta(x)=\sum_{p\le x}\ln p,$

$\psi(x) = \frac12 \bigg(\sum_{p^n < x} \ln p\ + \sum_{p^n \le x} \ln p\bigg).$

Excepté aux discontinuités des puissances de nombres premiers, nous avons

$\psi(x)=\sum_{n=1}^\infty\theta(x^{1/n})=\sum_{n\le x}\Lambda(n).$

Inégalités

Ci-dessous se trouvent quelques inégalités pour $\pi(x)\,$ .

$\pi(x) < 1,25506\ \frac {x} {\log x}$ si x > 1.

$\frac {x} {\log x + 2} < \pi(x) < \frac {x} {\log x - 4}$ si x ≥ 55^[4].

Les inégalités suivantes sont vérifiées par le n^e nombre premier, noté p_n^[5] :

$n\ln n + n\ln\ln n - n^{\,} < p_n^{\,} < n \ln n + n \ln \ln n$ si n ≥ 6.

L'inégalité de gauche est vraie si n ≥ 1 et celle de droite si n ≥ 6 ; plus précisément encore, si n ≥ 40 000, on a

$n\ln n + n\ln\ln n - n^{\,} < p_n^{\,} < n \ln n + n \ln \ln n-0,948 n$

Une approximation pour le n^e nombre premier est

$p_n = n \ln n + n \ln \ln n - n + \frac {n \ln \ln n - 2n} {\ln n} + O\left( \frac {n (\ln \ln n)^2} {(\ln n)^2}\right).$

L'hypothèse de Riemann

L'hypothèse de Riemann propose une estimation plus serrée de $\pi(x)\,$ , équivalente à distribution plus régulière des nombres premiers:

$\pi(x) = \operatorname{Li}(x) + O(\sqrt{x} \log{x}).$

Relation avec les sommes de nombres premiers

Si nous avons une somme de fonction sur tous les nombres premiers : $\sum_{p}f(x)\,$ et que nous souhaitons accélérer sa convergence, nous pouvons l'écrire sous la forme :

$\sum_{n=1}^{\infty}(-1)^{n}(\pi(n)-\pi(n-1)+1)f(n)=2f(2)-\sum_{p}f(x)+\sum_{n=1}^{\infty}(-1)^{n}f(n)$

pour la série de gauche, nous avons pu appliquer la transformée d'Euler pour les séries alternées, en apportant que f(n)>f(n+1) et que les 2 séries convergent, elle relie aussi une série alternée avec sa somme de nombres premiers, d'autre part. La principale utilisation de ceci est que nous pouvons donner une bonne approximation en utilisant seulement quelques valeurs de la Fonction compte des nombres premiers.

Table de π(x), x / ln x, et Li(x)

Voici une table qui montre le comportement comparé des trois fonctions π(x), x / ln x et Li(x) :

x	π(x)	π(x) − x / ln x	Li(x) − π(x)	x / π(x)
10	4	−0,3	2,2	2,500
10²	25	3,3	5,1	4,000
10³	168	23	10	5,952
10⁴	1 229	143	17	8,137
10⁵	9 592	906	38	10,425
10⁶	78 498	6,116	130	12,740
10⁷	664 579	44,158	339	15,047
10⁸	5 761 455	332,774	754	17,357
10⁹	50 847 534	2 592 592	1 701	19,667
10¹⁰	455 052 511	20 758 029	3 104	21,975
10¹¹	4 118 054 813	169 923 159	11 588	24,283
10¹²	37 607 912 018	1 416 705 193	38 263	26,590
10¹³	346 065 536 839	11 992 858 452	108 971	28,896
10¹⁴	3 204 941 750 802	102 838 308 636	314 890	31,202
10¹⁵	29 844 570 422 669	891 604 962 452	1 052 619	33,507
10¹⁶	279 238 341 033 925	7 804 289 844 393	3 214 632	35,812
10¹⁷	2 623 557 157 654 233	68 883 734 693 281	7 956 589	38,116
10¹⁸	24 739 954 287 740 860	612 483 070 893 536	21 949 555	40,420
10¹⁹	234 057 667 276 344 607	5 481 624 169 369 960	99 877 775	42,725
10²⁰	2 220 819 602 560 918 840	49 347 193 044 659 701	222 744 644	45,028
10²¹	21 127 269 486 018 731 928	446 579 871 578 168 707	597 394 254	47,332
10²²	201 467 286 689 315 906 290	4 060 704 006 019 620 994	1 932 355 208	49,636
10²³	1 925 320 391 606 818 006 727	37 083 513 766 592 669 113	7 236 148 412	51,939

La première colonne est la suite A006880 de l’OEIS, la deuxième colonne est la suite A057835 et la troisième colonne, la suite A057752.

Formules pour les fonctions de compte des nombres premiers

Celles-ci sont de deux sortes, les formules arithmétiques et les formules analytiques. Ces dernières sont celles qui nous permettent de prouver le théorème des nombres premiers. Elles proviennent des travaux de Riemann et de von Mangoldt, et sont généralement connues comme formules explicites pour les fonctions L (en).

Nous avons l'expression suivante pour $\psi\,$ :

$\psi(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \ln 2\pi - \frac12 \ln(1-x^{-2}).$

Ici, $\rho\,$ sont les zéros de la fonction zêta de Riemann dans la bande critique, où la partie réelle de $\rho\,$ est comprise entre zéro et un. La formule est valide pour les valeurs de x plus grandes que un, qui est la région qui nous intéresse, et la somme des racines est convergente sous conditions, et devrait être prise en ordre croissant des valeurs absolues des parties imaginaires.

Pour J, nous avons une formule plus compliquée :

$J(x) = \operatorname{li}(x) - \sum_{\rho}\operatorname{li}(x^{\rho}) - \ln 2 + \int_x^\infty \frac{dt}{t(t^2-1) \ln t}.$

De nouveau, la formule est valide pour x > 1, et $\rho\,$ représente les zéros non triviaux de la fonction zêta ordonnés en accord avec leurs valeurs absolues. Le premier terme li(x) est le logarithme intégral habituel ; néanmoins, il est moins facile de décrire ce que représente li dans les autres termes. La meilleure manière de concevoir cela est de considérer l'expression $\operatorname{li}(x^\rho)\,$ comme une abréviation de $\operatorname{Ei}(\rho\ln x)\,$ , où Ei est le prolongement analytique de la fonction exponentielle intégrale à partir des réels positifs vers le plan complexe muni d'une coupure le long des réels négatifs.

Notes et références

Notes

↑ C'est en 1849, soit plus de 40 ans après la publication de Legendre, que Gauss indique, dans une correspondance avec Encke, qu'il a conjecturé en 1793 que $π(x)$ est approximativement égal à $x / l n (x)$ .
↑ A.M. Legendre, Essai sur la théorie des nombres, Seconde édition. Paris, Courcier (1808) p. 394
↑ Hwang H., Cheng, « Démarches de la Géométrie et des Nombres de l'Université du Bordeaux », dans Prime Magic conference, 2001
↑ (en) Barkley Rosser (en), « Explicit bounds for some functions of prime numbers », dans Amer. J. Math, vol. 63, 1941, p. 211–232 [texte intégral]
↑ (en) Pierre Dusart, « The kth prime is greater than k(ln k + ln ln k-1) for k≥2 », dans Mathematics of Computation, vol. 68, 1999, p. 411–415 [texte intégral]

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Prime-counting function » (voir la liste des auteurs)
Jean-Paul Delahaye, Merveilleux nombres premiers, 2000, Éditions Belin (ISBN 2-84245-017-5)
(en) Eric Bach et Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press (ISBN 0-262-02405-5) page 234, section 8.8
(en) Leonard Eugene Dickson, History of the Theory of Numbers I: Divisibility and Primality, 2005, Dover Publications (ISBN 0-486-44232-2)

Catégories :

Théorie analytique des nombres
Fonction remarquable

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction de compte des nombres premiers de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

Fonction De Compte Des Nombres Premiers — En mathématiques, la fonction de compte des nombres premiers est la fonction comptant le nombre de nombres premiers inférieurs ou égaux à un nombre réel x. Elle est notée (à ne pas confondre avec la constante π). Les 60 premièr … Wikipédia en Français
Caractérisation des nombres premiers — Nombre premier 7 est un nombre premier car il admet exactement deux diviseurs positifs … Wikipédia en Français
Nombres premiers — Nombre premier 7 est un nombre premier car il admet exactement deux diviseurs positifs … Wikipédia en Français
Formule Pour Les Nombres Premiers — Formules pour les nombres premiers En mathématiques, la recherche de formules exactes donnant tous les nombres premiers (ou même donnant uniquement des nombres premiers) s est généralement avérée vaine, ce qui a amené à se contenter de formules… … Wikipédia en Français
Formule pour les nombres premiers — Formules pour les nombres premiers En mathématiques, la recherche de formules exactes donnant tous les nombres premiers (ou même donnant uniquement des nombres premiers) s est généralement avérée vaine, ce qui a amené à se contenter de formules… … Wikipédia en Français
Formules pour les nombres premiers — En mathématiques, la recherche de formules exactes donnant tous les nombres premiers (ou même donnant uniquement des nombres premiers) s est généralement avérée vaine, ce qui a amené à se contenter de formules approchées. Cette page recense les… … Wikipédia en Français
Liste Des Matières De La Théorie Des Nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 … Wikipédia en Français
Liste des matieres de la theorie des nombres — Liste des matières de la théorie des nombres Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 … Wikipédia en Français
Liste des matières de la théorie des nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 Test de primalité e … Wikipédia en Français
Sur le nombre de nombres premiers inferieurs a une taille donnee — Sur le nombre de nombres premiers inférieurs à une taille donnée Sur le nombre de nombres premiers inférieurs à une taille donnée (ou Über die Anzahl der Primzahlen unter einer gegebenen Grösse) est un article de 8 pages écrit par Bernhard… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Fonction de compte des nombres premiers

Sommaire

Historique

Algorithmes d'évaluation de π(x)

Autres fonctions de compte des nombres premiers

Inégalités

L'hypothèse de Riemann

Relation avec les sommes de nombres premiers

Table de π(x), x / ln x, et Li(x)

Formules pour les fonctions de compte des nombres premiers

Notes et références

Notes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Fonction de compte des nombres premiers

Sommaire

Historique

Algorithmes d'évaluation de π(x)

Autres fonctions de compte des nombres premiers

Inégalités

L'hypothèse de Riemann

Relation avec les sommes de nombres premiers

Table de π(x), x / ln x, et Li(x)

Formules pour les fonctions de compte des nombres premiers

Notes et références

Notes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link