Število praštevil

Števílo práštevíl je v matematiki nemultiplikativna aritmetična funkcija poljubnega pozitivnega realnega števila ${\displaystyle x\,}$, ki se jo označi s ${\displaystyle \pi (x)\,}$, in da število praštevil, ki ne presegajo ${\displaystyle x\,}$. Po navadi se namesto realnega števila vzame pozitivno celo število ${\displaystyle n\,}$. Prve vrednosti ${\displaystyle \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, ...

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

${\displaystyle x/\ln x\!\,,}$

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

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

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

Enakovredno kot zgoraj velja:

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

kjer je ${\displaystyle \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 ${\displaystyle \pi (x)\,}$, kot je na primer:

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

kjer je ${\displaystyle {\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 ${\displaystyle \pi (x)\,}$ je raziskoval James Joseph Sylvester.

Podobna je domneva za praštevilske vrste:

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

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

Bolj izdelano pot je podal Legendre. Če so za dani ${\displaystyle x\,}$ ${\displaystyle p_{1}\,}$, ${\displaystyle p_{2}\,}$, ..., ${\displaystyle p_{k}\,}$ različna praštevila, je število celih števil manjših ali enakih od ${\displaystyle x\,}$, ki niso deljiva s ${\displaystyle p_{i}\,}$:

${\displaystyle \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 ${\displaystyle \lfloor \cdot \rfloor }$ funkcija celega dela. To število je tako enako:

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

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

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

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

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

${\displaystyle \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 ${\displaystyle \pi (x)\,}$ za ${\displaystyle x\,}$ enak 5 · 10⁵, 10⁶, 10⁷ in 10⁸.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 ${\displaystyle \Pi _{0}(x\,)}$ in tudi ${\displaystyle f(x)\,}$. Funkcija narašča korakoma po ${\displaystyle 1/n\,}$ za praštevilske potence ${\displaystyle 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 ${\displaystyle \Pi _{0}(x)\,}$ kot:

${\displaystyle \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 ${\displaystyle p\,}$ praštevilo.

Lahko se piše tudi:

${\displaystyle \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 ${\displaystyle \Lambda (n)\,}$ von Mangoldtova funkcija in:

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

Möbiusova inverzna formula da:

${\displaystyle \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 ${\displaystyle M(u)\,}$ Mertensova funkcija.

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

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

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

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

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