|
根据双筛法及素数定理可进一步推得:r2(N)=(N/2)∏mr≥[N/(lnN )^2 ]≥1
证明:
对于共轭互逆数列A、B:
A:{1,3,5,7,9,……,(N-1)}
B:{(N-1),……,9,7,5,3,1}
显然N=A+B
根据埃氏筛法获得奇素数集合{Pr}:
{1,3,5,…,Pr},Pr<√N
为了获得偶数N的(1+1)表法数,按照双筛法进行分步操作:
第1步:将互逆数列用3双筛后得到真实剩余比m1
第2步:将余下的互逆数列再用5双筛后得到真实剩余比m2
第3步:将余下的互逆数列再用7双筛后得到真实剩余比m3
…
依次类推到:
第r步:将余下的互逆数列再用Pr双筛后得到真实剩余比mr
这样就完成了对偶数N的求双筛法(1+1)表法数,根据乘法原理有:
r2(N)=(N/2)*m1*m2*m3*…*mr
即r2(N)=(N/2)∏mr
例如:
[√70]=8,{Pr}={1,3,5,7},
3|/70,首先这35个奇数用3双筛后得到剩余13个奇数,则其真实剩余比:m1=13/35
5|70, 剩余的13个奇数再用5双筛剩余10个奇数,则其真实剩余比:m2=10/13
7|70, 剩余的10个奇数再用7双筛剩余10个奇数,则其真实剩余比:m3=10/10
根据真值公式得:
r2(70)
=(70/2)*m1*m2*m3
=35*13/35*10/13*10/10
=10
r2(70)=10
分析双筛法r2(N)的下限值:
双筛法本质上第一步:先对A数列筛选,根据素数定理,A中至少有[N/lnN ]≥1个奇素数,
即此时的共轭互逆数列AB中至少有[ N/lnN ]个奇素数
第二步:再对B数列进行筛选,筛子是相同的1/lnN
则根据乘法原理由此推得共轭数列AB中至少有:r2(N)≥[N/(lnN )^2 ]≥1个奇素数。
例如:30第一步:先对A数列筛选,A中至少有[ N/lnN ]=[30/ln30 ]=8个奇素数,而π(30)=10
即此时的共轭互逆数列AB中至少有[N/lnN ]=[30/ln30 ]=8个奇素数。
A 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
B 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1
第二步:再对B数列进行筛选,筛子是相同的 , 由此推得共轭数列AB中至少有:
r2(30)≥[30/(ln30 )^2 ]=2个奇素数,而r2(30)=8
A 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
B 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1
故:r2(N)=(N/2)∏mr≥[ N/(lnN )^2 ]≥1个奇素数
|
|