Število praštevil

Števílo práštevíl je v matematiki nemultiplikativna aritmetična funkcija poljubnega pozitivnega realnega števila x, ki jo označimo s π(x) in da število praštevil, ki ne presegajo x. Po navadi namesto realnega števila vzamemo pozitivno celo število n. Prve vrednosti π(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 π(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 π(x) in x/ln x:

$\lim_{x\rightarrow +\infty}\frac{\pi(x)}{x/\operatorname{ln} \, x}=1 \; .$

Asimptotično obnašanje π(x) ~ 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 li(·) fukcija logaritemski integral. Praštevilski izrek sta leta 1896 neodvisno dokazala Hadamard in de la Vallée Poussin s pomočjo lastnosti Riemannove funkcije ζ, ki jo je uvedel Riemann leta 1859.

Znane so natančnejše ocene za π(x) kot je na primer:

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

kjer je 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 π(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 π(x)

Preprost način za računanje π(x), če x ni prevelik, je Eratostenovo sito, s katerim najdemo praštevila manjša ali enaka x, in jih preštejemo.

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_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots \; ,$

kjer je $\lfloor\cdot\rfloor$ funkcija celi del. 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 π(x). Naj bodo $p_{1}$, $p_{2}$, …, $p_{n}$ prva n praštevila in naj Φ(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 π(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}\le y\le\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 ≥ 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\le\sqrt{m}}\left(\pi\left(\frac mp\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 naslednje 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}\,ds = \pi(t) \; ,$

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

$\Theta(s)=s\frac{d}{ds} \; .$

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ⁿ, in zavzema vrednosti na polovici obeh nezveznosti. Na ta način je lahko določena z obratom Mellinove transformacije. Strogo lahko določimo $\Pi_{0}(x)$ kot:

$\Pi_0(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg) \; ,$

kjer je p praštevilo.

Lahko pišemo tudi:

$\Pi_0(x) = \sum_2^x \frac{\Lambda(n)}{\ln n} - \frac12 \frac{\Lambda(x)}{\ln x} = \sum_{n=1}^\infty \frac1n \pi_0(x^{1/n})$

kjer je Λ(n) von Mangoldtova funkcija in:

$\pi_0(x) = \frac{\pi(x-0)+\pi(x+0)}2 \; .$

Möbiusova inverzna enačba da:

$\pi_{0}(x) = \sum_{n=1}^\infty \frac{\mu(n)}n \Pi_0(x^{1/n})=\int_{1}^{\infty}du M'(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 imamo:

$\ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s+1}\,dx \; .$

Funkcija π(x) je v tesni zvezi s funkcijama Čebišova θ(x) in ψ(x), ki razvrščata praštevila ali praštevilske potence pⁿ z ln(p):

$\theta(x)=\sum_{p\le x}\ln p \; ,$

$\psi(x) = \sum_{p^n \le x} \ln p = \sum_{n=1}^\infty \theta(x^{1/n}) = \sum_{n\le x}\Lambda(n) \; .$