Funcția de distribuție a numerelor prime

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 septembrie 2021; verificările necesită 2 modificări .

În matematică , funcția de distribuție a primelor , sau funcția pi , este o funcție egală cu numărul de numere prime mai mici sau egale cu numărul real x . [1] [2] Se notează (nu are nimic de-a face cu pi ). $\pi(x)$ $\pi(x)$

Istorie

De mare interes în teoria numerelor este rata de creștere a funcției pi. [3] [4] La sfârșitul secolului al XVIII-lea, Gauss și Legendre au sugerat că funcția pi este estimată ca

{\frac {x}{\ln x}}

in sensul că

\lim \limits _{{x\to +\infty }}{\frac {\pi (x)}{x/\ln x}}=1.

Această afirmație este teorema distribuției numerelor prime . Este echivalent cu afirmația

\lim \limits _{{x\to +\infty }}{\frac {\pi (x)}{\operatorname {li}(x)))=1

unde este logaritmul integral al lui . Teorema numerelor prime a fost demonstrată pentru prima dată în 1896 de Jacques Hadamard și independent de Vallée-Poussin , folosind funcția zeta Riemann introdusă de Riemann în 1859. $\operatorname {li}$

Mai exact, creșterea este acum descrisă ca $\pi(x)$

\pi (x)=\operatorname {li} (x)+O{\bigl (}xe^{-{\sqrt {\ln x))/15}{\bigr ))

unde denotă O mare . Când x nu este foarte mare mai mare decât , diferența își schimbă semnul de un număr infinit de ori, cel mai mic număr natural pentru care are loc o schimbare de semn se numește număr Skewes . $O$ $\operatorname {li} (x)$ $\pi(x)$ $\pi (x)-\operatorname {li} (x)$

Dovezi ale teoremei numerelor prime care nu folosesc funcția zeta sau analiza complexă au fost găsite în 1948 de către Atle Selberg și Paul Erdős (în mare parte independent). [5]

Tabele pentru funcția pi, x / ln x și li( x )

Următorul tabel arată creșterea funcțiilor în puteri de 10 [3] [6] [7] [8] . $\pi (x),{\frac {x}{\ln x)),\operatorname {li} (x)$

X	π( x )	π( x ) − x / log x	li( x ) − π( x )	x / π( x )	π( x )/x (fracția de numere prime)
zece	patru	−0,3	2.2	2.500	40%
10 2	25	3.3	5.1	4.000	25%
10 3	168	23	zece	5.952	16,8%
10 4	1 229	143	17	8.137	12,3%
10 5	9 592	906	38	10.425	9,59%
10 6	78 498	6 116	130	12.740	7,85%
10 7	664 579	44 158	339	15.047	6,65%
10 8	5 761 455	332 774	754	17.357	5,76%
10 9	50 847 534	2 592 592	1 701	19.667	5,08%
10 10	455 052 511	20 758 029	3 104	21.975	4,55%
10 11	4 118 054 813	169 923 159	11 588	24.283	4,12%
10 12	37 607 912 018	1 416 705 193	38 263	26.590	3,76%
10 13	346 065 536 839	11 992 858 452	108 971	28.896	3,46%
10 14	3 204 941 750 802	102 838 308 636	314 890	31.202	3,20%
10 15	29 844 570 422 669	891 604 962 452	1 052 619	33.507	2,98%
10 16	279 238 341 033 925	7 804 289 844 393	3 214 632	35.812	2,79%
10 17	2 623 557 157 654 233	68 883 734 693 281	7 956 589	38.116	2,62%
10 18	24 739 954 287 740 860	612 483 070 893 536	21 949 555	40.420	2,47%
10 19	234 057 667 276 344 607	5 481 624 169 369 960	99 877 775	42.725	2,34%
10 20	2220 819 602 560 918 840	49 347 193 044 659 701	222 744 644	45.028	2,22%
10 21	21 127 269 486 018 731 928	446 579 871 578 168 707	597 394 254	47.332	2,11%
10 22	201 467 286 689 315 906 290	4 060 704 006 019 620 994	1 932 355 208	49.636	2,01%
10 23	1 925 320 391 606 803 968 923	37 083 513 766 578 631 309	7 250 186 216	51.939	1,92%
10 24	18 435 599 767 349 200 867 866	339 996 354 713 708 049 069	17 146 907 278	54.243	1,84%
10 25	176 846 309 399 143 769 411 680	3 128 516 637 843 038 351 228	55 160 980 939	56.546	1,77%
10 26	1 699 246 750 872 437 141 327 603	28 883 358 936 853 188 823 261	155 891 678 121	58.850	1,70%
10 27	16 352 460 426 841 680 446 427 399	267 479 615 610 131 274 163 365	508 666 658 006	61.153	1,64%

În OEIS , prima coloană de valori este secvența A006880 , este secvența A057835 și este secvența A057752 . $\pi(x)$ $\pi (x)-\left\lfloor {\frac {x}{\ln x}}+0{,}5\right\rfloor$ $\lfloor \operatorname {li}(x)+0{,}5\rfloor -\pi (x)$

Algoritmi pentru calcularea funcției pi

O modalitate ușoară de a găsi , dacă nu foarte mare, este să folosești sita lui Eratosthenes care dă numere prime care nu le depășesc și le numără. $\pi(x)$ $X$ $X$

O modalitate mai atentă de calcul a fost oferită de Legendre : dat , dacă sunt numere prime diferite, atunci numărul de numere întregi care nu depășesc și nu sunt oricum divizibile cu $\pi(x)$ $X$ $p_{1},p_{2},\ldots ,p_{k}$ $X$ $p_{i}$

\lfloor x\rfloor -\sum _{{i}}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{{i<j}}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{{i<j<k}}\left\lfloor {\frac {x}{p_{i}p_ {j}p_{k}}}\right\rfloor +\cdots

(unde denotă partea întreagă ). Prin urmare, numărul rezultat este $\lfloor \cdots \rfloor$

\pi (x)-\pi \left({\sqrt {x}}\right)+1

dacă numerele sunt toate numere prime care nu depăşesc . $p_{1},p_{2},\ldots ,p_{k}$ $\sqrt{x}$

În 1870-1885, într-o serie de articole, Ernst Meissel a descris (și a folosit) un mod practic combinatoriu de calcul . Fie primele numere prime, indică numărul de numere naturale care nu depășesc , care nu sunt divizibile cu niciun . Apoi $\pi(x)$ $p_{1},p_{2},\ldots ,p_{n}$ $n$ $\phi(m,n)$ $m$ $p_{i}$

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

Luați naturalul , dacă și dacă , atunci $m$ $n=\pi \left({\sqrt[ {3}]{m}}\right)$ $\mu =\pi \left({\sqrt {m}}\right)-n$

\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))))\dreapta)

Folosind această abordare, Meissel a calculat pentru . $\pi(x)$ $x=5\cdot 10^{5};10^{6};10^{7};10^{8}$

În 1959, Derrick Henry Lehmer a extins și simplificat metoda Meissel. Să definim, pentru numere reale și pentru numere naturale , ca numărul de numere care nu depășesc m având exact k factori primi, toți care depășesc . În plus, să punem . Apoi $m$ $n,k$ $P_{k}(m,n)$ $p_n$ $P_{0}(m,n)=1$

\Phi (m,n)=\sum _{{k=0}}^{{+\infty }}P_{k}(m,n)

unde suma are, evident, întotdeauna un număr finit de termeni nenuli. Fie un număr întreg astfel încât , și set . Apoi și la . prin urmare $y$ ${\sqrt[ {3}]{m}}\leqslant y\leqslant {\sqrt {m}}$ $n=\pi (y)$ $P_{1}(m,n)=\pi(m)-n$ $P_{k}(m,n)=0$ $k\geqslant 3$

\pi (m)=\Phi (m,n)+n-1-P_{2}(m,n)

Calculul poate fi obtinut in felul urmator: $P_{2}(m,n)$

P_{2}(m,n)=\sum _{{y<p\leqslant {\sqrt {m))))\left(\pi \left({\frac mp}\right)-\pi (p )+1\dreapta)

Pe de altă parte, calculul se poate face folosind următoarele reguli: $\phi(m,n)$

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

Folosind această metodă și un IBM 701, Lemaire a putut să calculeze . $\pi \left(10^{{10}}\right)$

Alte îmbunătățiri ale acestei metode au fost aduse de Lagarias, Miller, Odlyzko, Deleglise și Rivat. [9]

Matematicianul chinez Hwang Cheng a folosit următoarele identități: [10]

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

J(x)=\sum _{{n=1}}^{{\infty }}{\frac {\pi (x^{{1/n}})}{n}}

și, presupunând , efectuând transformarea Laplace a ambelor părți și aplicând suma unei progresii geometrice cu , s-a obținut expresia: $x=e^{t}$ $e^{{n\Theta}}$

{\frac {1}{2{\pi }i}}\int _{{ci\infty }}^{{c+i\infty }}g(s)t^{{s}}\,ds= \pi (t)

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

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

Alte funcții de numărare a primelor

Alte funcții care numără numere prime sunt, de asemenea, folosite, deoarece sunt mai convenabile de lucrat. Una dintre ele este funcția Riemann, adesea notată ca sau . Salt cu 1/n pentru puterile primelor , iar în punctul de salt valoarea sa este jumătate din suma valorilor de pe ambele părți ale lui . Aceste detalii suplimentare sunt necesare pentru a putea fi determinate prin transformarea inversă Mellin . În mod formal, definim ca $\Pi _{0}(x)$ $J_{0}(x)$ $p^{n}$ $X$ $X$ $\Pi _{0}(x)$

\Pi _{0}(x)={\frac 12}{\bigg (}\sum _{{p^{n}<x}}{\frac 1n}\ +\sum _{{p^{n }\leq x}}{\frac 1n}{\bigg )}

unde p este prim.

Putem si scrie

\Pi _{0}(x)=\sum \limits _{{n=2}}^{x}{\frac {\Lambda (n)}{\ln n}}-{\frac 12}{\ frac {\Lambda (x)}{\ln x}}=\sum _{{n=1}}^{\infty }{\frac 1n}\pi _{0}({\sqrt[ {n}] {X}})

unde este funcţia Mangoldt şi $\Lambda(n)$

\pi _{0}(x)=\lim _{{\varepsilon \rightarrow 0}}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}2}.

Formula de inversare a lui Möbius dă

\pi _{{0}}(x)=\sum _{{n=1}}^{\infty }{\frac {\mu (n)}n}\Pi _{0}({\sqrt[ {n}]{x}})

Folosind relația cunoscută dintre logaritmul funcției zeta Riemann și funcția Mangoldt și folosind formula Perron , obținem $\lambda$

\ln \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{{-s-1}}\,dx

Funcția Riemann are o funcție generatoare

\sum _{n=1}^{\infty }\Pi _{0}(n)x^{n}=\sum _{a=2}^{\infty }{\frac {x^ {a}}{1-x}}-{\frac {1}{2}}\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }{\frac {x^{ab}}{1-x}}+{\frac {1}{3}}\sum _{a=2}^{\infty }\sum _{b=2}^{\infty } \sum _{c=2}^{\infty }{\frac {x^{abc}}{1-x}}-{\frac {1}{4}}\sum _{a=2}^{ \infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }{\frac {x^{abcd }}{1-x}}+\cdots

Funcțiile Chebyshev sunt funcții care calculează puteri ale numerelor prime cu greutate : $p^{n}$ $\ln p$

\theta (x)=\sum _{{p\leqslant x}}\ln p

\psi (x)=\sum _{{p^{n}\leqslant x}}\ln p=\sum _{{n=1}}^{\infty }\theta ({\sqrt[ {n} ]{x}})=\sum _{{n\leqslant x}}\Lambda (n).

Formule pentru funcții care numără numere prime

Formulele pentru funcțiile care numără numere prime sunt de două tipuri: formule aritmetice și formule analitice. Formulele analitice pentru astfel de funcții au fost folosite pentru a demonstra teorema numerelor prime . Ele provin din lucrările lui Riemann și Mangoldt și sunt în general cunoscute ca formule explicite . [unsprezece]

Există următoarea expresie pentru funcția Chebyshev: $\psi$

\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac 12}\ln( 1-x^{{-2}})

Unde

\psi _{0}(x)=\lim _{{\varepsilon \rightarrow 0}}{\frac {\psi (x-\varepsilon )+\psi (x+\varepsilon )}2}.

Aici zerourile funcției zeta rulează în banda critică, unde partea reală se află între zero și unu. Formula este valabilă pentru toată lumea . Seria în termeni de rădăcini converge condiționat și poate fi luată în ordinea valorii absolute a creșterii părții imaginare a rădăcinilor. Rețineți că o sumă similară peste rădăcini triviale dă ultimul termen din formulă. $\rho$ $\rho$ $x>1$

Căci avem următoarea formulă complexă $\scriptstyle \Pi _{0}(x)$

\Pi _{0}(x)=\operatorname {li}(x)-\sum _{{\rho }}\operatorname {li}(x^{{\rho }})-\ln 2+\int _{x}^{\infty }{\frac {dt}{t(t^{2}-1)\ln t}}.

Din nou, formula este adevărată pentru toate , unde sunt zerouri netriviale ale funcției zeta, ordonate după valoarea lor absolută și, din nou, ultima integrală este luată cu semnul minus și este aceeași sumă, dar peste zerouri triviale. Expresia din al doilea termen poate fi considerată ca , unde este continuarea analitică a funcției exponențiale integrale la planul complex cu o ramură tăiată de-a lungul liniei . $x>1$ $\rho$ $\operatorname {li}(x^{{\rho }})$ $\operatorname {Ei}(\rho \ln x)$ $\operatorname {Ei}$ $x<0$

Astfel, formula de inversare a lui Möbius ne dă [12]

\pi _{{0}}(x)=\operatorname {R}(x)-\sum _{{\rho }}\operatorname {R}(x^{{\rho }})-{\frac { 1}{\ln x))+{\frac {1}{\pi )){\mathop ({\mathrm {arctg)))){\frac {\pi }{\ln x))

corect pentru , unde $x>1$

\operatorname {R}(x)=\sum _{{n=1}}^{{\infty }}{\frac {\mu (n)}{n}}\operatorname {li}(x^{{ 1/n)))=1+\sum _{{k=1}}^{\infty }{\frac {(\ln x)^{k}}{k!k\zeta (k+1)} }

se numește funcția R, tot după Riemann. [13] Ultima serie din ea este cunoscută ca seria Gram [14] și converge pentru toate . $x>0$

Suma peste zerourile netriviale ale funcției zeta din formula pentru descrie fluctuațiile lui , în timp ce termenii rămași dau partea netedă a funcției pi, [15] astfel încât să putem folosi $\pi _{0}(x)$ $\pi _{0}(x)$

\operatorname {R}(x)-{\frac {1}{\ln x}}+{\frac {1}{\pi }}{\mathop {{\mathrm {arctg}}}}{\frac { \pi }{\ln x}}

ca cea mai bună aproximare pentru pentru . $\pi(x)$ $x>1$

Amplitudinea părții „zgomotoase” este estimată euristic ca , astfel încât fluctuațiile în distribuția primelor pot fi reprezentate explicit de funcția - ${\sqrt x}/\ln x$ $\Delta$

\Delta (x)=\left(\pi _{0}(x)-\operatorname {R}(x)+{\frac {1}{\ln x}}-{\frac {1}{\pi }}{\mathop {{\mathrm {arctg}}}}{\frac {\pi }{\ln x}}\right){\frac {\ln x}{{\sqrt x}}}.

Tabelele cu valori extinse sunt disponibile aici. [7] $\Delta (x)$

Inegalități

Iată câteva inegalități pentru . $\pi(x)$

{\frac {x}{\ln x}}<\pi (x)<1{,}25506\cdot {\frac {x}{\ln x}}\qquad x\geqslant 17.

Inegalitatea din stânga este satisfăcută pentru , iar cea din dreapta, pentru [16] $x\geqslant 17$ $x>1.$

Inegalități pentru numărul prim : $n$ $p_n$

n\ln n+n\ln \ln n-3/2\cdot n<p_{n}<n\ln n+n\ln \ln n,\n\geqslant 6.

Inegalitatea din stânga este adevărată pentru , iar cea dreaptă, pentru . $n \geqslant 2$ $n\geqslant 6$

Următoarele asimptotice sunt valabile pentru al -lea număr prim : $n$ $p_n$

p_{n}=n\ln n\left(1+{\frac {\ln \ln n-1}{\ln n))+{\frac {\ln \ln n-2}{\ ln ^{2}n))+{\frac {-1/2\ln ^{2}\ln n+3\ln \ln n-11/2}{\ln ^{3}n))+O \left({\frac {\ln ^{3}\ln n}{\ln ^{4}n}}\dreapta)\right)

Ipoteza Riemann

Ipoteza Riemann este echivalentă cu o limită mai precisă a erorii de aproximare prin logaritmul integral și, prin urmare, cu o distribuție mai regulată a numerelor prime $\pi(x)$

\pi (x)=\operatorname {li}(x)+O({\sqrt {x}}\ln x).

În special, [17]

|\pi (x)-\operatorname {li}(x)|<{\frac {1}{8\pi }}{\sqrt {x}}\,\ln x,\qquad x\geqslant 2657.

Vezi și

Note

↑ Bach, Eric; Shallit, Jeffrey. Secțiunea 8.8 // Teoria algoritmică a numerelor (nedefinită) . - MIT Press , 1996. - Vol. 1. - P. 234. - ISBN 0-262-02405-5 .
^ Weisstein , Eric W. Prime Counting Function pe site- ul Wolfram MathWorld .
↑ 1 2 Câte numere prime există? . Chris K. Caldwell. Consultat la 2 decembrie 2008. Arhivat din original la 20 septembrie 2012. (nedefinit)
^ Dickson, Leonard EugeneIstoria teoriei numerelor I: divizibilitate și primalitate (engleză) . - Dover Publications , 2005. - ISBN 0-486-44232-2 .
↑ K. Irlanda, M. Rosen. O introducere clasică în teoria modernă a numerelor . - Al doilea. - Springer, 1998. - ISBN 0-387-97329-X .
↑ Tabele de valori ale lui pi(x) și ale lui pi2(x) . Tomas Oliveira e Silva . Consultat la 14 septembrie 2008. Arhivat din original pe 20 septembrie 2012. (nedefinit)
↑ 1 2 Valorile lui π(x) și Δ(x) pentru diferite x-uri . Andrei V. Kulsha. Consultat la 14 septembrie 2008. Arhivat din original pe 20 septembrie 2012. (nedefinit)
↑ Un tabel cu valorile lui pi(x) . Xavier Gourdon, Pascal Sebah, Patrick Demichel. Consultat la 14 septembrie 2008. Arhivat din original pe 20 septembrie 2012. (nedefinit)
↑ Computing ?(x): Metoda Meissel, Lehmer, Lagarias, Miller, Odlyzko . Marc Deleglise și Joel Rivat, Mathematics of Computation , voi. 65 , numărul 33, ianuarie 1996, paginile 235–245. Consultat la 14 septembrie 2008. Arhivat din original pe 20 septembrie 2012. (nedefinit)
↑ Hwang H., Cheng . Demarches de la Geometrie et des Nombres de l'Universite du Bordeaux, conferința Prime Magic.
↑ Titchmarsh, EC Theory of Functions, ed . a 2-a . — Oxford University Press , 1960.
↑ Riesel, Hans; Gohl, Gunnar. Câteva calcule legate de formula numerelor prime a lui Riemann // Matematica calculului : jurnal. - Societatea Americană de Matematică, 1970. - Vol. 24 , nr. 112 . - P. 969-983 . — ISSN 0025-5718 . - doi : 10.2307/2004630 . — .
↑ Weisstein, Eric W. Riemann Prime Counting Function pe site- ul Wolfram MathWorld .
^ Weisstein , Eric W. Seria Gram pe site- ul Wolfram MathWorld .
↑ Codificarea distribuției prime prin zerourile zeta . Matthew Watkins. Consultat la 14 septembrie 2008. Arhivat din original pe 20 septembrie 2012. (nedefinit)
↑ Rosser, J. Barkley; Schoenfeld, Lowell. Formule aproximative pentru unele funcții ale numerelor prime // Illinois J. Math. : jurnal. - 1962. - Vol. 6 . - P. 64-94 . — ISSN 0019-2082 . Arhivat din original pe 28 februarie 2019.
↑ Lowell Schoenfeld. Limite mai clare pentru funcțiile Chebyshev θ( x ) și ψ( x ). II (engleză) // Matematica calculului : jurnal. - Societatea Americană de Matematică, 1976. - Vol. 30 , nr. 134 . - P. 337-360 . — ISSN 0025-5718 . - doi : 10.2307/2005976 . — .

Literatură

K. Prahar. Distribuția numerelor prime. - Mir, 1967.
V. I. Zenkin. Distribuția numerelor prime. Metode elementare. Kaliningrad, 2008.

Link -uri

Chris Caldwell, A N-a pagină principală la The Prime Pages .