Odpre glavni meni

Število praštevil

Števílo práštevíl je v matematiki nemultiplikativna aritmetična funkcija poljubnega pozitivnega realnega števila , ki se jo označi s , in da število praštevil, ki ne presegajo . Po navadi se namesto realnega števila vzame pozitivno celo število . Prve vrednosti 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

ZgodovinaUredi

V teoriji števil je pomembno raziskovanje obnašanja števila praštevil. Gauss in Legendre sta domnevala, da je vrednost funkcije približno enaka:

 

tako da je limita kvocienta funkcij   in  :

 

Asimptotično obnašanje  , je dano s praštevilskim izrekom.

Enakovredno kot zgoraj velja:

 

kjer je   fukcija logaritemskega integrala. Praštevilski izrek sta leta 1896 neodvisno dokazala Hadamard in 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  , kot je na primer:

 

kjer je   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   je raziskoval James Joseph Sylvester.

Podobna je domneva za praštevilske vrste:

 

Algoritmi za računanje Uredi

Preprost način za računanje  , če   ni prevelik, je Eratostenovo sito, s katerim se najde praštevila manjša ali enaka  , in se jih prešteje.

Bolj izdelano pot je podal Legendre. Če so za dani     , ...,   različna praštevila, je število celih števil manjših ali enakih od  , ki niso deljiva s  :

 

kjer je   funkcija celega dela. To število je tako enako:

 

kjer so števila   praštevila manjša ali enaka kvadratnemu korenu od  .

Meissel je v nizu člankov, objavljenih med letoma 1870 in 1885, opisal in uporabil praktični kombinatorični način računanja  . Naj bodo   , ...,   prva   praštevila in naj   označuje število naravnih števil manjših od  , ki niso deljiva s kakšnim  . Potem velja:

 

Če za dano naravno število   velja   in  , potem velja:

 

S tem pristopom je Meissel izračunal   za   enak 5 · 105, 106, 107 in 108.

Leta 1959 je Lehmer razširil in poenostavil Meisslovo metodo. Za realno število   in za naravni števili   in   naj je   število števil manjših od   z natanko   prafaktorji, večjimi od  . Naj velja tudi  . Potem je:

 

kjer ima vsota dejansko le končno število neničelnih členov. Naj   označuje takšno celo število, da je   in naj je  . Potem je   in  , ko je  . Zato:

 

  je moč izračunati kot:

 

  se lahko izračuna s pomočjo naslednjih pravil:

  1.  
  2.  

S pomočjo te metode in računalnika IBM 701 je Lehmer lahko izračunal  .

Hvang Čeng je na konferenci o praštevilih na Univerzi v Bordeauxu uporabil naslednji enakosti:

 
 

pri čemer je  . Z Laplaceovo transformacijo obeh strani in geometrično vsoto   izhaja:

 
 
 

Druge funkcije štetja praštevilUredi

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   in tudi  . Funkcija narašča korakoma po   za praštevilske potence  , in zavzema vrednosti na polovici obeh nezveznosti. Na ta način je lahko določena z obratom Mellinove transformacije. Strogo se lahko določi   kot:

 

kjer je   praštevilo.

Lahko se piše tudi:

 

kjer je   von Mangoldtova funkcija in:

 

Möbiusova inverzna formula da:

 

kjer je   Mertensova funkcija.

Z zvezo med Riemannovo funkcijo ζ(·) in von Mangoldtovo funkcijo Λ(·) ter Perronovo enačbo je:

 

Funkcija   je v tesni zvezi s funkcijama Čebišova θ(x) in ψ(x), ki razvrščata praštevila ali praštevilske potence   z  :