Š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 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[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 \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 de 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)\, [uredi | uredi kodo]

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_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 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 · 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 \ge 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 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[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 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) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg) \!\, ,

kjer je p\, praštevilo.

Lahko se piše 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 \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}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 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\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) \!\, .