Število praštevil: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
+|popravek en:Prime-counting function |
+ |
||
Vrstica 11:
: <math>\lim_{x\rightarrow +\infty}\frac{\pi(x)}{x/\operatorname{ln} \, x}=1 \; . </math>
Asimptotično obnašanje π(''x'') ~ ''x'' / ln ''x'', je dano s [[praštevilski izrek|praštevilskim izrekom]].
Enakovredno kot zgoraj velja:
Vrstica 45:
kjer so števila <math>p_{1}, p_{2},\dots,p_{k}</math> praštevila manjša ali enaka [[kvadratni koren|kvadratnemu korenu]] od ''x''.
[[Ernst Meissel|Meissel]] je v nizu člankov, objavljenih med letoma [[1870]] in [[1885]], opisal in uporabil praktični [[kombinatorika|kombinatorični]] način računanja π(''x''). Naj bodo <math>p_{1}</math>, <math>p_{2}</math>, …, <math>p_{n}</math> prva ''n'' praštevila in naj Φ(''m'',''n'') označuje število naravnih števil manjših od ''m'', ki niso deljiva s kakšnim <math>p_{i}</math>. Potem velja:
: <math> \Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right) \; . </math>
Če za dano naravno število ''m'' velja <math>n=\pi\left(\sqrt[3]{m}\right)</math> in <math>\mu=\pi\left(\sqrt{m}\right)-n</math>, potem velja:
: <math> \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) \; . </math>
S tem pristopom je Meissel izračunal π(''x'') za ''x'' enak 5 · 10<sup>5</sup>, 10<sup>6</sup>, 10<sup>7</sup> in 10<sup>8</sup>.
Leta [[1959]] je [[Derrick Henry Lehmer|Lehmer]] razširil in poenostavil Meisslovo metodo. Za realno število ''m'' in za naravni števili ''n'' in ''k'' naj je <math>P_{k}(m,n)</math> število števil manjših od ''m'' z natanko ''k'' prafaktorji, večjimi od <math>p_{n}</math>. naj velja tudi <math>P_{0}(m,n)=1</math>. Potem je:
: <math> \Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n) \; , </math>
kjer ima vsota dejansko le končno število neničelnih členov. Naj ''y'' označuje takšno celo število, da je <math>\sqrt[3]{m}\le y\le\sqrt{m}</math> in naj je <math>n=\pi(y)</math>. Potem je <math>P_{1}(m,n)=\pi(m)-n</math> in <math>P_{k}(m,n)=0</math>, ko je ''k'' ≥ 3. Zato:
: <math> \pi(m)=\Phi(m,n)+n-1-P_2(m,n) \; . </math>
<math>P_{2}(m,n)</math> je moč izračunati kot:
: <math> P_{2}(m,n)=\sum_{y<p\le\sqrt{m}}\left(\pi\left(\frac mp\right)-\pi(p)+1\right) \; . </math>
<math>\Phi(m,n)</math> se lahko izračuna s pomočjo naslednjih pravil:
# <math> \Phi(m,0)=\lfloor m\rfloor;\,</math>
# <math> \Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right) \; . </math>
S pomočjo te metode in računalnika [[IBM]] 701 je Lehmer lahko izračunal <math>\pi\left(10^{10}\right)</math>.
Hvang Čeng je na konferenci o praštevilih na [[Univerza v Bordeaux|Univerzi v Bordeauxu]] uporabil naslednje enakosti:
: <math> e^{(a-1)\Theta}f(x)=f(ax) \; , </math>
: <math> J(x)=\sum_{n=1}^{\infty}\frac{\pi(x^{1/n})}{n} \; , </math>
pri čemer je <math>x=e^{t}</math>. Z [[Laplaceova transformacija|Laplaceovo transformacijo]] obeh strani in geometrično vsoto <math> e^{n\Theta} </math> izhaja:
: <math> \frac{1}{2{\pi}i}\int_{c-i\infty}^{c+i\infty}g(s)t^{s}\,ds = \pi(t) \; , </math>
: <math> \frac{\ln \zeta(s)}{s}=(1-e^{\Theta(s)})^{-1}g(s) \; , </math>
: <math> \Theta(s)=s\frac{d}{ds} \; . </math>
== 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 <math>\Pi_{0}(x)</math> in tudi ''f''(''x''). Funkcija narašča korakoma po ''1/n'' za praštevilske potence ''p''<sup>n</sup>, in zavzema vrednosti na polovici obeh nezveznosti. Na ta način je lahko določena z obratom [[Mellinova transformacija|Mellinove transformacije]]. Strogo lahko določimo <math>\Pi_{0}(x)</math> kot:
: <math> \Pi_0(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg) \; , </math>
kjer je ''p'' praštevilo.
Lahko pišemo tudi:
: <math> \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}) </math>
kjer je Λ(''n'') [[von Mangoldtova funkcija]] in:
:<math> \pi_0(x) = \frac{\pi(x-0)+\pi(x+0)}2 \; . </math>
[[Möbiusova inverzna enačba]] da:
: <math>\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} \; , </math>
kjer je M(u) [[Mertensova funkcija]].
Z zvezo med [[Riemannova funkcija zeta|Riemannovo funkcijo ζ(·)]] in von Mangoldtovo funkcijo Λ(·) ter [[Perronova enačba|Perronovo enačbo]] imamo:
: <math> \ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s+1}\,dx \; . </math>
Funkcija π(''x'') je v tesni zvezi s [[funkcija Čebišova|funkcijama Čebišova]] θ(''x'') in ψ(''x''), ki razvrščata praštevila ali praštevilske potence ''p''<sup>''n''</sup> z ln(''p''):
: <math> \theta(x)=\sum_{p\le x}\ln p \; , </math>
: <math> \psi(x) = \sum_{p^n \le x} \ln p = \sum_{n=1}^\infty \theta(x^{1/n}) = \sum_{n\le x}\Lambda(n) \; . </math>
{{math-stub}}
| |||