素数定理能够帮助我们快速估算给定自然数范围内的素数的个数的。
素数定理可以给出第n个素数p(n)的渐近估计: 它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个,它是素数的概率大约是1/ln n。
这意味着在自然数n范围内素数的个数:π(n)~n/ln n 。
举个例子,以n=1000为例,π(1000)~1000/ln1000≈1000≈145。
实际1000以内的素数个数有168个。这里的误差不小。当然,用素数定理估算的准确性是在数值越大时越准确,并且还容易计算。
但不管怎样,其实我们还是可以考虑另外一种估算素数个数的方法。
在1000以内的自然数表中,按照埃拉托色尼筛法,我们只需考虑31以内的素数,也即只要考虑筛数:2,3,5,7,11,13,17,19,23,29,31。
我们首先用全体自然数(注意:有无穷多)来考虑不能被上述11个“筛数”所整除的所有自然数,我们不妨把这类自然数称为M(11)数,它所对应在全体自然数中的比例不妨称为λ[M(11)]。
然后我们来尝试求λ[M(11)]。
我们设想如下的在全体自然数中的类“埃拉托色尼”(注意:不是“埃拉托色尼”筛法,两者略有不同)筛除进程:
我们先用2来筛除,筛除所有偶数(包括2),等于筛去1/2。
然后再用3来筛除,然后筛除所有奇数中的3倍数(包括3),于是再筛去上一步骤剩余的1/3,等于在全体自然数中保留了(1-1/2)(1-1/3)=1/3。
这样我们剩余的数的形式为:6k-1与6k+1两种形式。然后再筛除这两种形式中的5倍数(包括5),等于在全体自然数中剩下了(1-1/2)(1-1/3)(1-1/5)=4/15。
这样我们由上一步骤剩余的数的形式是如下8种:30k-29,30k-23,30k-19,30k-17,30k-13,30k-11,30k-7,30k-1。在这8种中又分别筛除7倍数(包括7),我们将在全体自然数中剩下(1-1/2)(1-1/3)(1-1/5)(1-1/7)=8/35
类似地,一直延续上述进程,最后我们会得到:
λ[M(11)]=(1-1/2)(1-1/3)(1-1/5)(1-1/7)(1-1/11)(1-1/13)(1-1/17)(1-1/19)(1-1/23)(1-1/29)(1-1/31)
=30656102400/200560490130
≈0.153
1000以内的M(11)数除了1以外(1也是M(11)数)都是素数,其实际比例将会略多于λ[M(11)],我们不妨用λ[M(11)]作为近似值,于是可得1000以内的M(11)数的个数为:1000×M(11)=153,其中有152个是素数。
考虑到2,3,5,7,11,13,17,19,23,29,31等11个数是不计入M(11)数的,因此我们进一步可知1000以内的素数至少有:152+11=163个。这与实际检验1000以内素数表中的素数个数168已是相当接近了。
由此可见这个算法的精确度比目前通行的素数定理的估算法相比会更快地近似于实际。当然这个算法相比素数定理也有很大的弊端,就是计算量庞大,不像素数定理计算量少而简洁。但这个工作若是交给计算机,似乎这弊端就不算太大了;而且如果不只考虑计算,而是看到其可用于证明,那么它自有其独立于素数定理的巨大价值。
以上是举例来说明,如果要抽象表述,上述算法可以归纳如下:
用p(n)表示第n个素数,将全体自然数中不能被不大于p(n)的素数整除的所有自然数称为M(n)数,并记M(n)数在全体自然数中的比例为λ[M(n)],那么必有:
λ[M(n)]=∏(1-1/p(i)) (这里i为从1至n)
显然,当大于1的自然数m∈M(n),并且m足够小时,比如 m<p(n+1)²时,m是素数。
因此假设自然数N满足p(n)²<N<p(n+1)²时,我们便可结合估算N在自然数N范围内M(n)数的个数从而进一步计算N范围内的的素数个数X至少为:
X>n-1+N·λ[M(n)]=n-1+N·∏(1-1/p(i)) (这里i为从1至n)
这个估算公式是有别于利用素数定理的估算的。
前述证明是否完全正确呢?检验它的正确性的方法可以有另外一条:判断它是否违反素数定理。在我看来这两者是相容的,不过目前这也只是我个人的猜想与判断。愿有识者可以进一步对此进行证明或否证。
我在昨天发布的文章《一条孪生素数分布规律:相邻素数平方数区间总有2对以上孪生素数》中也使用了类似算法(改造为相对孪生素数的公式的复杂度会略高一些)来估算孪生素数的对数。
为了进一步阐释澄清这个思路,回答“從爻之民”先生对前文论证提出的质疑,特写此文。正如“從爻之民”先生所指出,如果这个方法是成立的话,不仅能用于证明孪生素数猜想,也能用于对哥德巴赫猜想(1+1)的证明。