Število praštevil: Razlika med redakcijama

'''Števílo práštevíl''' je v [[matematika|matematiki]] [[multiplikativna funkcija|nemultiplikativna]] [[aritmetična funkcija]] poljubnega [[pozitivno število|pozitivnega]] [[realno število|realnega števila]] ''<math>x''\, </math>, ki se jo označi s π<math>\pi (''x'')\, </math>, in da število [[praštevilo|praštevil]], ki ne presegajo ''<math>x''\, </math>. Po navadi se namesto realnega števila vzame pozitivno [[celo število]] ''<math>n''\, </math>. Prve vrednosti π<math>\pi (''n'')\, </math> za ''n'' = [[1 (število)|1]], [[2 (število)|2]], [[3 (število)|3]], ... so {{OEIS|id=A000720}}:

V [[teorija števil|teoriji števil]] je pomembno raziskovanje obnašanja števila praštevil. [[Carl Friedrich Gauss|Gauss]] in [[Adrien-Marie Legendre|Legendre]] sta [[domneva]]la, da je vrednost funkcije približno enaka:

tako da je limita kvocienta funkcij π<math>\pi (''x'')\, </math> in ''<math>x''/ \ln ''x''\, </math>:

: <math> \lim_{x\rightarrow +\infty}\frac{\pi(x)}{x/\operatorname{ln} \, x}=1 \!\, . </math>

Asimptotično obnašanje π<math>\pi (''x'') ~\sim ''x'' / \ln ''x''\, </math>, je dano s [[praštevilski izrek|praštevilskim izrekom]].

: <math> \lim_{x\rightarrow +\infty}\pi(x) / \operatorname{li}(x)=1 \!\, , </math>

kjer je ''<math>\operatorname{li''} (·x)\, </math> fukcija [[logaritemski integral|logaritemskega integrala]]. Praštevilski izrek sta leta 1896 neodvisno dokazala [[Jacques Hadamard|Hadamard]] in [[Charles-Jean de la Vallée Poussin|de la Vallée Poussin]] s pomočjo značilnosti [[Riemannova funkcija zeta|Riemannove funkcije ζ]], ki jo je uvedel [[Bernhard Riemann|Riemann]] leta 1859.

Znane so točnejše ocene za π<math>\pi (''x'')\, </math>, kot je na primer:

: <math> \pi(x) = \operatorname{li}(x) + \mathcal{O} \left( x \exp \left( -\frac{\sqrt{\ln(x)}}{15} \right) \right) \!\, , </math>

kjer je ''<math>\mathcal{O''}\, </math> [[O notacija|Landauov simbol]]. [[elementarni dokaz|Elementarne dokaze]] praštevilskega izreka brez uporabe funkcije ζ ali [[kompleksna analiza|kompleksne analize]] sta leta 1948 večinoma neodvisno odkrila [[Atle Selberg|Selberg]] in [[Paul Erdős|Erdős]].

Funkcijo π<math>\pi (''x'')\, </math> je raziskoval [[James Joseph Sylvester]].

== Algoritmi za računanje π<math>\pi (''x'')\, </math> ==

Preprost način za računanje π<math>\pi (''x'')\, </math>, če ''<math>x''\, </math> ni prevelik, je [[Eratostenovo sito]], s katerim se najde praštevila manjša ali enaka ''<math>x''\, </math>, in se jih prešteje.

Bolj izdelano pot je podal Legendre. Če so za dani ''<math>x''\, </math> <math>p_{1}\, </math>,&nbsp;<math>p_{2}\, </math>,&nbsp;…...,&nbsp;<math>p_{k}\, </math> različna praštevila, je število celih števil manjših ali enakih od ''<math>x''\, </math>, ki [[tuje število|niso deljiva]] s <math>p_{i}\, </math>:

kjer so števila <math>p_{1}, p_{2},\dots,p_{k}\, </math> praštevila manjša ali enaka [[kvadratni koren|kvadratnemu korenu]] od ''<math>x''\, </math>.

[[Ernst Meissel|Meissel]] je v nizu člankov, objavljenih med letoma 1870 in 1885, opisal in uporabil praktični [[kombinatorika|kombinatorični]] način računanja π<math>\pi (''x'')\, </math>. Naj bodo <math>p_{1}\, </math>,&nbsp;<math>p_{2}\, </math>,&nbsp;…...,&nbsp;<math>p_{n}\, </math> prva ''<math>n''\, </math> praštevila in naj Φ<math>\Phi (''m'',''n'')\, </math> označuje število naravnih števil manjših od ''<math>m''\, </math>, ki niso deljiva s kakšnim <math>p_{i}\, </math>. Potem velja:

Če za dano naravno število ''<math>m''\, </math> velja <math>n=\pi\left(\sqrt[3]{m}\right)\, </math> in <math>\mu=\pi\left(\sqrt{m}\right)-n\, </math>, potem velja:

S tem pristopom je Meissel izračunal π<math>\pi (''x'')\, </math> za ''<math>x''\, </math> enak 5 · 10⁵, 10⁶, 10⁷ in 10⁸.

Leta 1959 je [[Derrick Henry Lehmer|Lehmer]] razširil in poenostavil Meisslovo metodo. Za realno število ''<math>m''\, </math> in za naravni števili ''<math>n''\, </math> in ''<math>k''\, </math> naj je <math>P_{k} (m,n)\, </math> število števil manjših od ''<math>m''\, </math> z natanko ''<math>k''\, </math> prafaktorji, večjimi od <math>p_{n}\, </math>. najNaj velja tudi <math>P_{0}(m,n)=1\, </math>. Potem je:

kjer ima vsota dejansko le končno število neničelnih členov. Naj ''<math>y''\, </math> označuje takšno celo število, da je <math>\sqrt[3]{m}\le y\le\sqrt{m}\, </math> in naj je <math>n=\pi(y)\, </math>. Potem je <math>P_{1}(m,n)=\pi(m)-n\, </math> in <math>P_{k}(m,n)=0\, </math>, ko je ''<math>k'' ≥\ge 3\, </math>. Zato:

: <math> \pi(m)=\Phi (m,n)+n-1-P_2P_{2} (m,n) \!\, . </math>

<math>P_{2} (m,n)\, </math> je moč izračunati kot:

: <math> P_{2} (m,n)=\sum_{y<p\le\sqrt{m}}\left(\pi\left(\frac mp\right)-\pi(p)+1\right) \!\, . </math>

<math>\Phi (m,n)\, </math> se lahko izračuna s pomočjo naslednjih pravil:

# <math> \Phi (m,0)=\lfloor m\rfloor \!\, , </math>

# <math> \Phi (m,b)=\Phi (m,b-1)-\Phi \left(\frac m{p_b},b-1\right) \!\, . </math>

S pomočjo te metode in računalnika [[IBM]]&nbsp;701 je Lehmer lahko izračunal <math>\pi\left(10^{10}\right)\, </math>.

Hvang Čeng je na konferenci o praštevilih na [[Univerza v Bordeaux|Univerzi v Bordeauxu]] uporabil naslednjenaslednji enakosti:

: <math> e^{(a-1)\Theta}f (x)=f (ax) \!\, , </math>

: <math> J (x) = \sum_{n=1}^{\infty}\frac{\pi (x^{1/n})}{n} \!\, , </math>

pri čemer je <math>x=e^{t}\, </math>. Z [[Laplaceova transformacija|Laplaceovo transformacijo]] obeh strani in geometrično vsoto <math> e^{n\Theta}\, </math> izhaja:

: <math> \frac{1}{2{\pi}i}\int_{c-i\infty}^{c+i\infty}g (s)t^{s} \,ds \mathrm{d} s = \pi(t) \!\, , </math>

: <math> \Theta(s)=s\frac{\mathrm{d}}{ds\mathrm{d} s} \!\, . </math>

Uporabljajo se tudi druge funkcije, ker je lažje delati z njimi. Ena od njih je [[Riemannova funkcija števila praštevil]], običajno označena kot <math>\Pi_{0}(x\, )</math> in tudi ''<math>f'' (''x'')\, </math>. Funkcija narašča korakoma po ''<math>1/n''\, </math> za praštevilske potence ''p''<supmath>p^{n}\, </supmath>, in zavzema vrednosti na polovici obeh nezveznosti. Na ta način je lahko določena z obratom [[Mellinova transformacija|Mellinove transformacije]]. Strogo se lahko določi <math>\Pi_{0}(x)\, </math> kot:

kjer je ''<math>p''\, </math> praštevilo.

kjer je Λ<math>\Lambda (''n'')\, </math> [[von Mangoldtova funkcija]] in:

[[Möbiusova inverzna enačbaformula]] da:

kjer je <math>M (u)\, </math> [[Mertensova funkcija]].

Funkcija π<math>\pi (''x'')\, </math> je v tesni zvezi s [[funkcija Čebišova|funkcijama Čebišova]] θ(''x'') in ψ(''x''), ki razvrščata praštevila ali praštevilske potence ''p''<supmath>''p^{n''}\, </supmath> z <math>\ln('' p'')\, </math>: