素数计数函数

小於或等於某數的質數個數

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

π(n)的最初60个值

历史

编辑

数论中,素数计数函数的增长率引起了很大的兴趣。在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时,  。因此:

 

 的计算可以用这种方法来获得:

 

另一方面, 的计算可以用以下规则来完成:

  1.  
  2.  

利用这种方法,勒梅尔计算了 

其它素数计数函数

编辑

我们也使用其它的素数计数函数,因为它们更方便。其中一个是黎曼的素数计数函数,通常记为 。这个函数在自变量为素数的幂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. 
  • 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.