|
素数分布数量的规律与概率计算
素数的定义是:不能被除了自身与1以外的自然数整除的自然数。
由爱拉托斯筛法可知素数的另一简便的判断方法为:x不能被小于或等于√x的全部素数整除即为素数;这是大多数人所知道的。
那么在一个自然数区间[2,x]内素数的数量能否进行计算呢?其分布有没有规律呢?分析如下:
把≤√x的所有素数记为2,3,5,...,r(r为最大);依据爱拉托斯筛法,用这些素数就可以满足判断出自然数区间[2,x]内全部素数。
在自然数区间[2,x]内素数的分布概率分析:
在自然数中,不能被2整除的数的分布概率是1/2;
不能被3整除的数的分布概率是(1-1/3);
不能被5整除的数的分布概率是(1-1/5);
不能被7整除的数的分布概率是(1-1/7);
……
不能被素数r整除的数的分布概率是(1-1/r);
那么同时满足上面的这些条件的数的分布概率怎么样呢?
教科书关于概率事件独立事件的乘法原理——
事件的独立性的定义:
设有事件A与B,如果
P(A*B)=P(A)*P(B)
那么我们就称事件A与B为互相独立。……
由事件独立性的定义,容易推得:不可能事件或必然事件与任何事件都相互独立;并且如果事件A与B互相独立,那么A 与B排相互独立,A 排与B相互独立,及A排 与B排也相互独立。(A排表示A上加一横,即事件A的对立事件,余同)……(211页)
上面仅讨论了两个事件的独立性,但是这个概念可推广到任意有限多个事件上去。
对于事件A1,A2,...,An,我们说它们是互相独立的,如果对于任何r(1≤r≤n)及
1≤i1<i2<...<ir≤n(其中r,i1,i2,...,ir都是整数)有
P(Ai1*Ai2*...*Air)=P(Ai1)P(Ai2)...P(Air)。
显然,如果A1,A2,...,An相互独立,那么
P(A1*A2*...*An)=P(A1)P(A2)...P(An)。(212页)
——以上摘自《高等数学》(化、生、地类专业)第一册。书号:13012.096,人民教育出版社出版。上海师范大学数学系,中山大学数学力学系,上海师范学院数学系 合编
[另注:在原文中“A1,A2,...,An”的1,2,n 均为下标;“P(Ai1*Ai2*...*Air)”中的r(1≤r≤n),均为下标i的下标,Word中打不出,只好这样处理了]
在区间[2,x]内素数的分布概率分析:
独立事件的乘法法则的运用
对于自然数列 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,...里的任意数t,除以2,3,5,...,r这些有限的素数中的任意二个素数j,k时的余数ji、ki的同时发生的概率,显然具有相互独立的特性,即被t除时:
余数同时满足等于ji、ki的概率,有
P(j*k)=P(j)*P(k)=(1/j)(1/k)
(2≤j,k≤r;j≠k;ji=0,1,2,...,j-1;ki=0,1,2,...,k-1)
由事件独立性的定义推得的“A排与B排也相互独立”的性质,由上面的概念推广可知,这个概念同样可推广到2,3,5,...,r这有限多个素数上去,在区间[2,x]内的数t分别除以这些素数时的余数同时满足不等于零的概率,有
P(t)=P(2*3*…*n*…*r)
= P(2)*P(3)*…*P(n)*…*P(r)
=(1/2)*[(3-1)/3]*[(5-1)/5]*…*[(r-1)/r];
由概率的乘法原理推广可知:
在[2,x]内的全部x-1个整数中,素数数量的概率计算式为:
Sp(x)=(x-r)*P(t)+k;
=(x-r)*(1/2)*(2/3)*(4/5)*…*[r-1]/r]+k ;
式中:k表示小于等于根号x 的素数的数量。
这里采用了区间(x-r)值作为计算区间,是因为[2,r]里面的k个素数已经分类计算了。
这样的概率计算数值的准确程度怎么样呢?与已有的数学家的观点作比较:
用什么样的规律来表达自然数中的素数呢?数学家高斯思索过这个问题,并预想过素数定理,即
当自然数x趋向无穷大时,有Lim[π(x) /(x/ln x)]= 1
对自然数x而言,π(x)是表示p≤x 的素数个数。
下面是1000万内的素数数量的分区概率计算与素数定理计算值的对比
素数数量的概率计算值与该区间里的实际上的素数数量π(x)之间的相对误差为:E=[Sp(x)-π(x)]/π(x)。
[素数定理的计算数量x / ln x用Gs(x)表示,其相对误差用E2 表示。]
π(X)——[2,x]内素数的实际个数。
Sp(x)—概率计算的值;
E—概率计算Sp(x)的相对误差。
Gs(x)—高斯定理的计算值;
E2-- Gs(x)的相对误差。
in [2, 1000 ]: π(X)= 168 Sp(x)= 159.11 E=-.053 Gs(x)= 144.76 E2=-.138
in [2, 2000 ]: π(X)= 303 Sp(x)= 291.34 E=-.038 Gs(x)= 263.13 E2=-.132
in [2, 3000 ]: π(X)= 430 Sp(x)= 417.05 E=-.03 Gs(x)= 374.7 E2=-.129
in [2, 4000 ]: π(X)= 550 Sp(x)= 536.32 E=-.025 Gs(x)= 482.27 E2=-.123
in [2, 5000 ]: π(X)= 669 Sp(x)= 658.43 E=-.016 Gs(x)= 587.05 E2=-.122
in [2, 6000 ]: π(X)= 783 Sp(x)= 768.08 E=-.019 Gs(x)= 689.69 E2=-.119
in [2, 7000 ]: π(X)= 900 Sp(x)= 873.46 E=-.029 Gs(x)= 790.63 E2=-.122
in [2, 8000 ]: π(X)= 1007 Sp(x)= 985.74 E=-.021 Gs(x)= 890.16 E2=-.116
in [2, 9000 ]: π(X)= 1117 Sp(x)= 1107.32 E=-.009 Gs(x)= 988.47 E2=-.115
in [2, 10000 ]: π(X)= 1229 Sp(x)= 1216.5 E=-.01 Gs(x)= 1085.74 E2=-.117
in [2, 20000 ]: π(X)= 2262 Sp(x)= 2245.83 E=-.007 Gs(x)= 2019.49 E2=-.107
in [2, 30000 ]: π(X)= 3245 Sp(x)= 3238.72 E=-.002 Gs(x)= 2910.09 E2=-.103
in [2, 40000 ]: π(X)= 4203 Sp(x)= 4181.11 E=-.005 Gs(x)= 3774.78 E2=-.102
in [2, 50000 ]: π(X)= 5133 Sp(x)= 5171.97 E= .008 Gs(x)= 4621.17 E2=-.1
in [2, 60000 ]: π(X)= 6057 Sp(x)= 6074 E= .003 Gs(x)= 5453.5 E2=-.1
in [2, 70000 ]: π(X)= 6935 Sp(x)= 7000.6 E= .009 Gs(x)= 6274.51 E2=-.095
in [2, 80000 ]: π(X)= 7837 Sp(x)= 7883.55 E= .006 Gs(x)= 7086.05 E2=-.096
in [2, 90000 ]: π(X)= 8713 Sp(x)= 8804.71 E= .011 Gs(x)= 7889.5 E2=-.095
in [2, 100000 ]: π(X)= 9592 Sp(x)= 9686.73 E= .01 Gs(x)= 8685.89 E2=-.094
in [2, 200000 ]: π(X)= 17984 Sp(x)= 18312.86 E= .018 Gs(x)= 16385.29 E2=-.089
in [2, 300000 ]: π(X)= 25997 Sp(x)= 26628.83 E= .024 Gs(x)= 23787.74 E2=-.085
in [2, 400000 ]: π(X)= 33860 Sp(x)= 34667.03 E= .024 Gs(x)= 31009.63 E2=-.084
in [2, 500000 ]: π(X)= 41538 Sp(x)= 42615.18 E= .026 Gs(x)= 38102.89 E2=-.083
in [2, 600000 ]: π(X)= 49098 Sp(x)= 50380.15 E= .026 Gs(x)= 45096.9 E2=-.081
in [2, 700000 ]: π(X)= 56543 Sp(x)= 58193.57 E= .029 Gs(x)= 52010.44 E2=-.08
in [2, 800000 ]: π(X)= 63951 Sp(x)= 65814.13 E= .029 Gs(x)= 58856.56 E2=-.08
in [2, 900000 ]: π(X)= 71274 Sp(x)= 73476.84 E= .031 Gs(x)= 65644.8 E2=-.079
in [2, 1000000 ]: π(X)= 78498 Sp(x)= 81052.53 E= .033 Gs(x)= 72382.41 E2=-.078
in [2, 2000000 ]: π(X)= 148933 Sp(x)= 154670.5 E= .039 Gs(x)= 137848.7 E2=-.074
in [2, 3000000 ]: π(X)= 216816 Sp(x)= 225223 E= .039 Gs(x)= 201151.6 E2=-.072
in [2, 4000000 ]: π(X)= 283146 Sp(x)= 294842 E= .041 Gs(x)= 263126.7 E2=-.071
in [2, 5000000 ]: π(X)= 348513 Sp(x)= 363658.8 E= .043 Gs(x)= 324150.2 E2=-.07
in [2, 6000000 ]: π(X)= 412849 Sp(x)= 430445.9 E= .043 Gs(x)= 384436.2 E2=-.069
in [2, 7000000 ]: π(X)= 476648 Sp(x)= 498431.1 E= .046 Gs(x)= 444122.4 E2=-.068
in [2, 8000000 ]: π(X)= 539777 Sp(x)= 563802.4 E= .045 Gs(x)= 503304.4 E2=-.068
in [2, 9000000 ]: π(X)= 602489 Sp(x)= 629911.8 E= .046 Gs(x)= 562052.6 E2=-.067
in [2, 10000000]: π(X)= 664579 Sp(x)= 696241.3 E= .048 Gs(x)= 620420.7 E2=-.066
数据显示,在自然数x的不太大(受电脑与所用程序的运算能力限制,我只能计算到自然数x略大于1000万的范围)的情况下,素数数量的概率计算式比素数定理表述的误差要小得多;
从误差的变化趋势上,我并不怀疑当自然数x趋向无穷大时,π(x) = x / ln x的误差会会越来越小,因为数学家已经证明了。但至少在比较容易计算的自然数范围里(1千万以下),概率计算的相对误差E的绝对值 要比素数定理计算的相对误差E2的绝对值要小得多,这是不争的事实。
因此可以得到结论:在自然数x的不太大的情况下,区间[2,x]内素数的分布规律与依据概率的乘法法则的计算结果比较接近。
|
|