素数计数函数
历史
在数论中,素数计数函数的增长率引起了很大的兴趣。在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)的方法
如果不太大,一个简单的计算的方法就是使用埃拉托斯特尼筛法。
一个比较复杂的计算的方法是勒让德发现的:给定,如果、 、 ……、 是不同的素数,则小于且不能被任何一个整除的整数个数是:
(其中是取整函数)。因此这个数等于:
其中是小于或等于的平方根的素数的个数。
恩斯特·梅塞尔(Ernst Meissel)在1870年和1885年发表的一系列文章中,描述并使用了一个计算的组合方法。设, , …, 是最初个素数,不大于且不能整除任何一个的自然数个数记为,那么:
给定一个自然数,如果且,那么:
利用这种方法,梅塞尔计算了等于5×105、106、107以及108时的值。
1959年,德里克·亨利·勒梅尔(Derrick Henry Lehmer)推广并简化了梅塞尔的方法。对于实数和自然数和,定义为不大于m且正好有k个大于的素因子的整数个数。更进一步,设定。那么:
这个和实际上只有有限个非零的项。设为一个整数,使得,并设。那么当 ≥ 3时,且。因此:
的计算可以用这种方法来获得:
另一方面,的计算可以用以下规则来完成:
利用这种方法,勒梅尔计算了。
其它素数计数函数
我们也使用其它的素数计数函数,因为它们更方便。其中一个是黎曼的素数计数函数,通常记为。这个函数在自变量为素数的幂pn时突然增加了1/n,而该点的值则是两边的平均值。我们可以用以下公式来定义:
其中p是素数。
也可以写成以下公式:
其中Λ(n)是馮·曼戈爾特函數,
利用默比乌斯反演公式,可得:
知道了黎曼ζ函数的对数与馮·曼戈爾特函數之间的关系,并利用Perron公式,可得:
不等式
下面是一些有用的π(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. . 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. . Dover Publications. 2005. ISBN 0-486-44232-2.
- Ireland, Kenneth; Rosen, Michael. 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