|
同余筛法(5)
哥德巴赫素数同余筛法
我们用同余筛法去筛哥德巴赫素数时取h=2.
a11,a12,a13,...,a1n=0
a21=a11=0
a22,a23,...,a2n根据偶数2k与pn的同余
命D(x)为不大于x的哥德巴赫素数对数
我们有
6=3+0
8=3+2
10=3+1
12=3+0
14=3+2
16=3+1
18=3+0
20=3+2
22=3+1
24=3+0
26=3+2,5+1
50=3+2,5+0,7+1
122=3+2,5+2,7+3,11+1
170=3+2,5+0,7+2,11+5,13+1
当n=1时m1=2
筛去2
剩下数1
所以φ2(m1)= 1
当n=2时m2=6
筛去2,3,4,6
剩下数1,5
取偶数6
6=3+0
第二次不用筛
剩下数1,5
所以φ2(m2)=φ(m2)=2
因为1不是素数,所以它们都不是
3+3=3+0
所以D(6)=1
当n=3时m3=30
筛去2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30
剩下数1,7,11,13,17,19,23,29
取偶数16
16=3+1,5+1
第二次筛去1,7,11,13,19,
剩下数17,23,29
所以φ2(m3)=3
因为17,23,29都大于16
3+13=3+1
5+11=5+1
所以D(16)=2
取偶数28
28=3+1,5+3
第二次筛去1,7,13,19,23
剩下数11,17,29
所以φ2(m3)=3
因为29大于28
5+23=5+3
11+17=3+1,5+3
所以D(28)=2
这样可以一直做下去.
命D(x)为不大于x的哥德巴赫素数对数
根据已有的资料
我们有
D(12)=1
D(68)=2
D(128)=3
D(332)=6
D(992)=13
D(2672)=28
D(2936)=31
D(9602)=77
D(2^21)=7471
D(2^22)=13705
D(2^26)=153850
命φ2(mn)=(mn)^t
D(mn)=(mn)^s
我们有
D(12)=12^0=1
D(68)=68^0.164272050=2
D(128)=128^0.226423214=3
D(332)=332^0.308650785=6
D(992)=992^0.371746708=13
D(2672)=2672^0.422301458=28
D(2936)=2936^0.430065342=31
D(9602)=9602^0.473711547=77
D(2^21)=(2^21)^0.612718364=7471
D(2^22)=(2^22)^0.624655214=13705
D(2^26)=(2^26)^0.662737112=153850
D(123456789000)=123456789000^0.681485985
由于偶数2n中与pn的同余不一定有一个非0的同余
为解决此问题我们提出一个纯偶数问题
纯偶数就是形如2^k的数,因为这样的偶数都不能被2以外的素数整除
我们有
D(2^2)=4^0=1
D(2^3)=8^0=1
D(2^4)=16^0.25=2
D(2^5)=32^0.2=2
D(2^6)=64^0.386988015=5
D(2^7)=128^0.226423214=3
D(2^8)=256^0.375=8
D(2^9)=512^0.384381291=11
D(2^10)=1024^0.439231742=21
D(2^11)=2048^0.416814772=24
D(2^12)=4096^0.475036643=52
D(2^13)=8192^0.482060503=77
D(2^14)=16384^0.51702891=151
D(2^21)=(2^21)^0.612718364=7471
D(2^22)=(2^22)^0.624655214=13705
D(2^26)=(2^26)^0.662737112=153850
作者施承忠 2011.4.5
|
|