Funkce počítání prvočísel
V matematice se prime počet počet funkcí je funkce, která počítá počet prvočísel méně než nebo rovna reálné číslo x . Označuje se π ( x ) (nezaměňovat s konstantou π ).
Na následujícím obrázku je znázorněna funkce π ( n ) pro celočíselné hodnoty proměnné. Zdůrazňuje přírůstky 1, které funkce prochází pokaždé, když se x rovná prvočíslu.
Historický
Od Euklida je známo, že existují prvočísla v nekonečném množství. Aby upřesnila znalosti o těchto číslech, začala teorie čísel určovat jejich rychlost růstu. Na konci XVIII th století, Gauss a Legendre se domníval, že toto množství je „v blízkosti“ x / ln ( x ) , kde ln je funkce přirozeného logaritmu .
Přesněji,
limX→+∞π(X)X/ln(X)=1{\ displaystyle \ lim _ {x \ rightarrow + \ infty} {\ frac {\ pi (x)} {x / \ ln (x)}} = 1}
|
Toto tvrzení je prvočíslo věta , ukázal nezávisle Hadamard a La Vallée Poussin v roce 1896, a to díky zeta funkci z Riemann . Ekvivalentní tvrzení je:
limX→+∞π(X)li(X)=1,{\ displaystyle \ lim _ {x \ rightarrow + \ infty} {\ frac {\ pi (x)} {{\ rm {li}} (x)}} = 1,}
kde integrální logaritmická funkce je vlastně přesnější aproximace .
li(X)=∫0Xdtln(t){\ displaystyle {\ rm {li}} (x) = \ int _ {0} ^ {x} {\ frac {\ mathrm {d} t} {\ ln (t)}}}
Důkazy o teorému prvočísel nepoužívající komplexní analýzu navrhli v roce 1948 Atle Selberg a Paul Erdős .
Algoritmy pro vyhodnocení π ( x )
Snadný způsob, jak vypočítat π ( x ) , je-li x malé číslo, je použít Eratosthenovo síto , abyste našli všechna prvočísla menší než x a poté je spočítat.
Propracovanější způsob, jak najít π ( x ), vynalezl Legendre: vzhledem k tomu, že celé číslo x , jestliže p 1 , p 2 ,…, p l jsou odlišná prvočísla, pak počet celých čísel menší nebo rovný x, které nejsou dělitelné libovolným p i je
X-∑i⌊Xpi⌋+∑i<j⌊Xpipj⌋-∑i<j<k⌊Xpipjpk⌋+⋯{\ displaystyle x- \ 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} }} \ doprava \ rfloor + \ cdots}, kde označuje
celočíselnou funkci (tento vzorec je aplikací
principu zahrnutí-vyloučení ).
⌊⋅⌋{\ displaystyle \ lfloor \ cdot \ rfloor}Toto číslo se tedy rovná:
kde čísla p 1 , p 2 ,…, p l jsou prvočísla menší nebo rovná druhé odmocnině x .
π(X)-π(X)+1{\ displaystyle \ pi (x) - \ pi \ vlevo ({\ sqrt {x}} \ vpravo) +1 \,}
V sérii prací publikovaných v letech 1870 až 1885 popsal Ernst Meissel (a použil) praktický kombinatorický způsob vyhodnocení π ( x ) . Nechť p 1 , p 2 ,…, p n jsou první n prvočísla a označme Φ ( m , n ) počet přirozených čísel menších než m, která nejsou dělitelná žádnými . Tak
pi{\ displaystyle p_ {i} \,}
Φ(m,ne)=Φ(m,ne-1)-Φ([mpne],ne-1),{\ displaystyle \ Phi (m, n) = \ Phi (m, n-1) - \ Phi \ left (\ left [{\ frac {m} {p_ {n}}} \ right], n-1 \ že jo), \,}Nechť m je přirozené číslo , jestli a jestli , pak
ne=π(m3){\ displaystyle n = \ pi \ left ({\ sqrt [{3}] {m}} \ right) \,}μ=π(m)-ne{\ displaystyle \ mu = \ pi \ left ({\ sqrt {m}} \ right) -n \,}
π(m)=Φ(m,ne)+ne(μ+1)+μ2-μ2-1-∑k=1μπ(mpne+k).{\ 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). \,}Při použití tohoto přístupu, Meissel vypočítá π ( x ) , pro x rovnající se 5 x 10 5 , 10 6 , 10 7 a 10 8 .
V roce 1959 Derrick Lehmer rozšířil a zjednodušil Meisselovu metodu. Definujme pro reálné m a pro přirozená čísla n a k , P k ( m , n ) jako počet čísel menších než m s přesně k prvočiniteli, vše větší než p n . Dále opravme P 0 ( m , n ) = 1. Potom
Φ(m,ne)=∑k=0+∞Pk(m,ne),{\ displaystyle \ Phi (m, n) = \ součet _ {k = 0} ^ {+ \ infty} P_ {k} (m, n), \,}kde aktuální součet má pouze konečným způsobem několik jiných členů než nula. Nechť y označuje celé číslo takové, že a opravíme n = π ( y ) . Pak a když k ≥ 3. Proto
m3≤y≤m{\ displaystyle {\ sqrt [{3}] {m}} \ leq y \ leq {\ sqrt {m}} \,}P1(m,ne)=π(m)-ne{\ displaystyle P_ {1} (m, n) = \ pi (m) -n \,}Pk(m,ne)=0{\ displaystyle P_ {k} (m, n) = 0 \,}
π(m)=Φ(m,ne)+ne-1-P2(m,ne){\ displaystyle \ pi (m) = \ Phi (m, n) + n-1-P_ {2} (m, n) \,}.
Výpočet P 2 ( m , n ) lze získat tímto způsobem:
P2(m,ne)=∑y<p≤m(π(mp)-π(p)+1).{\ displaystyle P_ {2} (m, n) = \ součet _ {y <p \ leq {\ sqrt {m}}} \ left (\ pi \ left ({\ frac {m} {p}} \ right ) - \ pi (p) +1 \ vpravo). \,}Na druhou stranu lze výpočet Φ ( m , n ) provést pomocí následujících pravidel:
- Φ(m,0)=⌊m⌋;{\ displaystyle \ Phi (m, 0) = \ lfloor m \ rfloor; \,}
- Φ(m,b)=Φ(m,b-1)-Φ(mpb,b-1).{\ displaystyle \ Phi (m, b) = \ Phi (m, b-1) - \ Phi \ left ({\ frac {m} {p_ {b}}}, b-1 \ right). \,}
Pomocí této metody a IBM 701 byl Lehmer schopen vypočítat π (10 10 ).
Choulostivější výsledky analytické teorie čísel a použití stále výkonnějších strojů umožnily v roce 2010 přesný výpočet π (10 24 ) (za předpokladu Riemannovy hypotézy ).
Další funkce počítání prvočísel
Používají se také další funkce počítání prvočísel, protože je pro ně pohodlnější pracovat. Jedním z nich je Riemannova funkce počítání prvočísel, označená Π ( x ) nebo J ( x ) . Toto má skoky 1 / n pro mocniny prvočísel p n , které nabývají hodnoty na půli cesty mezi dvěma stranami nespojitostí. Může být také definována inverzní Mellinovou transformací. Formálně můžeme definovat J pomocí
J(X)=12(∑pne<X1ne +∑pne≤X1ne){\ displaystyle J (x) = {\ frac {1} {2}} \ vlevo (\ sum _ {p ^ {n} <x} {\ frac {1} {n}} \ + \ sum _ {p ^ {n} \ leq x} {\ frac {1} {n}} \ vpravo)}kde p je prvočíslo.
Můžeme také psát
J(X)=∑2XΛ(ne)ln(ne)-Λ(X)2ln(X)=∑ne=1∞π0(X1/ne)ne{\ displaystyle J (x) = \ součet _ {2} ^ {x} {\ frac {\ Lambda (n)} {\ ln (n)}} - {\ frac {\ Lambda (x)} {2 \ ln (x)}} = \ sum _ {n = 1} ^ {\ infty} {\ frac {\ pi _ {0} (x ^ {1 / n})} {n}}}kde Λ je von Mangoldtova funkce a
π0(X)=limε→0π(X-ε)+π(X+ε)2{\ displaystyle \ pi _ {0} (x) = \ lim _ {\ varepsilon \ až 0} {\ frac {\ pi (x- \ varepsilon) + \ pi (x + \ varepsilon)} {2}}}
a tak ( Möbiově inverzí ),
π0(X)=∑ne=1∞μ(ne)J(X1/ne)ne{\ displaystyle \ pi _ {0} (x) = \ součet _ {n = 1} ^ {\ infty} {\ frac {\ mu (n) J (x ^ {1 / n})} {n}} }.
Známe vztah mezi logaritmem Riemannovy zeta funkce a funkcí Λ a Perronovým vzorcem , máme:
ln(ζ(s))=s∫0∞J(X)X-s+1 dX{\ displaystyle \ ln (\ zeta (s)) = s \ int _ {0} ^ {\ infty} J (x) x ^ {- s + 1} ~ {\ rm {d}} x}Čebyševova funkce váhy prvočísla nebo pravomoci prvočísel p n u ln p :
θ(X)=∑p≤Xlnp,{\ displaystyle \ theta (x) = \ součet _ {p \ leq x} \ ln p,}
ψ(X)=∑pne≤Xlnp=∑ne=1∞θ(X1/ne)=∑ne≤XΛ(ne).{\ 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).}
Nerovnost
Níže jsou uvedeny některé nerovnosti pro π ( x ) .
Pro jakékoli skutečné x ≥ 17 (a jakékoli celé číslo x ≥ 11 ), a dokonce i pro x > 1 s ohledem na zvýšení
XlnX<π(X)<1,25506 XlnX{\ displaystyle {\ frac {x} {\ ln x}} <\ pi (x) <1,25506 \ {\ frac {x} {\ ln x}}}.
Pro x ≥ 67 , a dokonce i pro x > e 3/2 s ohledem na zvýšení
XlnX-12<π(X)<XlnX-32{\ displaystyle {\ frac {x} {\ ln x- {1 \ nad 2}}} <\ pi (x) <{\ frac {x} {\ ln x- {3 \ nad 2}}}}.
Další nerovnosti poskytují aproximace n- tého prvočísla .
Riemannova hypotéza
Riemann hypotéza je ekvivalentní k mnohem těsnější horní mez chyby v aproximaci n ( x ) , tedy k více pravidelné rozložení prvočísel:
π(X)=li(X)+Ó(Xln(X)).{\ displaystyle \ pi (x) = {\ rm {li}} (x) + O \ left ({\ sqrt {x}} \ ln (x) \ right).}
Vzorce pro funkce počítání prvočísel
Jedná se o dva druhy, aritmetické vzorce a analytické vzorce. Druhé jsou ty, které nám umožňují dokázat teorém o prvočísle. Pocházejí z práce Riemanna a von Mangoldta a jsou obecně známé jako explicitní vzorce pro funkce L (en) .
Máme následující výraz pro
ψ0(X)=limε→0ψ(X-ε)+ψ(X+ε)2 :{\ displaystyle \ psi _ {0} (x) = \ lim _ {\ varepsilon \ až 0} {\ frac {\ psi (x- \ varepsilon) + \ psi (x + \ varepsilon)} {2}} ~ :}
ψ0(X)=X-∑ρXρρ-ln2π-12ln(1-X-2).{\ displaystyle \ psi _ {0} (x) = x- \ součet _ {\ rho} {\ frac {x ^ {\ rho}} {\ rho}} - \ ln 2 \ pi - {\ frac {1 } {2}} \ ln (1-x ^ {- 2}).}Zde ρ jsou nuly Riemannovy zeta funkce v kritickém pásmu, kde skutečná část ρ je mezi 0 a 1. Vzorec platí pro hodnoty x větší než 1, což je oblast, která nás zajímá a součet kořenů je za podmínek konvergentní a měl by být vzat vzestupně podle absolutních hodnot imaginárních částí.
Pro J máme složitější vzorec:
J(X)=li(X)-∑ρli(Xρ)-ln2+∫X∞dtt(t2-1)lnt.{\ displaystyle J (x) = \ operatorname {li} (x) - \ suma _ {\ rho} \ operatorname {li} (x ^ {\ rho}) - \ ln 2+ \ int _ {x} ^ { \ infty} {\ frac {{\ rm {d}} t} {t (t ^ {2} -1) \ ln t}}.}Vzorec opět platí pro x > 1 a ρ představuje netriviální nuly funkce zeta seřazené podle jejich absolutních hodnot. První člen li ( x ) je obvyklý integrální logaritmus; je však méně snadné popsat, co li znamená jinými slovy. Nejlepším způsobem, jak si to představit, je považovat výraz li ( x ρ ) za zkratku Ei (ρ ln ( x )) , kde Ei je analytické rozšíření integrální exponenciální funkce z pozitivních real do poskytnuté komplexní roviny s řezem podél negativních real.
Poznámky a odkazy
(fr) Tento článek je částečně nebo zcela převzat z článku
anglické Wikipedie s názvem
„ Funkce počítání Prime “ ( viz seznam autorů ) .
Poznámky
-
Jean-Benoît Bost , „Věta o prvočísle a Fourierova transformace“ , Jean-Benoît Bost, Pierre Colmez a Philippe Biane , La function Zêta , Paříž, Éditions de l'École polytechnique,2002( ISBN 978-2-7302-1011-9 , číst online ) , s. 1.
-
Bylo to v roce 1849, více než 40 let po vydání Legendra, že Gauss v korespondenci s Enckem naznačuje, že se domníval v letech 1792 nebo 1793 - tedy kolem 15. roku - že π ( x ) se přibližně rovná x / ln ( x ) . (en) Julian Havil , Gamma: Exploring Euler's Constant , PUP ,2010, 296 s. ( ISBN 978-1-4008-3253-8 , číst online ) , s. 174-176.
-
AM Legendrova, esej o teorii čísel , 2 e ed., Paříž, Courcier, 1808, str. 394 .
-
(en) primes.utm.edu Podmíněný výpočet pí (10 ^ 24).
-
Přesněji, funkce π ( x ) ln ( x ) / x (která má tendenci k 1, když x má tendenci k nekonečnu) je striktně větší než 1 z x = 17 a dosahuje svého maxima pro x = 113: J Barkley Rosser a Lowell Schoenfeld , „ Přibližné vzorce pro některé funkce prvočísel “, Illinois J. Math. , sv. 6,1962, str. 64–94 ( ISSN 0019-2082 , zbMATH 0122.05001 , číst online ) p. 69 a pokračování A209883 z OEIS .
-
Rosser Schoenfield , str. 69, který mimo jiné specifikuje podobné výsledky
(en) Barkley Rosser , „ Explicit bounds for some functions of prime numbers “ , Amer. J. Math , sv. 63,1941, str. 211-232 ( číst online ).
Reference
- Jean-Paul Delahaye , Báječná prvočísla: Cesta k srdci aritmetiky ,2000[ detail vydání ]
- (en) Eric Bach (en) a Jeffrey Shallit , Algorithmic theory theory: efficient algorithms , vol. 1, Cambridge, Mass, MIT Press,1996, 512 s. ( ISBN 0-262-02405-5 ) , kap. 8,8, s. 234
- (en) Leonard Dickson , Dějiny teorie čísel , sv. 1: Dělitelnost a originalita , publikace Mineola, Dover,2005( ISBN 0-486-44232-2 )
Související články
Externí odkaz
- Zobrazit více A000720 z OEIS