[原创]素数分布数量的概率计算与素数定理的计算的相对误差的比较

愚工688

[这个贴子最后由愚工688在 2008/10/08 11:42pm 第 2 次编辑]

[watermark] 素数分布数量的概率计算与素数定理的计算的相对误差的比较

在素数的分布问题上，高斯思索过这个问题，并预想过素数定理，即
       当自然数x趋向无穷大时    π(x) = x / ln x
对自然数x而言，π(x)是表示p≤x 的素数个数。
这是数学家们已经证明的。
然而，对我们业余爱好者来说，无穷大时的规律性是不易理解的，我们也需要知道在自然数x 不太大时，π(x)表示的素数个数有何种更直观的规律可循？
以下我依据教科书上已有的概率知识，来谈谈π(x)表示的素数个数的一种规律。

教科书关于概率事件独立事件的乘法原理
事件的独立性的定义：
设有事件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中打不出，只好这样处理了]

在素数的分布问题上，独立事件的乘法法则的运用
对于自然数列 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,...里的任意数x，除以2,3,5,...，r这些有限的素数中的任意二个素数j，k时的余数ji、ki的同时发生的概率，显然具有相互独立的特性，即被x除时：
余数同时满足等于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排也相互独立”的性质，在自然数列里的数在除以任意二个素数j，k时，余数同时不满足等于ji、ki [ji=0,1, …，j-1；ki=0,1, …，k-1] 的概率 ，有：  P(j*k)=P(j)*P(k)=(1-1/j)(1-1/k)
由上面的概念推广可知，这个概念同样可推广到2,3,5,...，r这有限多个素数上去，当x分别除以这些素数时的余数同时满足不等于2i、3i、5i、...、ri的概率，有
P(x)=P(2*3*…*n*…*r)
= P(2)*P(3)*…*P(n)*…*P(r)
=(1/2)*[(3-1)/3]*[(5-1)/5]*…*[(r-1)/r]；   
我们常用“爱拉脱斯”筛法来判断素数：
x不能被≤√x的所有素数整除时就是素数。
若把除数限定为≤√x的2,3,5,...，r这些有限多的素数时，这实际上是上面的概念推广的一个特例：x除以≤√x的2,3,5,...，r这些素数时的余数同时满足2i≠0、3i≠0、5i≠0、...、ri≠0  时的特殊情况。
在自然数区间[2,x]内素数的分布概率分析：
在自然数中，不能被2整除的数的概率是1/2；
不能被3整除的数的概率是（1－1/3）；
不能被5整除的数的概率是（1－1/5）；
不能被7整除的数的概率是（1－1/7）；
……
不能被素数r整除的数的概率是（1－1/r）；
由概率的乘法原理推广可知：
在[2,x]内的全部x-1个整数中，素数数量的概率计算式为：
Sp(x)=(x-r)*P(k)+k；
    =(x-r)*(1/2)*(2/3)*(4/5)*…*［r-1］/r]+k ;
式中：k表示小于等于根号x 的素数2—r 的数量。
其与该区间里的实际上的素数数量π(x)之间的相对误差为：E=[Sp(x)-π(x)]/π(x)。

下面是1000万内的素数数量的分区概率计算与素数定理计算值的对比
[素数定理的数量x / ln x用Gs(x)表示，其相对误差用E2 表示。]
区间[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大到千万级的范围）的情况下，素数数量的概率计算式比素数定理表述的误差要小得多；
从误差的变化趋势上，我并不怀疑当自然数x趋向无穷大时，π(x) = x / ln x的误差会会越来越小，因为数学家已经证明了。但至少在比较容易计算的自然数范围里(假定1亿以下吧)，概率计算的相对误差E的绝对值 要比素数定理计算的相对误差E2的绝对值要小得多，这是不争的事实。
由此在自然数x的不太大的情况下，素数数量的概率计算式比素数定理能更确切地体现一个有限区间[2,x]里的素数分布数量的规律。

[/watermark]

愚工688

[这个贴子最后由愚工688在 2008/10/02 09:06pm 第 1 次编辑]

正文所运用的分区进行概率计算与高斯定理计算的Basic 程序。供参考。
语句69的分母决定分区的大小。
1 ';The program can list all prine numbers & compute the number in [2,B]."
3  OPEN "gaosifen.rtf" FOR OUTPUT AS #3
4 PRINT " if B<2 then end."
5 INPUT "2,B=";  b
6 IF b < 2 THEN END
10 s1 = 0: s2 = 0: r1 = 0: q = 1: n1 = 0
20 FOR j = 2 TO b
22 P = 1: n = 0
30 READ r
35 IF r > (j + .001) ^ (1 / 2) THEN 60
38 P = P * ((r - 1) / r)
39 IF P < q THEN q = P
40 IF r > r1 THEN r1 = r
45 n = n + 1
46 IF n > n1 THEN n1 = n
48 IF INT(j / r) = j / r AND j / r > 1 THEN 68
50 GOTO 30
60 PRINT j;
62 IF j <= b ^ (1 / 2) THEN s2 = s2 + 1 ELSE s1 = s1 + 1
68 RESTORE
69 IF INT(j / 1000) = j / 1000 THEN GOSUB 150
70 NEXT j
72 s = s1 + s2
75 Sp = (b - r1) * q + s2
76 E = (Sp - s) / s
77 E = INT(100 * E + .5) / 100
78 q = INT(100 * q + .5) / 100
79 Sp = INT(100 * Sp + .5) / 100
80 PRINT TAB(0); "in ["; a; ","; b; "]:"; TAB(22); "S="; s; TAB(31); "r="; r1;
81 PRINT TAB(38); "s2="; s2; TAB(46); "p="; q; TAB(55); "Sp="; Sp; TAB(69); "E="; E
88 GOTO 4
150 t1 = LOG(j)
152 Sp = (j - r1) * q + n1
155 s0 = s1 + s2
160 t = j / t1
165 e2 = t / s0
166 e2 = INT((e2 - 1) * 1000 + .5) / 1000
168 t = INT(100 * t + .5) / 100
176 E = (Sp - s0) / s0
177 E0 = INT(1000 * E + .5) / 1000
178 q0 = INT(1000 * q + .5) / 1000
179 Sp0 = INT(100 * Sp + .5) / 100
185 PRINT &#35;3, TAB(0); "in [2,"; j; "]:"; TAB(20); "S="; s0; TAB(31); "Sp(x)="; Sp0; TAB(45); "E="; E0; TAB(57); "Gs(x)="; t; TAB(72); "E2="; e2
190 RETURN
DATA 2, 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
DATA 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293
DATA 307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499
DATA 503,509,521,523,541,547,557,563,569,571,577,587,593,599, 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691
DATA 701,709,719,727,733,739,743,751,757,761,769,773,787,797, 809,811,821,823,827,829,839,853,857,859,863,877,881,883,887
DATA 907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009, 1013 , 1019 , 1021 , 1031 , 1033 , 1039 , 1049 , 1051 , 1061 , 1063 , 1069 , 1087 , 1091 , DATA 1093 , 1097 , 1103 , 1109 , 1117 , 1123 , 1129 , 1151 , 1153 , 1163 , 1171 , 1181 , 1187 , 1193 , 1201 , 1213 , 1217 , 1223 , 1229 , 1231 , 1237 , 1249 , 1259 , 1277 , 1279 , 1283 , 1289 , 1291 , 1297，
DATA 1301 , 1303 , 1307 , 1319 , 1321 , 1327 , 1361 , 1367 , 1373 , 1381 , 1399 , 1409 , 1423 , 1427 , 1429 , 1433 , 1439 , 1447 , 1451 , 1453 , 1459 , 1471 , 1481 , 1483 , 1487 , 1489 , 1493 , 1499
  DATA 1511 , 1523 , 1531 , 1543 , 1549 , 1553 , 1559 , 1567 , 1571 , 1579 , 1583 , 1597 , 1601 , 1607 , 1609 , 1613 , 1619 , 1621 , 1627 , 1637 , 1657 , 1663 , 1667 , 1669 , 1693 , 1697 , 1699
  DATA 1709 , 1721 , 1723 , 1733 , 1741 , 1747 , 1753 , 1759 , 1777 , 1783 , 1787 , 1789 , 1801 , 1811 , 1823 , 1831 , 1847 , 1861 , 1867 , 1871 , 1873 , 1877 , 1879 , 1889 , 1901 , 1907 , 1913 , 1931 , 1933 , 1949 , 1951 , 1973 , 1979 , 1987 , 1993 , 1997 , 1999
  DATA 2003 , 2011 , 2017 , 2027 , 2029 , 2039 , 2053 , 2063 , 2069 , 2081 , 2083 , 2087 , 2089 , 2099 , 2111 , 2113 , 2129 , 2131 , 2137 , 2141 , 2143 , 2153 , 2161 , 2179 , 2203 , 2207 , 2213 , 2221 , 2237 , 2239 , 2243 , 2251 , 2267 , 2269 , 2273 , 2281 , 2287 , 2293 , 2297
  DATA 2309 , 2311 , 2333 , 2339 , 2341 , 2347 , 2351 , 2357 , 2371 , 2377 , 2381 , 2383 , 2389 , 2393 , 2399 , 2411 , 2417 , 2423 , 2437 , 2441 , 2447 , 2459 , 2467 , 2473 , 2477
  DATA 2503 , 2521 , 2531 , 2539 , 2543 , 2549 , 2551 , 2557 , 2579 , 2591 , 2593 , 2609 , 2617 , 2621 , 2633 , 2647 , 2657 , 2659 , 2663 , 2671 , 2677 , 2683 , 2687 , 2689 , 2693 , 2699 , 2707 , 2711 , 2713 , 2719 , 2729 , 2731 , 2741 , 2749 , 2753 , 2767 , 2777 , 2789 , 2791 , 2797 , 2801 , 2803 , 2819 , 2833 , 2837 , 2843 , 2851 , 2857 , 2861 , 2879 , 2887 , 2897 , 2903 , 2909 , 2917 , 2927 , 2939 , 2953 , 2957 , 2963 , 2969 , 2971 , 2999
  DATA 3001 , 3011 , 3019 , 3023 , 3037 , 3041 , 3049 , 3061 , 3067 , 3079 , 3083 , 3089 , 3109 , 3119 , 3121 , 3137 , 3163 , 3167 , 3169 , 3181 , 3187 , 3191 , 3203 , 3209 , 3217 , 3221 , 3229 , 3251 , 3253 , 3257 , 3259 , 3271 , 3299 , 3301 , 3307 , 3313 , 3319 , 3323 , 3329 , 3331 , 3343 , 3347 , 3359 , 3361 , 3371 , 3373 , 3389 , 3391 , 3407 , 3413 , 3433 , 3449 , 3457 , 3461 , 3463 , 3467 , 3469 , 3491 , 3499
  DATA 3511 , 3517 , 3527 , 3529 , 3533 , 3539 , 3541 , 3547 , 3557 , 3559 , 3571 , 3581 , 3583 , 3593 , 3607 , 3613 , 3617 , 3623 , 3631 , 3637 , 3643 , 3659 , 3671 , 3673 , 3677 , 3691 , 3697 , 3701 , 3709 , 3719 , 3727 , 3733 , 3739 , 3761 , 3767 , 3769 , 3779 , 3793 , 3797 , 3803 , 3821 , 3823 , 3833 , 3847 , 3851 , 3853 , 3863 , 3877 , 3881 , 3889 , 3907 , 3911 , 3917 , 3919 , 3923 , 3929 , 3931 , 3943 , 3947 , 3967 , 3989
  DATA 4001 , 4003 , 4007 , 4013 , 4019 , 4021 , 4027 , 4049 , 4051 , 4057 , 4073 , 4079 , 4091 , 4093 , 4099 , 4111 , 4127 , 4129 , 4133 , 4139 , 4153 , 4157 , 4159 , 4177 , 4201 , 4211 , 4217 , 4219 , 4229 , 4231 , 4241 , 4243 , 4253 , 4259 , 4261 , 4271 , 4273 , 4283 , 4289 , 4297 , 4327 , 4337 , 4339 , 4349 , 4357 , 4363 , 4373 , 4391 , 4397 , 4409 , 4421 , 4423 , 4441 , 4447 , 4451 , 4457 , 4463 , 4481 , 4483 , 4493
  DATA 4507 , 4513 , 4517 , 4519 , 4523 , 4547 , 4549 , 4561 , 4567 , 4583 , 4591 , 4597 , 4603 , 4621 , 4637 , 4639 , 4643 , 4649 , 4651 , 4657 , 4663 , 4673 , 4679 , 4691 , 4703 , 4721 , 4723 , 4729 , 4733 , 4751 , 4759 , 4783 , 4787 , 4789 , 4793 , 4799 , 4801 , 4813 , 4817 , 4831 , 4861 , 4871 , 4877 , 4889 , 4903 , 4909 , 4919 , 4931 , 4933 , 4937 , 4943 , 4951 , 4957 , 4967 , 4969 , 4973 , 4987 , 4993 , 4999
  

刘合亮

》》》P(x)=P(2*3*…*n*…*r);
= P(2)*P(3)*…*P(n)*…*P(r)
=(1/2)*[(3-1)/3]*[(5-1)/5]*…*[(r-1)/r]；
这是特殊情况。  

愚工688

下面引用由刘合亮在 2008/10/04 09:17am 发表的内容：
》》》P(x)=P(2*3*…*n*…*r);
= P(2)*P(3)*…*P(n)*…*P(r)
=(1/2)***…*；
这是特殊情况。

这个特殊的情况就是我们常用来判断素数的“爱拉脱斯”筛法：
‘x不能被≤√x的所有素数整除时就是素数’的素数发生概率。

刘合亮

下面引用由愚工688在 2008/10/04 09:48am 发表的内容：
这个特殊的情况就是我们常用来判断素数的“爱拉脱斯”筛法：
‘x不能被≤√x的所有素数整除时就是素数’的素数发生概率。

“爱拉脱斯”筛法与
P(x)=P(2*3*…*n*…*r);
= P(2)*P(3)*…*P(n)*…*P(r)
=(1/2)***…*；
真的一样吗？

愚工688

[这个贴子最后由愚工688在 2008/10/04 03:27pm 第 1 次编辑]

下面引用由刘合亮在 2008/10/04 10:02am 发表的内容：
“爱拉脱斯”筛法与
P(x)=P(2*3*…*n*…*r);
= P(2)*P(3)*…*P(n)*…*P(r)
=(1/2)***…*；
...

爱拉脱斯筛法(简称：爱氏筛法，Eratoshenes--古希腊数学家 )
“爱拉脱斯”筛法：x不能被≤√x的所有素数整除时就是素数；
P(x)=P(2*3*…*n*…*r);
= P(2)*P(3)*…*P(n)*…*P(r)
是在区间[2，x]中的数不能被≤√x的所有素数整除时的素数发生概率（我的观点）。我采用“爱拉脱斯”筛法来判断素数是因为他所需要的筛除元素最少。
两者是两回事。

刘合亮

》》我采用“爱拉脱斯”筛法来判断素数是因为他所需要的筛除元素最少。


那么用你的推导分析式计算一下，结果是否与理论相符呢？

愚工688

下面引用由刘合亮在 2008/10/06 00:16pm 发表的内容：
》》我采用“爱拉脱斯”筛法来判断素数是因为他所需要的筛除元素最少。
那么用你的推导分析式计算一下，结果是否与理论相符呢？

推导分析式计算的结果与实际比较。哪有与理论比的？
随便哪个理论的结果正确与否都应该与实际进行验证。

Donqy

我看到：从１至９之间有４个质数，
　　　　从９至２５之间有５个，
　　　　２５至４９之间有６个，．．．．．
所以质数的分布概率应为｛（３＋n）＋［３＋（n－１）］+.....+４｝／（２n＋１）^2[br][br]-=-=-=-=- 以下内容由 Donqy 在 时添加 -=-=-=-=-
当n等于１时，｛（３＋n）＋［３＋（n－１）］+.....+４｝＝４[br][br]-=-=-=-=- 以下内容由 Donqy 在 时添加 -=-=-=-=-
当n等于2时，｛（３＋n）＋［３＋（n－１）］+.....+４｝＝9[br][br]-=-=-=-=- 以下内容由 Donqy 在 时添加 -=-=-=-=-
当n等于3时，｛（３＋n）＋［３＋（n－１）］+.....+４｝＝15
.............

刘合亮

in [2, 100000 ]:   π(x)= 9592    Sp(x)= 9716.84 p?
概率计算数值  Sp= 9686.73  个&G [
这些数据都是引用你的。怎么会不一样？ 另，你怎么来认识误差的产生？R`N):
》》推导分析式计算的结果与实际比较。哪有与理论比的？

推导分析式计算的结果与实际比较。然后再与你的理论比。