Število praštevil

Iz Wikipedije, proste enciklopedije

Š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)

[uredi] 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}) \; .$

[uredi] 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 = π(y)$ . Potem je $P 1 (m, n) = π(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) \; .$

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

$\Phi(m,0)=\lfloor m\rfloor;\,$
$\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 Θ$ 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} \; .$

[uredi] 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 $Π 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 $Π 0 (x)$ kot: