Prímszámláló függvény
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
|}

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.

Analitikus számelmélet
Prímszámok
Számelméleti függvények
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 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ételtban egymástól függetlenül Jacques Hadamard és Charles de la Vallée Poussin is bebizonyította , a Riemann általben 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átban 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 megkü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 ) |- | | 4 | −0,3 |2 |500 |- | | |3 |1 |000 |- | | | | |952 |- | |229 | | |137 |- | |592 | | |425 |- | |498 |116 | |740 |- | |579 |158 | |047 |- | |761 455 |774 | |357 |- | |847 534 |592 592 |701 |667 |- | |052 511 |758 029 |104 |975 |- | |118 054 813 |923 159 |588 |283 |- | |607 912 018 |416 705 193 |263 |590 |- | |065 536 839 |992 858 452 |971 |896 |- | |204 941 750 802 |838 308 636 |890 |202 |- | |844 570 422 669 |604 962 452 |052 619 |507 |- | |238 341 033 925 |804 289 844 393 |214 632 |812 |- | |623 557 157 654 233 |883 734 693 281 |956 589 |116 |- | |739 954 287 740 860 |483 070 893 536 |949 555 |420 |- | |057 667 276 344 607 |481 624 169 369 960 |877 775 |725 |- | |220 819 602 560 918 840 |347 193 044 659 701 |744 644 |028 |- | |127 269 486 018 731 928 |579 871 578 168 707 |394 254 |332 |- | |467 286 689 315 906 290 |060 704 006 019 620 994 |932 355 208 |636 |- | |925 320 391 606 803 968 923 |083 513 766 578 631 309 |250 186 216 |939 |- | |435 599 767 349 200 867 866 |996 354 713 708 049 069 |146 907 278 |243 |- | |846 309 399 143 769 411 680 |128 516 637 843 038 351 228 |160 980 939 |546 |- | |699 246 750 872 437 141 327 603 |883 358 936 853 188 823 261 |891 678 121 |850 | } 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 éskö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őésé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 IBMelektroncsö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áln 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éskö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 >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 >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 >é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 ≥ A bal oldali egyenlőtlenség minden x ≥re , a jobb oldali egyenlőtlenség minden x >re teljesül . Az25506 konstans magyarázata itt olvasható : \ . Pierre Dusart igazoltaben , hogy : ha és ha\ . Néhány az n-edik prímszámra , pn-re vonatkozó egyenlőtlenség . ha n ≥ A bal oldali egyenlőtlenség minden n ≥re , a jobb oldali minden n ≥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 . Analitikus számelmélet Prímszámok Számelméleti függvények