有多少个质数吗?

内容:

  1. 作品简介:问正确的问题
  2. 素数定理
  3. 历史和π(π)的其他近似x)
  4. 有更好的估计!

(了)”width=1.引言:问正确的问题

2300多年前<一个href="//www.sdsmachining.com/notes/proofs/infinite/">欧几里得证明质数的数量是无限的,所以有两个问题可能会出现在脑海中:

  1. x> 0。比x小的质数有多少?
  2. 有无穷多个质数,但是无穷大有多大呢?

本文档将集中讨论第一个问题。第二个问题在"<一个href="//www.sdsmachining.com/infinity.shtml">无穷大有多大?。”

1.1。π(x)为小于或等于质数的个数x

x是一个正数。"小于多少质数"的问题x?”这个问题被问得如此频繁,以致于它的答案有了一个名字:

π(x) =小于或等于质数的个数x

小于25的素数是2、3、5、7、11、13、17、19和23,因此π(3) = 2, π(10) = 4, π(25) = 9。(在<一个href="#table">下一小节)。请看下图,并注意到π(π)的曲线是多么不规则。x)表示小值x

[π(x), 0<x<100]”src=现在返回并查看π(x)。[π(x), 0<x<1000]”src=

所以即使π(x)是<一个href="//www.sdsmachining.com/notes/gaps.html">“本地”不规则,其值有一定的趋势。(<一个href="//www.sdsmachining.com/gifs/pi1000000.gif">图- 1000000)。

在本文中,我们将学习π(x)、质数定理(量化这种趋势)和几个经典的π近似(x)。

1.2。π()的值表x)

的值x在这个表中(假设为10,000,000,000)π的值为x)可以通过查找并计算所有质数来找到。

在计算机时代之前,许多数学家形成了质数表。分布最广的是d·n·莱默质数表,长度为10,006,721 [<一个href="//www.sdsmachining.com/references/refs.cgi/Lehmer14">Lehmer14]。到目前为止,最令人惊奇的是库利克在1867年完成的一张表格。这个表列出了整数(因此是所有质数)的最小因数,最大值是100,330,200!

19世纪70年代,麦塞尔发明了一种计算π(x,并在1885年(稍有错误)计算出π(10)9)。1959年D. H. Lehmer简化了Meissel的方法,1985年Lagarias, Miller和Odlyzko改进了使用筛分技术[<一个href="//www.sdsmachining.com/references/refs.cgi/LMO85">LMO85]。

1994年Deléglise和Rivat [<一个href="//www.sdsmachining.com/references/refs.cgi/DR96">DR96]再次改进了计算π(10)的方法17)和π(1018)。Deléglise用改进的算法继续这一工作,找到π(10)20.)和其他值(见他的E-mail消息<一个href="//www.sdsmachining.com/notes/md.html">1996年4月18日和<一个href="//www.sdsmachining.com/notes/md6-96.html">1996年6月19日)。看到<一个href="//www.sdsmachining.com/references/refs.cgi/Riesel94">Riesel94关于如何进行这些计算的实用信息。

Xavier Gourdon的分布式计算项目确定π(4*10)22),<一个href="http://numbers.computation.free.fr/Constants/Primes/Pix/pixproject.html">但当他们发现π(10)的计算中至少有一个错误23)。Tomás Oliveira e Silva有<一个href="http://sweet.ua.pt/tos/primes.html">广泛的值表π(x)和π2(x)。2007年,他重新评估了π(10)23)获取表中的值。这个计算是在一台机器上完成的,并在2008年得到了验证。

表1。π的值(x)
n
x
π(x)
裁判
1
10
4
2
One hundred.
25
3.
1000年
168
4
10000年
1229年
5
100000年
9592年
6
1000000年
78498年
7
10000000年
664579年
8
100000000年
5761455年
9
1000000000年
50847534年
10
10000000000年
455052511年
11
100000000000年
4118054813年
12
1000000000000年
37607912018年
13
10000000000000年
346065536839年
14
100000000000000年
3204941750802年
(<一个href="//www.sdsmachining.com/references/refs.cgi/LMO85">LMO85]
15
1000000000000000年
29844570422669年
(<一个href="//www.sdsmachining.com/references/refs.cgi/LMO85">LMO85]
16
10000000000000000年
279238341033925年
(<一个href="//www.sdsmachining.com/references/refs.cgi/LMO85">LMO85]
17
100000000000000000年
2623557157654233年
(<一个href="//www.sdsmachining.com/references/refs.cgi/DR96">DR96]
18
1000000000000000000年
24739954287740860年
(<一个href="//www.sdsmachining.com/references/refs.cgi/DR96">DR96]
19
10000000000000000000年
234057667276344607年
20.
100000000000000000000年
2220819602560918840年
21
1000000000000000000000年
21127269486018731928年
22
10000000000000000000000年
201467286689315906290年
23
100000000000000000000000年
1925320391606803968923年
24
1000000000000000000000000年
18435599767349200867866年
(<一个href="//www.sdsmachining.com/notes/pi(10to24).html">请注意)
25
10000000000000000000000000年
176846309399143769411680年

π(10)的值24)是由J. Buethe, J. frank, A. Jost, T. Kleinjung在假定未经证明的黎曼假设的分析方法发现的。他们的方法“类似于Lagarias和Odlyzko描述的方法,但是使用Weil显式公式而不是复杂的曲线积分”(见他们的<一个href="//www.sdsmachining.com/notes/pi(10to24).html">电子邮件宣布结果2010年7月)。该值后来被D. J. Platt无条件验证[<一个href="//www.sdsmachining.com/references/refs.cgi/Platt2012">Platt2012]。

2013年5月,J. Buethe, J. Franke, A. Jost, T. Kleinjung用基于Weil显式公式的解析方法无条件完成了π(10^25)的计算。


(了)”width=2.素数定理:近似π(x)

尽管素数的分布似乎是随机的(可能有无穷多个孪生素数,而且素数之间存在(肯定)任意大的间隙),但函数π(x)表现得出奇地好:事实上,它已经得到了证明(见<一个href="#hist">下一节):

素数定理:不超过的质数数目x渐近x/ lnx

根据π(x)我们会这样写:

素数定理:π(x) ~x/ lnx

这(大致)意味着x/ lnx是π(x),但在我们考虑这个和其他结果之前,让我们更具体一点:

一个(x)是渐近b(x)”和“一个(x)~ b(x,两者都表示极限(如x趋近于无穷)的比值一个(x) / b (x)是1。

如果你没有学过微积分,这意味着你可以一个(x) /b(x)尽可能接近1,只要你需要它x足够大。警告:一个(x)~b (x)意味着一个(x)- - -b(x)很小!例如,x2是渐近x2-x,但它们之间的区别,x,得到任意大x趋于无穷。

结果一:你可以近似π(x),x/ (lnx- 1)

表2。π(x)节x/ lnx
x π(x) x/ lnx x/ (lnx1)
1000 168 145 169
10000 1229 1086 1218
100000 9592 8686 9512
1000000 78498 72382 78030
10000000 664579 620420 661459
100000000 5761455 5428681 5740304

素数定理显然意味着你可以用x/ (lnx-一个)(任何常量一个)以接近π(x)。素数定理用一个= 0,但<一个href="#better">它已经被证明那一个=1是最好的选择。

还有长一点的桌子<一个href="#table3">下面和(只有π(x))<一个href="#table">以上。

例子:最近有人给我发邮件要了一份名单所有最大为300位的质数。因为素数定理意味着这个列表大约有1.4*10297条目我们知道不可能有这样的列表!

请注意Pierre Dusart [<一个href="//www.sdsmachining.com/references/refs.cgi/Dusart99">Dusart99]表明如果x> 598

(x/ lnx) (1 + 0.992 / lnx)<π(x)<(x/ lnx) (1 + 1.2762 / lnx)
(上限对所有人都成立x> 1)。这给了更大的范围x。请注意x/ lnx <π(x)x> 10。

结果二:nTh '是关于nlnn

让p (n)是n'。证明素数定理与这个表述等价是很容易的

定理:p (n) ~nlnn

(见<一个href="//www.sdsmachining.com/references/refs.cgi/HW79">哈代和赖特,第10页)。更好的估计是

定理:p (n) ~n(lnn+ ln lnn- 1)

(见<一个href="//www.sdsmachining.com/references/refs.cgi/Ribenboim95">Ribenboim95pg 249]。

例子:这些公式预测第100万个质数分别是1380万和1540万。实际上,百万分之一的质数是15,485,863。

在这些方面已经有了很多改进;例如,罗宾[<一个href="//www.sdsmachining.com/references/refs.cgi/Robin83">Robin83]表明如果n>8601[实际上罗宾错误地使用了7021],那么

n(lnn+ ln lnn- 1.0073) < p(n) <n(lnn+ ln lnn- - - - - - 0.9385)

最近,马西亚斯和罗宾[<一个href="//www.sdsmachining.com/references/refs.cgi/MR96">MR96]表明如果n>15985,那么

p (n)< n(lnn+ ln lnn- - - - - - 0.9427)

如果n>13,然后

p (n)< n(lnn+ ln lnn- 1 + 1。8lnlnn/ lnn)

(这对大的更好n)。皮埃尔Dusart [<一个href="//www.sdsmachining.com/references/refs.cgi/Dusart99">Dusart99使这些结果更加有力

p (n) >n(lnn+ ln lnn- 1)

对所有n。Dusart的文章也给出了更接近下一项的更好的界pn。该渐近展开式的第一项由Cipolla [<一个href="//www.sdsmachining.com/references/refs.cgi/Cipolla1902">Cipolla19021902年):

p (n) =n(lnn+ ln lnn- 1 + (ln ln)n) - 2) / lnn-
((ln ln (n))2- 6ln ln (n+ 11)/(2 log2 n+ O(ln lnn/ lnn)3.))

再一次<一个href="//www.sdsmachining.com/references/refs.cgi/Ribenboim95">Ribenboim95和<一个href="//www.sdsmachining.com/references/refs.cgi/Riesel94">Riesel94是查找更多信息的绝佳起点。顺便说一下,如果你对nTh '表示小n(比如说少于1,000,000,000),然后使用<一个href="//www.sdsmachining.com/nthprime/">的nth '页面。”

结果三:随机整数出现的概率x质数是1/lnx

x必须是正整数。自x/ lnxx小于或等于的正整数x是质数,其中一个是质数的概率是1/lnx

例子:假设我想求一个1000位的质数。如果我选择1000位整数x来<一个href="//www.sdsmachining.com/prove/">素性测试 随机,那么我期望测试ln(101000),或者在找到质数之前约有2302个整数。显然,如果我用奇数,我可以把这个估计值乘以1/2,如果我选择不能被3整除的整数,那么我可以乘以2/3,…

另一种说法是质数的密度小于x大约是1 / ln吗x。下面是小值的实际密度图x

质数的密度从0到200”><h2 class=(了)”width=3.素数定理的历史

1798年,勒让德发表了第一个关于π(π)大小的重要猜想。x),当他的书Essai sur la Théie des Nombres他说

勒让德:π(x)大约是x/ (lnx- - - - - - 1.08366)

显然,Legendre猜想等价于素数定理,常数1.08366是基于π(π)的有限表得出的。x)(只到x= 400000)。从长远来看<一个href="#better">一个更好的选择比勒让德的1.08366。

高斯也在研究质数表,并提出了一个不同的估计(可能在1791年首次考虑),在1849年写给恩克的一封信中提出,并于1863年首次发表。

高斯:π(x)约为李(x1/ln的积分的主值uu= 0u=x)。

再次注意高斯猜想等同于素数定理。让我们来比较一下这些估算:

表3。近似π(x)的比较
x π(x) 高斯李 勒让德 x/ (lnx- 1) R (x)
1000 168 178 172 169 168.4
10000 1229 1246 1231 1218 1226.9
100000 9592 9630 9588 9512 9587.4
1000000 78498 78628 78534 78030 78527.4
10000000 664579 664918 665138 661459 664667.4
100000000 5761455 5762209 5769341 5740304 5761551.9
1000000000 50847534 50849235 50917519 50701542 50847455.4
10000000000 455052511 455055614 455743004 454011971 455050683.3

在这个表中Gauss' Li(x)总是大于π(x),所有的小公司都是如此x>2.然而在1914年利特伍德证明了π(x)李津(x)经常无限地假定正负值。1986年,Te Riele显示有超过10个180连续的整数x的π(x李)> (x6.62之间)10370和6.6910370

在1850年,切比雪夫在证明素数定理方面取得了第一个真正的进展,证明了存在正常数一个<1<b这样

一个(x/ lnx) <π(x) <b(x/ lnx)

如果π(x)/(x/ln x)有极限,那么它的值一定是1。西尔维斯特在1982年改进了切比雪夫的方法,并证明了我们可以使用一个= 0.95695,b= 1.04423,如果x足够大。(1962年,事实证明我们可以使用一个= 1x> 10 [<一个href="//www.sdsmachining.com/references/refs.cgi/RS62">RS62]。)

最后,在1896年,哈达玛和德·拉·珀森独立完全证明了素数定理利用黎曼关于π(x)到复函数。de la Vallée Poussin也证明了高斯的Li(x)更接近π(x比x / (ln)x-一个),无论赋给该常数的值是多少一个(而且也是最好的价值一个是1)。比这些更好的近似是黎曼函数[<一个href="//www.sdsmachining.com/references/refs.cgi/Ribenboim91">Ribenboim91,<一个href="//www.sdsmachining.com/references/refs.cgi/Riesel94">Riesel94]。

1949年在塞尔伯格[<一个href="//www.sdsmachining.com/references/refs.cgi/Selberg49">Selberg49和Paul Erdös [<一个href="//www.sdsmachining.com/references/refs.cgi/Erdos49">Erdos49]独立地给出了素数定理的第一个初等证明——这里初等意味着不使用现代复分析——事实上他们的证明是非常困难的!哈代和赖特的文章中有一个更容易阅读(但不那么基本)的证明[<一个href="//www.sdsmachining.com/references/refs.cgi/HW79">HW79教派,-16 - 22.15]。

最后,当Hadamard和de la Vallée Poussin证明<一个href="#pnt">素数定理,他们实际上展示了

π = Li(x) + O(x*e^(-a*√(ln x)))”width=

对于某个正常数一个。误差项取决于已知的黎曼ζ函数在临界带内的无零区域。随着我们对区域大小的了解的增加,误差项减小。1901年,冯·科赫证明了<一个href="//www.sdsmachining.com/notes/rh.html">黎曼假设相当于更严格的估计:

π(x) = Li(x) + O(x^(1/2)ln x)”width=

(了)”width=4.更准确的估计

R(x)与π(x)很接近”class=

这一页关注的是素数定理的最简单形式,但还有更好的估计π(x)。简而言之,黎曼ζ函数提供了一种给出π(x),通过对ζ函数的非平凡零求和(按大小递增的顺序)。

π(x)的精确公式”></div>
    <p>(在素数处,π(<i>x</i>)上升一个单位,这个公式在这一步的中间趋于数值。)上面的第一个(也是主要的)项叫做黎曼函数R(<i>x</i>)。</p>
    <div class= R(x)的定义”></div>
    <p>R()的最后一种形式<i>x</i>)是Graham级数,是计算这个函数的好方法。右边的图表显示了一个近似R(<i>x</i>)为,至少对于较小的值<i>x</i>。更适合最小的小公司<i>x</i>值如下所示(对于大的值,它们本质上是相同的<i>x</i>)。</p>
    <div class= R(x)的\π(x)近似值”></div>
    <p>要了解这些近似是多么接近,请看<一个href=令人印象深刻的偏差表由安德烈Kulsha。

马修·沃特金斯也有<一个href="http://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/encoding1.htm">美丽的发展这些信息和一些优秀的动画。

警告

表示R(x)、Li(x)和x/ln(x)近似π(x)的图”><br></strong>
     <p class=图4。表示R(x)、Li(x)和x/ln(x)近似π(x)的图

看看上面的图表很容易,上面显示了李(x)(蓝色)、R (x)(黑),π(x)(红色)和x/ lnx(绿色);然后宣布"R(x)是π的最佳估计。x)。”确实是在这个范围内,但是正如我们上面提到的,Li(x) -π(x)经常无限地改变符号,在其附近,Li(x)将是最划算的。<一个href="//www.sdsmachining.com/references/refs.cgi/Ingham1990">a . e .英是这样说的:

以前,黎曼提出的一个近似π(x)的函数被认为是非常重要的。对于π(x)的所有值,这个函数都以惊人的精度表示π(x),但我们现在看到,它比Li(x)的优越性是虚幻的……对于x的特殊值(我们想多大就多大),一个近似值和另一个近似值与真实值的偏差一样大。

…我们同样可以看到函数Li(x)-(1/2)Li(x1/2)在“平均上”比Li(x)更接近π(x);但即使重复平均,黎曼公式中的后一项也不重要。

问题是,在这些展开式中,非平凡零的贡献有时会淹没除主要项以外的任何项。

打印自PrimePages ©Chris Caldwell。