在數學 中,質數計數函數 是一個用來表示小於或等於某個實數 x 的質數 的個數的函數 ,記為
π
(
x
)
{\displaystyle \pi (x)}
。
π(n )的最初60個值
歷史
在數論 中,質數計數函數的增長率 引起了很大的興趣。在18世紀末,高斯 和勒壤得 曾猜想這個函數大約為:
x
/
ln
(
x
)
{\displaystyle x/\operatorname {ln} (x)\!}
也就是
lim
x
→
∞
π
(
x
)
x
/
ln
(
x
)
=
1.
{\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\operatorname {ln} (x)}}=1.\!}
這就是質數定理 。一個等價的表述,是:
lim
x
→
∞
π
(
x
)
/
li
(
x
)
=
1
{\displaystyle \lim _{x\rightarrow \infty }\pi (x)/\operatorname {li} (x)=1\!}
其中
li
(
x
)
{\displaystyle \operatorname {li} (x)}
是對數積分 函數。這個定理在1896年由法國 數學家雅克·阿達馬 和比利時 數學家德·拉·瓦萊布桑 先後獨立給出證明 。證明用到了黎曼ζ函數 的性質。
目前已知
π
(
x
)
{\displaystyle \pi (x)\!}
還有更精確的估計,例如:
π
(
x
)
=
li
(
x
)
+
O
(
x
exp
(
−
ln
(
x
)
15
)
)
{\displaystyle \pi (x)=\operatorname {li} (x)+\mathrm {O} \left(x\exp \left(-{\frac {\sqrt {\ln(x)}}{15}}\right)\right)\!}
其中O 是大O符號 。1948年,阿特勒·塞爾伯格 和保羅·艾狄胥 不使用函數或複分析 證明了質數定理。
另外一個關於質數計數函數的增長率 的猜想,是:
∑
p
≤
x
p
n
∼
π
(
x
n
+
1
)
∼
L
i
(
x
n
+
1
)
.
{\displaystyle \sum _{p\leq x}p^{n}\sim \pi (x^{n+1})\sim Li(x^{n+1}).}
π(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 )的方法
如果
x
{\displaystyle x}
不太大,一個簡單的計算
π
(
x
)
{\displaystyle \pi (x)}
的方法就是算出每個質數(比如使用埃拉托斯特尼篩法 )。
一個比較複雜的計算
π
(
x
)
{\displaystyle \pi (x)}
的方法是勒壤得 發現的:給定
x
{\displaystyle x}
,如果
p
1
{\displaystyle p_{1}}
、
p
2
{\displaystyle p_{2}}
、 ……、
p
k
{\displaystyle p_{k}}
是不同的質數,則小於
x
{\displaystyle x}
且不能被任何一個
p
i
{\displaystyle p_{i}}
整除的整數個數是:
⌊
x
⌋
−
∑
i
⌊
x
p
i
⌋
+
∑
i
<
j
⌊
x
p
i
p
j
⌋
−
∑
i
<
j
<
k
⌊
x
p
i
p
j
p
k
⌋
+
⋯
,
{\displaystyle \lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots ,}
(其中
⌊
⋅
⌋
{\displaystyle \lfloor \cdot \rfloor }
是取整函數 )。因此這個數等於:
π
(
x
)
−
π
(
x
)
+
1
{\displaystyle \pi (x)-\pi \left({\sqrt {x}}\right)+1\,}
其中
p
1
,
p
2
,
…
,
p
k
{\displaystyle p_{1},p_{2},\dots ,p_{k}}
是小於或等於
x
{\displaystyle x}
的平方根的質數的個數。
恩斯特·梅塞爾 在1870年和1885年發表的一系列文章中,描述並使用了一個計算
π
(
x
)
{\displaystyle \pi (x)}
的組合方法。設
p
1
{\displaystyle p_{1}}
,
p
2
{\displaystyle p_{2}}
, …,
p
n
{\displaystyle p_{n}}
是最初
n
{\displaystyle n}
個質數,不大於
m
{\displaystyle m}
且不能整除任何一個
p
i
{\displaystyle p_{i}}
的自然數個數記為
Φ
(
m
,
n
)
{\displaystyle \Phi (m,n)}
,那麼:
Φ
(
m
,
n
)
=
Φ
(
m
,
n
−
1
)
−
Φ
(
[
m
p
n
]
,
n
−
1
)
.
{\displaystyle \Phi (m,n)=\Phi (m,n-1)-\Phi \left(\left[{\frac {m}{p_{n}}}\right],n-1\right).\,}
給定一個自然數
m
{\displaystyle m}
,如果
n
=
π
(
m
3
)
{\displaystyle n=\pi \left({\sqrt[{3}]{m}}\right)}
且
μ
=
π
(
m
)
−
n
{\displaystyle \mu =\pi \left({\sqrt {m}}\right)-n}
,那麼:
π
(
m
)
=
Φ
(
m
,
n
)
+
n
(
μ
+
1
)
+
μ
2
−
μ
2
−
1
−
∑
k
=
1
μ
π
(
m
p
n
+
k
)
.
{\displaystyle \pi (m)=\Phi (m,n)+n(\mu +1)+{\frac {\mu ^{2}-\mu }{2}}-1-\sum _{k=1}^{\mu }\pi \left({\frac {m}{p_{n+k}}}\right).\,}
利用這種方法,梅塞爾計算了
x
{\displaystyle x}
等於5×105 、106 、107 以及108 時
π
(
x
)
{\displaystyle \pi (x)}
的值。
1959年,德里克·亨利·勒梅爾 推廣並簡化了梅塞爾的方法。對於實數
m
{\displaystyle m}
和自然數
n
{\displaystyle n}
和
k
{\displaystyle k}
,定義
P
k
(
m
,
n
)
{\displaystyle P_{k}(m,n)}
為不大於m 且正好有k 個大於
p
n
{\displaystyle p_{n}}
的質因子的整數個數。更進一步,設定
P
0
(
m
,
n
)
=
1
{\displaystyle P_{0}(m,n)=1}
。那麼:
Φ
(
m
,
n
)
=
∑
k
=
0
+
∞
P
k
(
m
,
n
)
,
{\displaystyle \Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n),\,}
這個和實際上只有有限個非零的項。設
y
{\displaystyle y}
為一個整數,使得
m
3
≤
y
≤
m
{\displaystyle {\sqrt[{3}]{m}}\leq y\leq {\sqrt {m}}}
,並設
n
=
π
(
y
)
{\displaystyle n=\pi (y)}
。那麼當
k
{\displaystyle k}
≥ 3時,
P
1
(
m
,
n
)
=
π
(
m
)
−
n
{\displaystyle P_{1}(m,n)=\pi (m)-n}
且
P
k
(
m
,
n
)
=
0
{\displaystyle P_{k}(m,n)=0}
。因此:
π
(
m
)
=
Φ
(
m
,
n
)
+
n
−
1
−
P
2
(
m
,
n
)
.
{\displaystyle \pi (m)=\Phi (m,n)+n-1-P_{2}(m,n).}
P
2
(
m
,
n
)
{\displaystyle P_{2}(m,n)}
的計算可以用這種方法來獲得:
P
2
(
m
,
n
)
=
∑
y
<
p
≤
m
(
π
(
m
p
)
−
π
(
p
)
+
1
)
.
{\displaystyle P_{2}(m,n)=\sum _{y<p\leq {\sqrt {m}}}\left(\pi \left({\frac {m}{p}}\right)-\pi (p)+1\right).\,}
另一方面,
Φ
(
m
,
n
)
{\displaystyle \Phi (m,n)}
的計算可以用以下規則來完成:
Φ
(
m
,
0
)
=
⌊
m
⌋
;
{\displaystyle \Phi (m,0)=\lfloor m\rfloor ;\,}
Φ
(
m
,
b
)
=
Φ
(
m
,
b
−
1
)
−
Φ
(
m
p
b
,
b
−
1
)
.
{\displaystyle \Phi (m,b)=\Phi (m,b-1)-\Phi \left({\frac {m}{p_{b}}},b-1\right).\,}
利用這種方法,勒梅爾計算了
π
(
10
10
)
{\displaystyle \pi \left(10^{10}\right)}
。
其它質數計數函數
我們也使用其它的質數計數函數,因為它們更方便。其中一個是黎曼的質數計數函數,通常記為
Π
0
(
x
)
{\displaystyle \Pi _{0}(x)}
。這個函數在自變數為質數的冪p n 時突然增加了1/n ,而該點的值則是兩邊的平均值。我們可以用以下公式來定義
Π
0
(
x
)
{\displaystyle \Pi _{0}(x)}
:
Π
0
(
x
)
=
1
2
(
∑
p
n
<
x
1
n
+
∑
p
n
≤
x
1
n
)
{\displaystyle \Pi _{0}(x)={\frac {1}{2}}{\bigg (}\sum _{p^{n}<x}{\frac {1}{n}}\ +\sum _{p^{n}\leq x}{\frac {1}{n}}{\bigg )}}
其中p 是質數。
也可以寫成以下公式:
Π
0
(
x
)
=
∑
2
x
Λ
(
n
)
ln
n
−
1
2
Λ
(
x
)
ln
x
=
∑
n
=
1
∞
1
n
π
0
(
x
1
/
n
)
{\displaystyle \Pi _{0}(x)=\sum _{2}^{x}{\frac {\Lambda (n)}{\ln n}}-{\frac {1}{2}}{\frac {\Lambda (x)}{\ln x}}=\sum _{n=1}^{\infty }{\frac {1}{n}}\pi _{0}(x^{1/n})}
其中Λ(n )是馮·曼戈爾特函數 ,
π
0
(
x
)
=
lim
ε
→
0
π
(
x
−
ε
)
+
π
(
x
+
ε
)
2
.
{\displaystyle \pi _{0}(x)=\lim _{\varepsilon \rightarrow 0}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}{2}}.}
利用默比烏斯反演公式 ,可得:
π
0
(
x
)
=
∑
n
=
1
∞
μ
(
n
)
n
Π
0
(
x
1
/
n
)
{\displaystyle \pi _{0}(x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\Pi _{0}(x^{1/n})}
知道了黎曼ζ函數 的對數與馮·曼戈爾特函數
Λ
{\displaystyle \Lambda }
之間的關係,並利用佩龍公式 ,可得:
ln
ζ
(
s
)
=
s
∫
0
∞
Π
0
(
x
)
x
−
s
+
1
d
x
{\displaystyle \ln \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{-s+1}\,dx}
不等式
下面是一些有用的π(x )不等式。
x
ln
x
<
π
(
x
)
<
1.25506
x
ln
x
{\displaystyle {\frac {x}{\ln x}}<\pi (x)<1.25506{\frac {x}{\ln x}}\!}
,左不等式適用於x ≥ 17,右不等式適用於x>1,常數1.25506為
30
ln
113
113
{\displaystyle {\frac {30\ln 113}{113}}}
保留5位有效小數,
π
(
x
)
ln
x
x
{\displaystyle {\frac {\pi (x)\ln x}{x}}}
最大值為x = 113。
Pierre Dusart 在2010年證明:
x
ln
x
−
1
<
π
(
x
)
{\displaystyle {\frac {x}{\ln x-1}}<\pi (x)\!}
(其中
x
≥
5393
{\displaystyle x\geq 5393}
)
π
(
x
)
<
x
ln
x
−
1.1
{\displaystyle \pi (x)<{\frac {x}{\ln x-1.1}}\!}
(其中
x
≥
60184
{\displaystyle x\geq 60184}
)
第n 個質數p n 的不等式:
n
ln
n
+
n
ln
ln
n
−
n
<
p
n
<
n
ln
n
+
n
ln
ln
n
{\displaystyle n\ln n+n\ln \ln n-n<p_{n}<n\ln n+n\ln \ln n\!}
左面的不等式當n ≥ 2時成立,右面的不等式當n ≥ 6時成立,上限由Rosser(1941)提出,下限由Dusrat(1999)提出。
第n 個質數的一個估計是:
p
n
=
n
ln
n
+
n
ln
ln
n
−
n
+
n
ln
ln
n
−
2
n
ln
n
+
O
(
n
(
ln
ln
n
)
2
(
ln
n
)
2
)
.
{\displaystyle p_{n}=n\ln n+n\ln \ln n-n+{\frac {n\ln \ln n-2n}{\ln n}}+O\left({\frac {n(\ln \ln n)^{2}}{(\ln n)^{2}}}\right).}
參考文獻
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
π
(
x
)
{\displaystyle \pi (x)}
: 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.