Funkce počítání Prime - Prime-counting function

v matematika, funkce počítání prvočísel je funkce počítání počtu prvočísla menší nebo rovno některým reálné číslo X.^[1][2] Označuje to π(X) (nesouvisí s číslo π ).

Hodnoty π(n) pro prvních 60 kladných celých čísel

Dějiny

Velký zájem o teorie čísel je tempo růstu funkce počítání prvočísel.^[3][4] to bylo domnělý na konci 18. století do Gauss a tím Legendre být přibližně

${ displaystyle { frac {x} { ln (x)}}}$

V tom smyslu, že

${ displaystyle lim _ {x rightarrow infty} { frac { pi (x)} {x / ln (x)}} = 1.}$

Toto prohlášení je věta o prvočísle. Ekvivalentní prohlášení je

${ displaystyle lim _ {x rightarrow infty} pi (x) / operatorname {li} (x) = 1 !}$

kde li je logaritmický integrál funkce. Věta o prvočísle byla poprvé prokázána v roce 1896 Jacques Hadamard a tím Charles de la Vallée Poussin samostatně, s využitím vlastností Funkce Riemann zeta představil Riemann v roce 1859. Důkazy věty o prvočísle nepoužívající funkci zeta nebo komplexní analýza byly nalezeny kolem roku 1948 Atle Selberg a tím Paul Erdős (z větší části samostatně).^[5]

V roce 1899 de la Vallée Poussin to dokázal (viz také Věta 23 z^[6])

${ displaystyle pi (x) = operatorname {li} (x) + O left (xe ^ {- a { sqrt { ln x}}} right) quad { text {as}} x do infty}$

pro nějakou pozitivní konstantu A. Tady, Ó(...) je velký Ó notace.

Přesnější odhady ${ displaystyle pi (x) !}$ jsou nyní známy. Například v roce 2002 Kevin Ford dokázal to^[7]

${ displaystyle pi (x) = operatorname {li} (x) + O left (x exp left (-0.2098 ( ln x) ^ { frac {3} {5}} ( ln ln x) ^ {- { frac {1} {5}}} vpravo) vpravo)}$.

V roce 2016 Tim Trudgian prokázal výslovnou horní hranici rozdílu mezi ${ displaystyle pi (x)}$ a ${ displaystyle operatorname {li} (x)}$:

${ displaystyle { big |} pi (x) - operatorname {li} (x) { big |} leq 0,2795 { frac {x} {( ln x) ^ {3/4}}} exp left (- { sqrt { frac { ln x} {6,455}}} right)}$

pro ${ displaystyle x geq 229}$.^[8]

Pro většinu hodnot ${ displaystyle x}$ nás zajímá (tj. kdy ${ displaystyle x}$ není nepřiměřeně velký) ${ displaystyle operatorname {li} (x) !}$ je větší než ${ displaystyle pi (x) !}$. Nicméně, ${ displaystyle pi (x) - operatorname {li} (x)}$ je známo, že mění znaménko nekonečně mnohokrát. Diskuse o tom viz Šikmé číslo.

Přesná forma

Zásadního významu, Bernhard Riemann dokázal že funkce počítání prvočísel je přesně^[9]

${ displaystyle pi (x) = operatorname {R} (x) - sum _ { rho} operatorname {R} (x ^ { rho})}$

kde

${ displaystyle operatorname {R} (x) = součet _ {n = 1} ^ { infty} { frac { mu (n)} {n}} operatorname {li} (x ^ {1 / n})}$,

μ(n) je Möbiova funkce, li (X) je logaritmická integrální funkce, ρ indexuje každou nulu z Funkce Riemann zeta, a li (X^{ρ / n}) není hodnocena pomocí a větev řez ale místo toho považováno za Ei (ρ/n ln X) kde Ei (X) je exponenciální integrál. Ekvivalentně, pokud se shromáždí triviální nuly a vezme se součet pouze přes netriviální nuly ρ z Funkce Riemann zeta, pak π(X) lze psát

${ displaystyle pi (x) = operatorname {R} (x) - suma _ { rho} operatorname {R} (x ^ { rho}) - { frac {1} { ln {x }}} + { frac {1} { pi}} arctan { frac { pi} { ln {x}}}}$.

The Riemannova hypotéza naznačuje, že každá taková netriviální nula leží spolu Re(s) = 1/2.

Tabulka π(X), X / ln Xa li (X)

Tabulka ukazuje, jak tyto tři funkce fungují π(X), X / ln X a li (X) porovnat při síle 10. Viz také,^[3][10][11] a^[12]

X	π(X)	π(X) − X / ln X	li (X) − π(X)	X / π(X)	x / ln x% chyba
10	4	−0.3	2.2	2.500	-7.5%
102	25	3.3	5.1	4.000	13.20%
103	168	23	10	5.952	13.69%
104	1,229	143	17	8.137	11.64%
105	9,592	906	38	10.425	9.45%
106	78,498	6,116	130	12.740	7.79%
107	664,579	44,158	339	15.047	6.64%
108	5,761,455	332,774	754	17.357	5.78%
109	50,847,534	2,592,592	1,701	19.667	5.10%
1010	455,052,511	20,758,029	3,104	21.975	4.56%
1011	4,118,054,813	169,923,159	11,588	24.283	4.13%
1012	37,607,912,018	1,416,705,193	38,263	26.590	3.77%
1013	346,065,536,839	11,992,858,452	108,971	28.896	3.47%
1014	3,204,941,750,802	102,838,308,636	314,890	31.202	3.21%
1015	29,844,570,422,669	891,604,962,452	1,052,619	33.507	2.99%
1016	279,238,341,033,925	7,804,289,844,393	3,214,632	35.812	2.79%
1017	2,623,557,157,654,233	68,883,734,693,281	7,956,589	38.116	2.63%
1018	24,739,954,287,740,860	612,483,070,893,536	21,949,555	40.420	2.48%
1019	234,057,667,276,344,607	5,481,624,169,369,960	99,877,775	42.725	2.34%
1020	2,220,819,602,560,918,840	49,347,193,044,659,701	222,744,644	45.028	2.22%
1021	21,127,269,486,018,731,928	446,579,871,578,168,707	597,394,254	47.332	2.11%
1022	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1,932,355,208	49.636	2.02%
1023	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	7,250,186,216	51.939	1.93%
1024	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	17,146,907,278	54.243	1.84%
1025	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	55,160,980,939	56.546	1.77%
1026	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%
1027	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%

Graf ukazující poměr funkce počítání prvočísel π(X) na dvě jeho aproximace, X/ ln X a Li (X). Tak jako X zvyšuje (pozn X osa je logaritmická), oba poměry mají sklon k 1. Poměr pro X/ ln X konverguje shora velmi pomalu, zatímco poměr pro Li (X) konverguje zespodu rychleji.

V On-line encyklopedie celočíselných sekvencí, π(X) sloupec je sekvence OEIS: A006880, π(X) − X/ ln X je sekvence OEIS: A057835, a li (X) − π(X) je sekvence OEIS: A057752.

Hodnota pro π(10²⁴) původně vypočítal J. Buethe, J. Franke, A. Jost a T. Kleinjung za předpokladu Riemannova hypotéza.^[13]Později to bylo bezpodmínečně ověřeno výpočtem D. J. Platta.^[14]Hodnota pro π(10²⁵) je kvůli J. Buethe, J. Franke, A. Jost a T. Kleinjung.^[15] Hodnota pro π(10²⁶) vypočítal D. B. Staple.^[16] Všechny ostatní předchozí položky v této tabulce byly také ověřeny jako součást této práce.

Hodnota pro 10²⁷ byl publikován v roce 2015 Davidem Baughem a Kim Walischem.^[17]

Algoritmy pro hodnocení π(X)

Jednoduchý způsob, jak najít ${ displaystyle pi (x)}$, pokud ${ displaystyle x}$ není příliš velký, je použít síto Eratosthenes vyrábět prvočísla menší nebo rovna ${ displaystyle x}$ a pak je spočítat.

Propracovanější způsob hledání ${ displaystyle pi (x)}$ je to kvůli Legendre (za použití zásada začlenění - vyloučení ): daný ${ displaystyle x}$, pokud ${ displaystyle p_ {1}, p_ {2}, ldots, p_ {n}}$ jsou odlišná prvočísla, pak je počet celých čísel menší nebo roven ${ displaystyle x}$ které jsou dělitelné č ${ displaystyle p_ {i}}$ je

${ displaystyle lfloor x rfloor - součet _ {i} vlevo lfloor { frac {x} {p_ {i}}} vpravo rfloor + sum _ {i$

(kde ${ displaystyle lfloor {x} rfloor}$ označuje funkce podlahy ). Toto číslo se tedy rovná

${ displaystyle pi (x) - pi vlevo ({ sqrt {x}} vpravo) +1}$

když čísla ${ displaystyle p_ {1}, p_ {2}, ldots, p_ {n}}$ jsou prvočísla menší nebo rovná druhé odmocnině z ${ displaystyle x}$.

Alisselův-Lehmerův algoritmus

V sérii článků publikovaných v letech 1870 až 1885 Ernst Meissel popsal (a použil) praktický kombinatorický způsob hodnocení ${ displaystyle pi (x)}$. Nechat ${ displaystyle p_ {1}}$, ${ displaystyle p_ {2}, ldots, p_ {n}}$ být první ${ displaystyle n}$ připraví a označí ${ displaystyle Phi (m, n)}$ počet přirozených čísel ne větší než ${ displaystyle m}$ které jsou dělitelné č ${ displaystyle p_ {i}}$. Pak

${ displaystyle Phi (m, n) = Phi (m, n-1) - Phi left ({ frac {m} {p_ {n}}}, n-1 right).}$

Vzhledem k přirozenému číslu ${ displaystyle m}$, pokud ${ displaystyle n = pi left ({ sqrt [{3}] {m}} right)}$ a pokud ${ displaystyle mu = pi vlevo ({ sqrt {m}} vpravo) -n}$, pak

${ displaystyle pi (m) = Phi (m, n) + n ( mu +1) + { frac { mu ^ {2} - mu} {2}} - 1- součet _ { k = 1} ^ { mu} pi left ({ frac {m} {p_ {n + k}}} right).}$

Pomocí tohoto přístupu Meissel vypočítal ${ displaystyle pi (x)}$, pro ${ displaystyle x}$ rovná se 5×10⁵, 10⁶, 10⁷a 10⁸.

V roce 1959 Derrick Henry Lehmer rozšířená a zjednodušená Meisselova metoda. Definujte, opravdu ${ displaystyle m}$ a pro přirozená čísla ${ displaystyle n}$ a ${ displaystyle k}$, ${ displaystyle P_ {k} (m, n)}$ protože počet čísel není větší než m přesně k hlavní faktory, všechny větší než ${ displaystyle p_ {n}}$. Dále nastavit ${ displaystyle P_ {0} (m, n) = 1}$. Pak

${ displaystyle Phi (m, n) = součet _ {k = 0} ^ {+ infty} P_ {k} (m, n)}$

kde součet má pouze konečně mnoho nenulových podmínek. Nechat ${ displaystyle y}$ označit celé číslo takové, že ${ displaystyle { sqrt [{3}] {m}} leq y leq { sqrt {m}}}$a nastavit ${ displaystyle n = pi (y)}$. Pak ${ displaystyle P_ {1} (m, n) = pi (m) -n}$ a ${ displaystyle P_ {k} (m, n) = 0}$ když ${ displaystyle k}$ ≥ 3. Proto

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

Výpočet ${ displaystyle P_ {2} (m, n)}$ lze získat tímto způsobem:

${ displaystyle P_ {2} (m, n) = součet _ {y$

,

kde součet přesahuje prvočísla.

Na druhou stranu, výpočet ${ displaystyle Phi (m, n)}$ lze provést pomocí následujících pravidel:

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

Pomocí jeho metody a IBM 701, Lehmer dokázal vypočítat ${ displaystyle pi left (10 ^ {10} right)}$.

Další vylepšení této metody provedli Lagarias, Miller, Odlyzko, Deléglise a Rivat.^[18]

Další funkce počítání prvočísel

Používají se také další funkce počítání prvočísel, protože je s nimi pohodlnější pracovat. Jedním z nich je Riemannova funkce počítání prvočísel, obvykle označovaná jako ${ displaystyle Pi _ {0} (x)}$ nebo ${ displaystyle J_ {0} (x)}$. To má skoky o 1 /n pro hlavní síly pⁿ, přičemž při diskontinuitách má hodnotu na půli cesty mezi oběma stranami. Tento přidaný detail se používá, protože pak může být funkce definována inverzí Mellinova transformace. Formálně můžeme definovat ${ displaystyle Pi _ {0} (x)}$ podle

${ displaystyle Pi _ {0} (x) = { frac {1} {2}} { bigg (} sum _ {p ^ {n}$

kde p je prime.

Můžeme také psát

${ displaystyle Pi _ {0} (x) = součet _ {n = 2} ^ {x} { frac { Lambda (n)} { ln n}} - { frac {1} {2 }} { frac { Lambda (x)} { ln x}} = sum _ {n = 1} ^ { infty} { frac {1} {n}} pi _ {0} (x ^ {1 / n})}$

kde Λ (n) je von Mangoldtova funkce a

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

The Möbioův inverzní vzorec pak dává

${ displaystyle pi _ {0} (x) = součet _ {n = 1} ^ { infty} { frac { mu (n)} {n}} Pi _ {0} (x ^ { 1 / n})}$

Znát vztah mezi protokolem Funkce Riemann zeta a von Mangoldtova funkce ${ displaystyle Lambda}$a pomocí Perronův vzorec my máme

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

The Čebyševova funkce váží prvočísla nebo hlavní síly pⁿ podle ln (p):

${ displaystyle theta (x) = součet _ {p leq x} ln p}$

${ displaystyle psi (x) = součet _ {p ^ {n} leq x} ln p = součet _ {n = 1} ^ { infty} theta (x ^ {1 / n}) = sum _ {n leq x} Lambda (n).}$

Vzorce pro funkce počítání prvočísel

Vzorce pro funkce počítání prvočísel přicházejí ve dvou druzích: aritmetické vzorce a analytické vzorce. Analytické vzorce pro počítání prime byly poprvé použity k prokázání věta o prvočísle. Vycházejí z práce Riemanna a von Mangoldt a jsou obecně známé jako explicitní vzorce.^[19]

Máme následující výraz pro ψ:

${ displaystyle psi _ {0} (x) = x- součet _ { rho} { frac {x ^ { rho}} { rho}} - ln 2 pi - { frac {1 } {2}} ln (1-x ^ {- 2}),}$

kde

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

Zde ρ jsou nuly Funkce Riemann zeta v kritickém pásu, kde je skutečná část ρ mezi nulou a jednou. Vzorec je platný pro hodnoty X větší než jedna, což je oblast zájmu. Součet přes kořeny je podmíněně konvergentní a měl by být vzat v pořadí zvýšení absolutní hodnoty imaginární části. Všimněte si, že stejný součet za triviální kořeny dává poslední subtrahend ve vzorci.

Pro ${ displaystyle Pi _ {0} (x)}$ máme složitější vzorec

${ displaystyle Pi _ {0} (x) = operatorname {li} (x) - součet _ { rho} operatorname {li} (x ^ { rho}) - ln 2+ int _ {x} ^ { infty} { frac {dt} {t (t ^ {2} -1) ln t}}.}$

Riemannova explicitní formule využívající prvních 200 netriviálních nul funkce zeta

Vzorec opět platí pro X > 1, zatímco ρ jsou netriviální nuly funkce zeta seřazené podle jejich absolutní hodnoty a druhý integrál, vzatý se znaménkem mínus, je opět stejný součet, ale přes triviální nuly. První termín li (X) je obvyklý logaritmická integrální funkce; výraz li (X^ρ) ve druhém termínu je třeba považovat za Ei (ρ lnX), kde Ei je analytické pokračování z exponenciální integrál funkce od záporných real do složité roviny s větvením podél pozitivních real.

Tím pádem, Möbioův inverzní vzorec nám dává^[20]

${ displaystyle pi _ {0} (x) = operatorname {R} (x) - sum _ { rho} operatorname {R} (x ^ { rho}) - { frac {1} { ln x}} + { frac {1} { pi}} arctan { frac { pi} { ln x}}}$

platný pro X > 1, kde

${ displaystyle operatorname {R} (x) = součet _ {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)}}}$

je Riemannova R-funkce^[21] a μ(n) je Möbiova funkce. Druhá řada pro něj je známá jako Gram série^[22][23]. Protože ${ displaystyle ln (x)$ pro všechny ${ displaystyle x> 0}$, tato řada konverguje pro všechny pozitivní X ve srovnání se sérií pro ${ displaystyle e ^ {x}}$.

Funkce Δ (červená čára) na stupnici protokolu

Součet nad netriviálními nulami nula ve vzorci pro ${ displaystyle pi _ {0} (x)}$ popisuje fluktuace ${ displaystyle pi _ {0} (x),}$ zatímco zbývající výrazy dávají „hladkou“ část funkce počítání prvočísel,^[24] takže lze použít

${ displaystyle operatorname {R} (x) - { frac {1} { ln x}} + { frac {1} { pi}} arctan { frac { pi} { ln x} }}$

jako nejlepší odhadce ${ displaystyle pi (x)}$ pro X > 1.

Amplituda „hlučné“ části je heuristicky asi ${ displaystyle { sqrt {x}} / ln x,}$ takže fluktuace distribuce prvočísel mohou být jasně vyjádřeny funkcí Δ:

${ displaystyle Delta (x) = left ( pi _ {0} (x) - operatorname {R} (x) + { frac {1} { ln x}} - { frac {1} { pi}} arctan { frac { pi} { ln x}} right) { frac { ln x} { sqrt {x}}}.}$

Rozsáhlá tabulka hodnot Δ (X) je k dispozici.^[11]

Nerovnosti

Zde jsou některé užitečné nerovnosti pro π(X).

${ displaystyle { frac {x} { ln x}} < pi (x) <1,25506 { frac {x} { ln x}}}$

pro X ≥ 17.

Levá nerovnost platí pro x ≥ 17 a pravá nerovnost platí pro x> 1. Konstanta 1,25506 je ${ displaystyle { frac {30 ln 113} {113}}}$ na 5 desetinných míst, jako ${ displaystyle { frac { pi (x) ln x} {x}}}$ má maximální hodnotu na x = 113.^[25]

Pierre Dusart prokázáno v roce 2010:

${ displaystyle { frac {x} { ln x-1}} < pi (x)}$ pro ${ displaystyle x geq 5393}$, a

${ displaystyle pi (x) <{ frac {x} { ln x-1,1}}}$ pro ${ displaystyle x geq 60184}$.^[26]

Zde jsou některé nerovnosti pro nth prime, p_n. Horní hranice je způsobena Rosserem (1941),^[27] spodní Dusart (1999):^[28]

${ Displaystyle n ( ln (n ln n) -1)$ pro n ≥ 6.

Levá nerovnost platí pro n ≥ 2 a pravá nerovnost platí pro n ≥ 6.

Aproximace pro nth prvočíslo je

${ displaystyle p_ {n} = n ( ln (n ln n) -1) + { frac {n ( ln ln n-2)} { ln n}} + O left ({ frac {n ( ln ln n) ^ {2}} {( ln n) ^ {2}}} vpravo).}$

Ramanujan^[29] prokázal, že nerovnost

${ displaystyle pi (x) ^ {2} <{ frac {ex} { log x}} pi { bigg (} { frac {x} {e}} { bigg)}}$

platí pro všechny dostatečně velké hodnoty ${ displaystyle x}$.

v ^[26], Dusart prokázal (tvrzení 6.6), že pro ${ displaystyle n geq 688383}$,

${ Displaystyle p_ {n} leq n left ( ln n + ln ln n-1 + { frac { ln ln n-2} { ln n}} right)}$ ,

a (návrh 6.7), že pro ${ displaystyle n geq 3}$,

${ Displaystyle p_ {n} geq n vlevo ( ln n + ln ln n-1 + { frac { ln ln n-2.1} { ln n}} vpravo)}$ .

Více nedávno, Dusart^[30]prokázal (Věta 5.1), že pro ${ displaystyle x> 1}$,

${ displaystyle pi (x) leq { frac {x} { ln x}} vlevo (1 + { frac {1} { ln x}} + { frac {2} { ln ^ {2} x}} + { frac {7.59} { ln ^ {3} x}} vpravo)}$ ,

a to pro ${ displaystyle x geq 88789}$,

${ displaystyle pi (x)> { frac {x} { ln x}} vlevo (1 + { frac {1} { ln x}} + { frac {2} { ln ^ { 2} x}} vpravo)}$ .

Riemannova hypotéza

The Riemannova hypotéza je ekvivalentem mnohem přísnějšího vztahu k chybě v odhadu pro ${ displaystyle pi (x)}$, a tedy k pravidelnější distribuci prvočísel,

${ displaystyle pi (x) = operatorname {li} (x) + O ({ sqrt {x}} log {x}).}$

Konkrétně^[31]

${ displaystyle | pi (x) - operatorname {li} (x) | <{ frac {1} {8 pi}} { sqrt {x}} , log {x}, qquad { text {pro všechny}} x geq 2657.}$

Viz také

• Foiasova konstanta
• Bertrandův postulát
• Oppermannova domněnka
• Ramanujan prime

Reference

externí odkazy

• Chris Caldwell, Nth Prime Page na Prime Stránky.
• Tomás Oliveira e Silva, Tabulky funkcí počítání prvočísel.