質數計算函數
在數學中,質數計數函數是一個用來表示小於或等於某個實數x的質數的個數的函數,記為。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/dc/PrimePi.svg/400px-PrimePi.svg.png)
歷史
編輯在數論中,質數計數函數的增長率引起了很大的興趣。在18世紀末,高斯和勒壤得曾猜想這個函數大約為:
也就是
這就是質數定理。一個等價的表述,是:
其中 是對數積分函數。這個定理在1896年由法國數學家雅克·阿達馬和比利時數學家德·拉·瓦萊布桑先後獨立給出證明。證明用到了黎曼ζ函數的性質。
目前已知 還有更精確的估計,例如:
其中O是大O符號。1948年,阿特勒·塞爾伯格和保羅·艾狄胥不使用函數或複分析證明了質數定理。
另外一個關於質數計數函數的增長率的猜想,是:
π(x)、x / ln x和li(x)
編輯x π(x) π(x) − x / ln x li(x) − π(x) x / π(x) x / ln x % Error 10 4 −0.3 2.2 2.500 -7.5% 102 25 3.3 5.1 4.000 13.20% 103 168 23 10 5.952 13.69% 104 1,229 143 17 8.137 11.64% 105 9,592 906 38 10.425 9.45% 106 78,498 6,116 130 12.740 7.79% 107 664,579 44,158 339 15.047 6.64% 108 5,761,455 332,774 754 17.357 5.78% 109 50,847,534 2,592,592 1,701 19.667 5.10% 1010 455,052,511 20,758,029 3,104 21.975 4.56% 1011 4,118,054,813 169,923,159 11,588 24.283 4.13% 1012 37,607,912,018 1,416,705,193 38,263 26.590 3.77% 1013 346,065,536,839 11,992,858,452 108,971 28.896 3.47% 1014 3,204,941,750,802 102,838,308,636 314,890 31.202 3.21% 1015 29,844,570,422,669 891,604,962,452 1,052,619 33.507 2.99% 1016 279,238,341,033,925 7,804,289,844,393 3,214,632 35.812 2.79% 1017 2,623,557,157,654,233 68,883,734,693,281 7,956,589 38.116 2.63% 1018 24,739,954,287,740,860 612,483,070,893,536 21,949,555 40.420 2.48% 1019 234,057,667,276,344,607 5,481,624,169,369,960 99,877,775 42.725 2.34% 1020 2,220,819,602,560,918,840 49,347,193,044,659,701 222,744,644 45.028 2.22% 1021 21,127,269,486,018,731,928 446,579,871,578,168,707 597,394,254 47.332 2.11% 1022 201,467,286,689,315,906,290 4,060,704,006,019,620,994 1,932,355,208 49.636 2.02% 1023 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309 7,250,186,216 51.939 1.93% 1024 18,435,599,767,349,200,867,866 339,996,354,713,708,049,069 17,146,907,278 54.243 1.84% 1025 176,846,309,399,143,769,411,680 3,128,516,637,843,038,351,228 55,160,980,939 56.546 1.77% 1026 1,699,246,750,872,437,141,327,603 28,883,358,936,853,188,823,261 155,891,678,121 58.850 1.70% 1027 16,352,460,426,841,680,446,427,399 267,479,615,610,131,274,163,365 508,666,658,006 61.153 1.64%
計算π(x)的方法
編輯如果 不太大,一個簡單的計算 的方法就是算出每個質數(比如使用埃拉托斯特尼篩法)。
一個比較複雜的計算 的方法是勒壤得發現的:給定 ,如果 、 、 ……、 是不同的質數,則小於 且不能被任何一個 整除的整數個數是:
(其中 是取整函數)。因此這個數等於:
其中 是小於或等於 的平方根的質數的個數。
恩斯特·梅塞爾在1870年和1885年發表的一系列文章中,描述並使用了一個計算 的組合方法。設 , , …, 是最初 個質數,不大於 且不能整除任何一個 的自然數個數記為 ,那麼:
給定一個自然數 ,如果 且 ,那麼:
利用這種方法,梅塞爾計算了 等於5×105、106、107以及108時 的值。
1959年,德里克·亨利·勒梅爾推廣並簡化了梅塞爾的方法。對於實數 和自然數 和 ,定義 為不大於m且正好有k個大於 的質因子的整數個數。更進一步,設定 。那麼:
這個和實際上只有有限個非零的項。設 為一個整數,使得 ,並設 。那麼當 ≥ 3時, 且 。因此:
的計算可以用這種方法來獲得:
另一方面, 的計算可以用以下規則來完成:
利用這種方法,勒梅爾計算了 。
其它質數計數函數
編輯我們也使用其它的質數計數函數,因為它們更方便。其中一個是黎曼的質數計數函數,通常記為 。這個函數在自變數為質數的冪pn時突然增加了1/n,而該點的值則是兩邊的平均值。我們可以用以下公式來定義 :
其中p是質數。
也可以寫成以下公式:
其中Λ(n)是馮·曼戈爾特函數,
利用默比烏斯反演公式,可得:
知道了黎曼ζ函數的對數與馮·曼戈爾特函數 之間的關係,並利用佩龍公式,可得:
不等式
編輯下面是一些有用的π(x)不等式。
- ,左不等式適用於x ≥ 17,右不等式適用於x>1,常數1.25506為 保留5位有效小數, 最大值為x = 113。
Pierre Dusart 在2010年證明:
- (其中 )
- (其中 )
第n個質數pn的不等式:
左面的不等式當n ≥ 2時成立,右面的不等式當n ≥ 6時成立,上限由Rosser(1941)提出,下限由Dusrat(1999)提出。
第n個質數的一個估計是:
參考文獻
編輯- Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory. MIT Press. 1996: volume 1 page 234 section 8.8. ISBN 0-262-02405-5.
- Marc Deléglise and Jöel Rivat, Computing : The Meissel, Lehmer, Lagarias, Miller, Odlyzko method(頁面存檔備份,存於網際網路檔案館), Mathematics of Computation, vol. 65, number 33, January 1996, pages 235–245
- Dickson, Leonard Eugene. History of the Theory of Numbers I: Divisibility and Primality. Dover Publications. 2005. ISBN 0-486-44232-2.
- Ireland, Kenneth; Rosen, Michael. A Classical Introduction to Modern Number Theory Second edition. Springer. 1998. ISBN 0-387-97329-X.
- Hwang H. Cheng Prime Magic conference given at the University of Bordeaux (France) at year 2001 Démarches de la Géométrie et des Nombres de l'Université du Bordeaux
- Titchmarsh, E. C. The Theory of Functions, 2nd ed. Oxford, England: Oxford University Press, 1960.
- Oliveira e Silva, Tomás Tables of values of pi(x) and of pi2(x) (頁面存檔備份,存於網際網路檔案館)
- Gourdon, Xavier; Sebah,Pascal PrimePi values thru 4E22(頁面存檔備份,存於網際網路檔案館)