A matematika, azon belül az analitikus számelmélet területén a prímszámláló függvény (prime-counting function) az a számelméleti függvény, ami az x valós számnál nem nagyobb prímszámok számát adja meg. Jelölése π(x) (nincs közvetlen köze a pí számhoz).
Története A számelmélet kutatóinak érdeklődésére régóta számot tart a prímszámláló függvény növekedési rátája. A 18. század végén Gauss és Legendre megsejtette, hogy értéke kb.
abban az értelemben, hogy
Ezt az állítást ma prímszámtételként ismerjük. Ezzel ekvivalens állítás, hogy
ahol li a logaritmikus integrál függvény. A prímszámtételt 1896-ban egymástól függetlenül Jacques Hadamard és Charles de la Vallée Poussin is bebizonyította, a Riemann által 1859-ben bevezetett Riemann-féle zéta-függvény tulajdonságainak felhasználásával.
Azokban a nagyságrendekben, amelyekben a számelmélet általában vizsgálódik (tehát amikor nem kezelhetetlenül nagy), nagyobb, mint , de végtelen sokszor igaz ennek az ellenkezője is. Ennek tárgyalását lásd a Skewes-féle szám szócikkben.
A prímszámtétel olyan bizonyítását, ami nem használta sem a zéta-függvényt, sem a komplex analízis eszköztárát 1948-ban adta Atle Selberg és Erdős Pál (nagyrészt egymástól függetlenül).
Táblázat π(x), x / ln x és li(x) értékeivel A táblázat a három függvény, π(x), x / ln x és li(x) értékeit mutatja meg 10 különböző hatványainál. Lásd még és
{| class="wikitable" style="text-align: right" ! x ! π(x) ! π(x) − x / ln x ! li(x) − π(x) ! x / π(x) |- | 10 | 4 | −0,3 | 2,2 | 2,500 |- | 102 | 25 | 3,3 | 5,1 | 4,000 |- | 103 | 168 | 23 | 10 | 5,952 |- | 104 | 1 229 | 143 | 17 | 8,137 |- | 105 | 9 592 | 906 | 38 | 10,425 |- | 106 | 78 498 | 6 116 | 130 | 12,740 |- | 107 | 664 579 | 44 158 | 339 | 15,047 |- | 108 | 5 761 455 | 332 774 | 754 | 17,357 |- | 109 | 50 847 534 | 2 592 592 | 1 701 | 19,667 |- | 1010 | 455 052 511 | 20 758 029 | 3 104 | 21,975 |- | 1011 | 4 118 054 813 | 169 923 159 | 11 588 | 24,283 |- | 1012 | 37 607 912 018 | 1 416 705 193 | 38 263 | 26,590 |- | 1013 | 346 065 536 839 | 11 992 858 452 | 108 971 | 28,896 |- | 1014 | 3 204 941 750 802 | 102 838 308 636 | 314 890 | 31,202 |- | 1015 | 29 844 570 422 669 | 891 604 962 452 | 1 052 619 | 33,507 |- | 1016 | 279 238 341 033 925 | 7 804 289 844 393 | 3 214 632 | 35,812 |- | 1017 | 2 623 557 157 654 233 | 68 883 734 693 281 | 7 956 589 | 38,116 |- | 1018 | 24 739 954 287 740 860 | 612 483 070 893 536 | 21 949 555 | 40,420 |- | 1019 | 234 057 667 276 344 607 | 5 481 624 169 369 960 | 99 877 775 | 42,725 |- | 1020 | 2 220 819 602 560 918 840 | 49 347 193 044 659 701 | 222 744 644 | 45,028 |- | 1021 | 21 127 269 486 018 731 928 | 446 579 871 578 168 707 | 597 394 254 | 47,332 |- | 1022 | 201 467 286 689 315 906 290 | 4 060 704 006 019 620 994 | 1 932 355 208 | 49,636 |- | 1023 | 1 925 320 391 606 803 968 923 | 37 083 513 766 578 631 309 | 7 250 186 216 | 51,939 |- | 1024 | 18 435 599 767 349 200 867 866 | 339 996 354 713 708 049 069 | 17 146 907 278 | 54,243 |- | 1025 | 176 846 309 399 143 769 411 680 | 3 128 516 637 843 038 351 228 | 55 160 980 939 | 56,546 |- | 1026 | 1 699 246 750 872 437 141 327 603 | 28 883 358 936 853 188 823 261 | 155 891 678 121 | 58,850
thumb|300px|A grafikon a π(x) prímszámláló függvény két közelítéséhez, az x/ln x-hez és a Li(x)-hez való arányát mutatja. Az x növekedésével (vegyük észre, hogy az x tengely logaritmikus beosztású), mindkét arány 1-hez tart. Az x/ln x felülről konvergál, viszonylag lassan, míg az Li(x) alulról, gyorsabban. Az On-Line Encyclopedia of Integer Sequences között a π(x) oszlop megtalálható , a π(x) − x / ln x oszlop a és a li(x) − π(x) oszlop pedig a sorozatnál.
A π(1024)-nél szereplő értéket először J. Buethe, J. Franke, A. Jost és T. Kleinjung számolta ki a Riemann-sejtés igazát feltételezve. Ezt a számítást később a feltétel nélkül is elvégezte D. J. Platt. A π(1025) értéket J. Buethe, J. Franke, A. Jost és T. Kleinjung, a π(1026) értéket pedig D. B. Staple számolta ki. A táblázat többi értékét a fenti munka során ellenőrizték.
Algoritmusok a π(x) értékének meghatározására
Triviális módja meghatározásának, ha nem túl nagy, hogy meghatározzuk az -nél nem nagyobb prímeket (akár Eratoszthenész szitájával), majd megszámoljuk őket.
Legendre kifinomultabb módszert talált kiszámolására: adott -re, ha különböző prímszámok, akkor az olyan egészek száma, melyek nem nagyobbak -nél és nem oszthatók egyetlen -vel sem, éppen
(ahol az alsó egészrész függvényt jelöli). A szám tehát egyenlő a következővel:
ahol a számok az négyzetgyökénél nem nagyobb prímszámok.
1870 és 1885 között megjelent cikksorozatában Ernst Meissel bemutatott egy praktikus kombinatorikai módszert kiszámolására. Legyen , az első prímszám, jelölje az -nél nem nagyobb természetes számokat, melyek nem oszthatók egyik -vel sem. Ekkor
Adott természetes számra, ha és , akkor
Ezt a megközelítést használva Meissel kiszámította -et az egyenlő 5, 106, 107 és 108 értékekre.
1959-ben Derrick Henry Lehmer kiterjesztette és egyszerűsítette Meissel módszerét. Az valós számra és az és természetes számokra definiáljuk -et úgy, hogy az m-nél nem nagyobb, de pontosan k darab, -nél nagyobb prímtényezővel rendelkező számok számát adja. Továbbá, legyen . Ekkor
ahol valójában csak véges számú nem nulla tagot összegzünk. Jelöljön olyan egész számot, amire igaz, hogy , és -et állítsuk értékre. Ekkor és , ha ≥ 3. Emiatt
A értéke így számítható:
Másrészről, a kiszámítása elvégezhető a következő szabályok alapján:
Ezzel a módszerrel és egy IBM 701 elektroncsöves számítógéppel Lehmer képes volt kiszámítani értékét.
A módszert a későbbiekben Lagarias, Miller, Odlyzko, Deléglise és Rivat tökéletesítették.
Más prímszámláló függvények Definiáltak más prímszámláló függvényeket is, melyekkel bizonyos feladatok kényelmesebben elvégezhetők. Az egyik ilyen a Riemann-féle prímszámláló függvény, aminek jelölése vagy . Ez a függvény a pn prímhatványoknál 1/n ugrásokat végez, a nem prímhatvány helyeken pedig a két szélső prímhatvány átlagát veszi fel. Ennek az az értelme, hogy a függvény értéke meghatározható egy inverz Mellin-transzformációval. Szabatosan a így definiálható:
ahol p prímszám.
Így is felírható:
ahol Λ(n) a von Mangoldt-függvény és
A Möbius-féle megfordítási formula ekkor kiadja, hogy:
A Riemann-féle zéta-függvény logaritmusának és a von Mangoldt-függvény ismeretében, a Perron-képlet felhasználásával:
A Csebisev-függvények a prímeket vagy pn prímhatványokat ln(p)-vel súlyozva összegeznek:
Prímszámláló függvények képletei A prímszámláló függvényképletek kétfajták lehetnek: számelméleti és analitikus formulák. Az analitikus prímszámlálási képleteket először a prímszámtétel bizonyítására használták. Riemann és von Mangoldt munkásságából erednek, és általában explicit formuláknak nevezik őket.
Van tehát a következő képletünk ψ-re:
ahol
Itt ρ a Riemann-féle zéta-függvény zérushelyei a kritikus sávban, ahol a ρ valós része 0 és 1 közé esik. A képlet érvényes az x>1 értékekre, ami az érdekes terület. A gyökök összege feltételesen konvergens, és a képzetes rész növekvő abszolút értékének sorrendjében kell elvégezni az összegzést. Vegyük észre, hogy ugyanez az összeg a triviális gyökökön elvégezve a képlet utolsó kivonandóját adja.
A -re bonyolultabb képletünk van:
Itt is az látható, hogy a képlet érvényes x > 1-re, ahol ρ a zéta-függvény nem triviális zérushelyei abszolút értékeik szerint rendezve, a második integrál, negatív előjellel, pedig ugyanaz az összeg, csak a triviális zérushelyeken. Az első tag li(x)-e a szokásos logaritmikus integrálfüggvény; a második tag li(xρ) kifejezését úgy kell érteni, mint Ei(ρ ln x), ahol Ei a pozitív valós számokon értelmezett exponenciális integrál függvény analitikus folytatása a komplex síkra, a negatív valós számok tengelyén.
Így a Möbius-féle megfordítási formula kiadja, hogy
ami x > 1-re van értelmezve, és ahol
az úgynevezett Riemann-féle R-függvény. Ez utóbbi sort Gram-sornak nevezik és minden pozitív x-re konvergens.
A képletében a nem triviális zérushelyek összege fluktuációit írja le, a maradék tagok pedig a prímszámláló függvény „sima” részét alkotják, így használható a
képlet a legjobb becsléseként az x > 1 értékekre.
A „zajos” rész amplitúdója heurisztikusan körül van, így a prímszámok eloszlásának fluktuációi megjeleníthetők a Δ-függvény segítségével:
A Δ(x) különböző helyeken vett értéket tartalmazó táblázat elérhető.
Egyenlőtlenségek Néhány hasznos egyenlőtlenség π(x)-szel kapcsolatban.
ha x ≥ 17. A bal oldali egyenlőtlenség minden x ≥ 17-re, a jobb oldali egyenlőtlenség minden x > 1-re teljesül.
Az 1,25506 konstans magyarázata itt olvasható: .
Pierre Dusart igazolta 2010-ben, hogy:
, ha és
, ha .
Néhány az n-edik prímszámra, pn-re vonatkozó egyenlőtlenség. ha n ≥ 6. A bal oldali egyenlőtlenség minden n ≥ 1-re, a jobb oldali minden n ≥ 6-ra teljesül.
Az n-edik prímszám közelítő értéke:
Jól ismert jegyzetfüzetében Rámánudzsan bizonyítja, hogy a egyenlőtlenség teljesül elegendően nagy értékeire.
A Riemann-sejtés A Riemann-sejtés megfelel a -re való becslés sokkal szigorúbb hibakorlátjának, és így a prímszámok szabályosabb eloszlásának:
Specifikusan,
Kapcsolódó szócikkek Bertrand-posztulátum Oppermann-sejtés Foias-állandó
Jegyzetek
További információk Chris Caldwell, The Nth Prime Page at The Prime Pages. Tomás Oliveira e Silva, Tables of prime-counting functions.
Kategória:Analitikus számelmélet Kategória:Prímszámok Kategória:Számelméleti függvények