選單圖示 主題
Search

素數計數函式

下載 Mathematica 筆記本下載 Wolfram 筆記本
PrimeCountingFunction

素數計數函式是函式 pi(x)，它給出小於或等於給定數 x 的素數的數量（Shanks 1993, p. 15）。例如，沒有小於或等於 <=1 的素數，所以 pi(1)=0。有一個素數 (2) 小於或等於 <=2，所以 pi(2)=1。有兩個素數（2 和 3）小於或等於 <=3，所以 pi(3)=2。以此類推。

素數計數函式的符號 pi(n) 有點不幸，因為它與常數 pi=3.1415... 沒有任何關係。這個符號是由數論學家 Edmund Landau 在 1909 年引入的，現在已經成為標準。正如 Derbyshire (2004, p. 38) 所說，“我很抱歉；這不是我的錯。你只能忍受它。”

令 p_n 表示第 n 個素數，p_n 是 pi(n) 的右逆，因為

pi(p_n)=n
(1)

對於所有正整數。此外，

p_(pi(n))=n
(2)

當且僅當 當且僅當 n 是素數。

對於 n=1, 2, ...，pi(n) 的前幾個值是 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, ... (OEIS A000720)。給出數字 x 的素數計數函式的 Wolfram 語言 命令是PrimePi[x]，它適用於最大值約為 x approx 8×10^(13)。

符號 pi_(a,b)(x) 用於表示模素數計數函式，即形式為 ak+b 且小於或等於 x 的素數的數量 (Shanks 1993, pp. 21-22)。

下表給出了 10 的冪的 pi(n) 值 (OEIS A006880)，擴充套件了其他印刷表格 (例如，Hardy and Wright 1979, p. 4; Shanks 1993, pp. 242-243; Ribenboim 1996, p. 237; Derbyshire 2004, p. 35)。請注意，Meissel (1885) 錯誤地計算了 pi(10^9) 為 50847478，誤差為 56 (Havil 2003, p. 171)，這個結果被 Hardy and Wright (1979) 和 Hardy (1999) 引用，有時（錯誤地）被稱為 Bertelsen 數。pi(10^(20)) 的值來自 Deleglise 和 Rivat (1996)，而 X. Gourdon 在 2000 年 10 月 27 日報告了 pi(10^(21))。Oliveira e Silva 和 X. Gourdon 獨立計算了 pi(10^(22)) 和 pi(10^(23)) 的值，但在 Gourdon 的計算中發現了一個錯誤。pi(10^(23)) 的值由 Tomás Oliveira e Silva 計算，他使用硬體和程式引數的集合驗證了這個結果（私人通訊，2008 年 4 月 7 日）。（Oliveira e Silva 和 X. Gourdon 獨立計算的 pi(x) 值對於所有高達 10^(22) 的 10 的冪都一致。）Büthe (2014) 計算了 pi(10^(25))，Staple 在 2014 年計算了 pi(10^(26)) (Staple 2015)，D. Baugh 和 K. Walisch (2015) 使用了 pi(10^(27)) 計算了primecount快速素數計數函式實現 (Walisch)。

npi(10^n)參考
14古代
225L. Pisano (1202; Beiler)
3168F. van Schooten (1657; Beiler)
41229F. van Schooten (1657; Beiler)
59592T. Brancker (1668; Beiler)
678498A. Felkel (1785; Beiler)
7664579J. P. Kulik (1867; Beiler)
85761455Meissel (1871; 已修正)
950847534Meissel (1886; 已修正)
10455052511Lehmer (1959; 已修正)
114118054813Bohmann (1972; 已修正)
1237607912018
13346065536839
143204941750802Lagarias et al. (1985)
1529844570422669Lagarias et al. (1985)
16279238341033925Lagarias et al. (1985)
172623557157654233M. Deleglise 和 J. Rivat (1994)
1824739954287740860Deleglise 和 Rivat (1996)
19234057667276344607M. Deleglise (1996 年 6 月 19 日)
202220819602560918840M. Deleglise (1996 年 6 月 19 日)
2121127269486018731928pi(x) 專案 (2000 年 12 月)
22201467286689315906290P. Demichel 和 X. Gourdon (2001 年 2 月)
231925320391606803968923T. Oliveira e Silva (私人通訊，2008 年 4 月 7 日)
2418435599767349200867866Platt
25176846309399143769411680Büthe (2014)
261699246750872437141327603Staple (2015)
2716352460426841680446427399D. Baugh 和 K. Walisch (2015)

數論中最基本和最重要的結果之一是 pi(n) 在 n 變大時的漸近形式。這由素數定理給出，該定理指出

pi(n)∼Li(n),
(3)

其中 Li(x) 是對數積分，∼ 是漸近符號。這個關係最初由高斯在 1792 年（他 15 歲時）提出，儘管直到 1849 年寫給 Johann Encke 的一封信中才透露，直到 1863 年才發表 (Gauss 1863; Havil 2003, pp. 176-177)。

PrimeCountingFunctions

下表比較了素數計數函式 pi(x)、黎曼素數計數函式 R(x) 和對數積分 Li(x) 對於 10 的冪，即 x=10^n。上面繪製了小 x 的相應差異。請注意，Hardy (1999, p. 26) 給出的 x=10^9 的值是不正確的。在下表中，[x] 表示最近整數函式。Borwein 和 Bailey (2003, p. 65) 給出了一個類似的表格，比較了 pi(10^n) 和 Li(10^n)。

SloaneA057794A057752
n[pi(10^n)-R(10^n)][pi(10^n)-Li(10^n)]
11-2
21-5
30-10
42-17
5-5-38
629-130
788-339
897-754
9-79-1701
10-1828-3104
11-2318-11588
12-1476-38263
13-5773-108971
14-19200-314890
1573218-1052619
16327052-3214632
17-598255-7956589
18-3501366-21949555
1923884333-99877775
20-4891825-222744644
21-86432204-597394254
22-127132665-1932355208

素數計數函式可以用勒讓德公式、萊梅公式、梅普斯方法或梅塞爾公式表示。Berndt (1994) 簡要介紹了計算 pi(n) 的嘗試歷史。下表取自 Riesel (1994)，其中 O(x) 是漸近符號。

方法時間複雜度儲存複雜度
Lagarias-Miller-OdlyzkoO(x^(2/3+epsilon))O(x^(1/3+epsilon))
Lagarias-Odlyzko 1O(x^(3/5+epsilon))O(x^epsilon)
Lagarias-Odlyzko 2O(x^(1/2+epsilon))O(x^(1/4+epsilon))
勒讓德公式O(x)O(x^(1/2))
萊梅O(x/(lnx)^4)O(x^(1/3)/lnx)
梅普斯方法O(x^(0.7))O(x^(0.7))
梅塞爾O(x/(lnx)^3)O(x^(1/2)/lnx)
PrimePiHarmonic

Locker-Ernst (Locker-Ernst 1959; Panaitopol 1999; Havil 2003, pp. 179-180) 提出的一個近似公式（如上圖所示）由下式給出

pi(n) approx n/(h_n),
(4)

其中 h_n 與調和數 H_n 的關係為 h_n=H_n-3/2。對於 50<=n<=1000，此公式在實際值的 approx 2 範圍內。pi(n)-n/h_n>0 為正值的 n 值是 1, 109, 113, 114, 199, 200, 201, ... (OEIS A051046)。Panaitopol (1999) 表明，對於所有 n>=1429，此量為正。

pi(n) 的上界由下式給出

pi(n)<(1.25506n)/(lnn)
(5)

對於 n>1，下界由下式給出

n/(lnn)<pi(n)
(6)

對於 n>=17 (Rosser 和 Schoenfeld 1962)。

Hardy 和 Wright (1979, p. 414) 給出了公式

pi(n)=-1+sum_(j=3)^n[(j-2)!-j|_((j-2)!)/j_|]
(7)

對於 n>3，其中 |_x_| 是向下取整函式。

素數計數函式的修改版本由下式給出

pi_0(p)={pi(p) for p composite; pi(p)-1/2 for p prime
(8)
pi_0(p)=sum_(n=1)^infty(mu(x)f(x^(1/n)))/n,
(9)

其中 mu(n) 是莫比烏斯函式，f(x) 是黎曼素數計數函式。

Ramanujan 還表明

(dpi(x))/(dx)∼1/(xlnx)sum_(n=1)^infty(mu(n))/nx^(1/n),
(10)

其中 mu(n) 是莫比烏斯函式 (Berndt 1994, p. 117; Havil 2003, p. 199)。

使得 x>=npi(x) 對於 n=2, 3, ... 成立的最小 x 是 2, 27, 96, 330, 1008, ... (OEIS A038625)，相應的 pi(x) 是 1, 9, 24, 66, 168, 437, ... (OEIS A038626)。x=npi(x) 對於 n=2, 3, ... 的解的數量是 4, 3, 3, 6, 7, 6, ... (OEIS A038627)。

Ramanujan 表明，對於足夠大的 x，

pi^2(x)<(ex)/(lnx)pi(x/e).
(11)

這對於 x=6, 9, 10, 12, 14, 15, 16, 18, ... (OEIS A091886) 成立。已知不等式不成立的最大素數是 38358837677 (Berndt 1994, pp. 112-113)。相關的不等式

[li(x)]^2<(ex)/(lnx)li(x/e)
(12)

其中

li(x)=int_0^x(dt)/(lnt),
(13)

對於 x>=2418 和沒有更小的數字成立 (Berndt 1994, p. 114)。

另請參閱

Bertelsen 數, 切比雪夫定理, 等數, 勒讓德常數, 勒讓德公式, Lehmer-Schur 方法, 對數積分, 梅普斯方法, 模素數計數函式, 素數算術級數, 素數計數串聯常數, 素數, 素數定理, 黎曼素數計數函式 在 課堂中探索此主題

相關 Wolfram 站點

http://functions.wolfram.com/NumberTheoryFunctions/PrimePi/

使用 探索

參考文獻

Baugh, D. 和 Walisch, K. "New Confirmed pi(1027) Prime Counting Function Record." https://www.mersenneforum.org/showthread.php?t=20473. 2015 年 9 月 6 日。Beiler, A. H. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, p. 218, 1966.Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, pp. 134-135, 1994.Booker, A. "The Nth Prime Page." http://primes.utm.edu/nthprime/.Borwein, J. 和 Bailey, D. "Prime Numbers and the Zeta Function." Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 63-72, 2003.Brent, R. P. "Irregularities in the Distribution of Primes and Twin Primes." Math. Comput. 29, 43-56, 1975.Büthe, J. "A Practical Analytic Method for Calculating pi(x) II." 2014 年 10 月 26 日。 http://arxiv.org/abs/1410.7008.Caldwell, C. "How Many Primes Are There?" http://primes.utm.edu/howmany.shtml.Deleglise, M. 和 Rivat, J. "Computing pi(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko Method." Math. Comput. 65, 235-245, 1996.Derbyshire, J. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. New York: Penguin, 2004.Finch, S. R. "Hardy-Littlewood Constants." §2.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 84-94, 2003.Forbes, T. "Prime k-tuplets." http://anthony.d.forbes.googlepages.com/ktuplets.htm.Gauss, C. F. Werke, Band 10, Teil I. p. 10, 1863.Gourdon, X. "New Record Computation for pi(x), x=10^21." 2000 年 10 月 27 日。 http://listserv.nodak.edu/scripts/wa.exe?A2=ind0010&L=nmbrthry&P=2988.Guiasu, S. "Is There Any Regularity in the Distribution of Prime Numbers at the Beginning of the Sequence of Positive Integers?" Math. Mag. 68, 110-121, 1995.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.Hardy, G. H. 和 Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 164-188, 2003.Lagarias, J.; Miller, V. S.; 和 Odlyzko, A. "Computing pi(x): The Meissel-Lehmer Method." Math. Comput. 44, 537-560, 1985.Lagarias, J. 和 Odlyzko, A. "Computing pi(x): An Analytic Method." J. Algorithms 8, 173-191, 1987.Locker-Ernst, L. "Bemerkung über die Verteilung der Primzahlen." Elemente Math. (Basel) 14, 1-5, 1959.Mapes, D. C. "Fast Method for Computing the Number of Primes Less than a Given Limit." Math. Comput. 17, 179-185, 1963.Meissel, E. D. F. "Über die Bestimmung der Primzahlmenge innerhalb gegebener Grenzen." Math. Ann. 2, 636-642, 1870.Meissel, E. D. F. "Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen vorkommen." Math. Ann. 25, 251-257, 1885.Nagell, T. "The Function pi(x)." §16 in Introduction to Number Theory. New York: Wiley, pp. 54-57, 1951.Panaitopol, L. "Several Approximations of pi(x)." Math. Ineq. Appl. 2, 317-324, 1999.Platt, D. "Computing pi(x) Analytically." 即將發表於 Math. Comput.Ribenboim, P. The New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, 1996.Riesel, H. "The Number of Primes Below x." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 10-12, 1994.Rosser, J. B. 和 Schoenfeld, L. "Approximate Formulas for Some Functions of Prime Numbers." Illinois J. Math. 6, 64-97, 1962.Séroul, R. "The Function pi(x)." §8.7 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 175-181, 2000.Shallit, J. http://www.math.uwaterloo.ca/~shallit/bib/pi.bib.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993.Sloane, N. J. A. Sequences A000720/M0256, A006880/M3608, A038625, A038626, A038627, A052434, A052435, A057752, A057794, and A091886 in "The On-Line Encyclopedia of Integer Sequences."Staple, D. B. "The Combinatorial Algorithm for Computing pi(x)." https://arxiv.org/abs/1503.01839. 2015 年 5 月 28 日。Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 74-76, 1991.Walisch, K. "Fast Prime Counting Function Implementations." https://github.com/kimwalisch/primecount.Wolf, M. "Unexpected Regularities in the Distribution of Prime Numbers." http://www.ift.uni.wroc.pl/~mwolf/.

在 中被引用

素數計數函式

引用為

Weisstein, Eric W. "Prime Counting Function." 來自 網路資源. https://mathworld.tw/PrimeCountingFunction.html

主題分類