Š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 , 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

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:

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

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:

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š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 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 :