同余筛法(5)

小草

                   同余筛法(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