素数计数函数

维基百科,自由的百科全书
跳转至: 导航搜索

数学中,素数计数函数是一个用来表示小于或等于某个实数x素数的个数的函数,记为\scriptstyle\pi(x)

π(n)的最初60个值

历史[编辑]

数论中,素数计数函数的增长率引起了很大的兴趣。在18世纪末,高斯勒让德曾猜想这个函数大约为:

 x/\operatorname{ln}(x)\!

也就是

\lim_{x\rightarrow\infty}\frac{\pi(x)}{x/\operatorname{ln}(x)}=1.\!

这就是素数定理。一个等价的表述,是:

\lim_{x\rightarrow\infty}\pi(x) / \operatorname{li}(x)=1\!

其中\operatorname{li}(x)对数积分函数。这个定理在1896年得到证明。证明用到了黎曼ζ函数的性质。

目前已知\pi(x)\!还有更精确的估计,例如:

\pi(x) = \operatorname{li}(x) + \mathrm{O} \left( x \exp \left( -\frac{\sqrt{\ln(x)}}{15} \right) \right)\!

其中O大O符号。1948年,阿特勒·塞爾伯格保罗·埃尔德什不使用函数或复分析证明了素数定理。

另外一个关于素数计数函数的增长率的猜想,是:

 \sum_{p \le 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)
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

计算π(x)的方法[编辑]

如果x不太大,一个简单的计算\pi(x)的方法就是使用埃拉托斯特尼筛法

一个比较复杂的计算\pi(x)的方法是勒让德发现的:给定x,如果p_1、 p_2、 ……、 p_k是不同的素数,则小于x且不能被任何一个p_i整除的整数个数是:

\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots,

(其中\lfloor\cdot\rfloor取整函数)。因此这个数等于:

\pi(x)-\pi\left(\sqrt{x}\right)+1\,

其中p_1, p_2,\dots,p_k是小于或等于x的平方根的素数的个数。

恩斯特·梅塞尔Ernst Meissel)在1870年和1885年发表的一系列文章中,描述并使用了一个计算\pi(x)的组合方法。设p_1p_2, …, p_n是最初n个素数,不大于m且不能整除任何一个p_i的自然数个数记为\Phi(m,n),那么:

\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right).\,

给定一个自然数m,如果n=\pi\left(\sqrt[3]{m}\right)\mu=\pi\left(\sqrt{m}\right)-n,那么:

\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等于5×105、106、107以及108\pi(x)的值。

1959年,德里克·亨利·勒梅尔Derrick Henry Lehmer)推广并简化了梅塞尔的方法。对于实数m和自然数nk,定义P_k(m,n)为不大于m且正好有k个大于p_n的素因子的整数个数。更进一步,设定P_0(m,n)=1。那么:

\Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n),\,

这个和实际上只有有限个非零的项。设y为一个整数,使得\sqrt[3]{m}\le y\le\sqrt{m},并设n=\pi(y)。那么当k ≥ 3时,P_1(m,n)=\pi(m)-nP_k(m,n)=0。因此:

\pi(m)=\Phi(m,n)+n-1-P_2(m,n).

P_2(m,n)的计算可以用这种方法来获得:

P_2(m,n)=\sum_{y<p\le\sqrt{m}}\left(\pi\left(\frac mp\right)-\pi(p)+1\right).\,

另一方面,\Phi(m,n)的计算可以用以下规则来完成:

  1. \Phi(m,0)=\lfloor m\rfloor;\,
  2. \Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right).\,

利用这种方法,勒梅尔计算了\pi\left(10^{10}\right)

其它素数计数函数[编辑]

我们也使用其它的素数计数函数,因为它们更方便。其中一个是黎曼的素数计数函数,通常记为\Pi_0(x)。这个函数在自变量为素数的幂pn时突然增加了1/n,而该点的值则是两边的平均值。我们可以用以下公式来定义\Pi_0(x)

\Pi_0(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg)

其中p是素数。

也可以写成以下公式:

\Pi_0(x) = \sum_2^x \frac{\Lambda(n)}{\ln n} - \frac12 \frac{\Lambda(x)}{\ln x} = \sum_{n=1}^\infty \frac1n \pi_0(x^{1/n})

其中Λ(n)是馮·曼戈爾特函數

\pi_0(x) = \lim_{\varepsilon \rightarrow 0}\frac{\pi(x-\varepsilon)+\pi(x+\varepsilon)}2.

利用默比乌斯反演公式,可得:

\pi_{0}(x) = \sum_{n=1}^\infty \frac{\mu(n)}n \Pi_0(x^{1/n})

知道了黎曼ζ函数的对数与馮·曼戈爾特函數\Lambda之间的关系,并利用Perron公式,可得:

\ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s+1}\,dx

不等式[编辑]

这里有一些π(x)的有用的不等式。

 
\pi(x) < 1.25506 \frac {x} {\log x}
\!,x > 1。
 
\frac {x} {\log x + 2} < \pi(x) <  \frac {x} {\log x - 4}
\!,x ≥ 55。

这里有一些关于第n个素数pn的不等式。

 
n\ \ln n + n\ln\ln n - n  < p_n <  n \ln n + n \ln \ln n
\!n ≥ 6。

左面的不等式当n ≥ 1时成立,右面的不等式当n ≥ 6时成立。

n个素数的一个估计是:

 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. 
  • 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.