Število praštevil

Števílo práštevíl je v matematiki nemultiplikativna aritmetična funkcija poljubnega pozitivnega realnega števila $x\,$, ki se jo označi s $\pi (x)\,$, in da število praštevil, ki ne presegajo $x\,$. Po navadi se namesto realnega števila vzame pozitivno celo število $n\,$. Prve vrednosti $\pi (n)\,$ za n = 1, 2, 3, ... so (OEIS A000720):

0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, ...

Graf prvih 60 vrednosti funkcije $\pi (n)\,$

Zgodovina

V teoriji števil je pomembno raziskovanje obnašanja števila praštevil. Gauss in Legendre sta domnevala, da je vrednost funkcije približno enaka:

$x/\ln x\!\,,$

tako da je limita kvocienta funkcij $\pi (x)\,$ in $x/\ln x\,$:

$\lim _{x\rightarrow +\infty }{\frac {\pi (x)}{x/\operatorname {ln} \,x}}=1\!\,.$

Asimptotično obnašanje $\pi (x)\sim x/\ln x\,$, je dano s praštevilskim izrekom.

Enakovredno kot zgoraj velja:

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

kjer je $\operatorname {li} (x)\,$ fukcija logaritemskega integrala. Praštevilski izrek sta leta 1896 neodvisno dokazala Hadamard in La Vallée Poussin s pomočjo značilnosti Riemannove funkcije ζ, ki jo je uvedel Riemann leta 1859.

Znane so točnejše ocene za $\pi (x)\,$, kot je na primer:

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

kjer je ${\mathcal {O}}\,$ Landauov simbol. Elementarne dokaze praštevilskega izreka brez uporabe funkcije ζ ali kompleksne analize sta leta 1948 večinoma neodvisno odkrila Selberg in Erdős.

Funkcijo $\pi (x)\,$ je raziskoval James Joseph Sylvester.

Podobna je domneva za praštevilske vrste:

$G(n,x)=\sum _{p}^{x}p^{n}\sim \pi (x^{n+1})\!\,.$

Algoritmi za računanje $\pi (x)\,$

Preprost način za računanje $\pi (x)\,$, če $x\,$ ni prevelik, je Eratostenovo sito, s katerim se najde praštevila manjša ali enaka $x\,$, in se jih prešteje.

Bolj izdelano pot je podal Legendre. Če so za dani $x\,$ $p_{1}\,$, $p_{2}\,$, ..., $p_{k}\,$ različna praštevila, je število celih števil manjših ali enakih od $x\,$, ki niso deljiva s $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 \!\,,$

kjer je $\lfloor \cdot \rfloor$ funkcija celega dela. To število je tako enako:

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

kjer so števila $p_{1},p_{2},\dots ,p_{k}\,$ praštevila manjša ali enaka kvadratnemu korenu od $x\,$.

Meissel je v nizu člankov, objavljenih med letoma 1870 in 1885, opisal in uporabil praktični kombinatorični način računanja $\pi (x)\,$. Naj bodo $p_{1}\,$, $p_{2}\,$, ..., $p_{n}\,$ prva $n\,$ praštevila in naj $\Phi (m,n)\,$ označuje število naravnih števil manjših od $m\,$, ki niso deljiva s kakšnim $p_{i}\,$. Potem velja:

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

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

$\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)\!\,.$

S tem pristopom je Meissel izračunal $\pi (x)\,$ za $x\,$ enak 5 · 10⁵, 10⁶, 10⁷ in 10⁸.

Leta 1959 je Lehmer razširil in poenostavil Meisslovo metodo. Za realno število $m\,$ in za naravni števili $n\,$ in $k\,$ naj je $P_{k}(m,n)\,$ število števil manjših od $m\,$ z natanko $k\,$ prafaktorji, večjimi od $p_{n}\,$. Naj velja tudi $P_{0}(m,n)=1\,$. Potem je:

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

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

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

$P_{2}(m,n)\,$ je moč izračunati kot:

$P_{2}(m,n)=\sum _{y<p\leq {\sqrt {m}}}\left(\pi \left({\frac {m}{p}}\right)-\pi (p)+1\right)\!\,.$

$\Phi (m,n)\,$ se lahko izračuna s pomočjo naslednjih pravil:

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

S pomočjo te metode in računalnika IBM 701 je Lehmer lahko izračunal $\pi \left(10^{10}\right)\,$.

Hvang Čeng je na konferenci o praštevilih na Univerzi v Bordeauxu uporabil naslednji enakosti:

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

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

pri čemer je $x=e^{t}\,$. Z Laplaceovo transformacijo obeh strani in geometrično vsoto $e^{n\Theta }\,$ izhaja:

${\frac {1}{2{\pi }i}}\int _{c-i\infty }^{c+i\infty }g(s)t^{s}\,\mathrm {d} s=\pi (t)\!\,,$

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

$\Theta (s)=s{\frac {\mathrm {d} }{\mathrm {d} s}}\!\,.$

Druge funkcije štetja praštevil

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 $\Pi _{0}(x\,)$ in tudi $f(x)\,$. Funkcija narašča korakoma po $1/n\,$ za praštevilske potence $p^{n}\,$, in zavzema vrednosti na polovici obeh nezveznosti. Na ta način je lahko določena z obratom Mellinove transformacije. Strogo se lahko določi $\Pi _{0}(x)\,$ kot:

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

kjer je $p\,$ praštevilo.

Lahko se piše tudi:

$\Pi _{0}(x)=\sum _{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})\!\,,$

kjer je $\Lambda (n)\,$ von Mangoldtova funkcija in:

$\pi _{0}(x)={\frac {\pi (x-0)+\pi (x+0)}{2}}\!\,.$

Möbiusova inverzna formula da:

$\pi _{0}(x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\Pi _{0}(x^{1/n})=\int _{1}^{\infty }duM'(u)\Pi _{0}(x^{1/u})u^{-1}\!\,,$

kjer je $M(u)\,$ Mertensova funkcija.

Z zvezo med Riemannovo funkcijo ζ(·) in von Mangoldtovo funkcijo Λ(·) ter Perronovo enačbo je:

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

Funkcija $\pi (x)\,$ je v tesni zvezi s funkcijama Čebišova θ(x) in ψ(x), ki razvrščata praštevila ali praštevilske potence $p^{n}\,$ z $\ln p\,$:

$\theta (x)=\sum _{p\leq x}\ln p\!\,,$

$\psi (x)=\sum _{p^{n}\leq x}\ln p=\sum _{n=1}^{\infty }\theta (x^{1/n})=\sum _{n\leq x}\Lambda (n)\!\,.$