在数学中,素数计数函数是一个用来表示小于或等于某个实数x的素数的个数的函数,记为。
历史
在数论中,素数计数函数的增长率引起了很大的兴趣。在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(页面存档备份,存于互联网档案馆)
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.