Število praštevil: Razlika med redakcijama

Izbrisana vsebina Dodana vsebina
Addbot (pogovor | prispevki)
m Bot: Migracija 18 interwikija/-ev, od zdaj gostuje(-jo) na Wikipodatkih, na d:q251922
m m/dp/slog
Vrstica 1:
'''Števílo práštevíl''' je v [[matematika|matematiki]] [[multiplikativna funkcija|nemultiplikativna]] [[aritmetična funkcija]] poljubnega [[pozitivno število|pozitivnega]] [[realno število|realnega števila]] ''x'', ki se jo označimooznači s π(''x'') in da število [[praštevilo|praštevil]], ki ne presegajo ''x''. Po navadi se namesto realnega števila vzamemovzame pozitivno [[celo število]] ''n''. Prve vrednosti π(''n'') za ''n'' = [[1 (število)|1]], [[2 (število)|2]], [[3 (število)|3]], ... so {{OEIS|id=A000720}}:
 
: [[nič|0]], 1, 2, 2, 3, 3, [[4 (število)|4]], 4, 4, 4, [[5 (število)|5]], 5, [[6 (število)|6]], 6, 6, [[7 (število)|7]], 7, [[8 (število)|8]], 8, ...
Vrstica 21:
: <math>\lim_{x\rightarrow +\infty}\pi(x) / \operatorname{li}(x)=1 \; , </math>
 
kjer je ''li''(·) fukcija [[logaritemski integral]]. Praštevilski izrek sta leta [[1896]] neodvisno dokazala [[Jacques Hadamard|Hadamard]] in [[Charles -Jean de la Vallée- Poussin|de la Vallée Poussin]] s pomočjo lastnostiznačilnosti [[Riemannova funkcija zeta|Riemannove funkcije ζ]], ki jo je uvedel [[Bernhard Riemann|Riemann]] leta [[1859]].
 
Znane so natančnejšetočnejše ocene za π(''x'') kot je na primer:
 
: <math>\pi(x) = \operatorname{li}(x) + O \left( x \exp \left( -\frac{\sqrt{\ln(x)}}{15} \right) \right) \; , </math>
 
kjer je ''O'' [[Landauov simbol]]. [[elementarni dokaz|Elementarne dokaze]] praštevilskega izreka brez uporabe funkcije ζ ali [[kompleksna analiza|kompleksne analize]] sta leta [[1948]] večinoma neodvisno odkrila [[Atle Selberg|Selberg]] in [[Paul Erdős|Erdős]].
 
Funkcijo π(''x'') je raziskoval [[James Joseph Sylvester]].
Vrstica 37:
== Algoritmi za računanje π(''x'') ==
 
Preprost način za računanje π(''x''), če ''x'' ni prevelik, je [[Eratostenovo sito]], s katerim najdemose najde praštevila manjša ali enaka ''x'', in se jih preštejemoprešteje.
 
Bolj izdelano pot je podal Legendre. Če so za dani ''x'' <math>p_{1}</math>,&nbsp;<math>p_{2}</math>,&nbsp;…,&nbsp;<math>p_{k}</math> različna praštevila, je število celih števil manjših ali enakih od ''x'', ki [[tuje število|niso deljiva]] s <math>p_{i}</math>
Vrstica 49:
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>,&nbsp;<math>p_{2}</math>,&nbsp;…,&nbsp;<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>
Vrstica 59:
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>
Vrstica 94:
== 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 se lahko določimodoloči <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>
Vrstica 100:
kjer je ''p'' praštevilo.
 
Lahko pišemose piše 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>
Vrstica 114:
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]] imamoje:
 
: <math> \ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s+1}\,dx \; . </math>