Število praštevil

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Š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[uredi | uredi kodo]

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)[uredi | uredi kodo]

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 · 105, 106, 107 in 108.

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[uredi | uredi kodo]

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 pn, 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 pn 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) \; .