埃拉托斯特尼筛法的模块理论

小草

埃拉托斯特尼筛法的模块理论

    文/施承忠


1：自然数模块

A1[1]1
B1[2]1
A2[3,4]2
B2[5,6]2
A3[7,8,9]3
B3[10,11,12]3
A4[13,14,15,16]4
B4[17,18,19,20]4
A5[21,22,23,24,25]5
B5[26,27,28,29,30]5
A6[31,32,33,34,35,36]6
B6[37,38,39,40,41,42]6
A7[43,44,45,46,47,48,49]7
B7,50,51,52,53,54,55,56]7
A8[57,58,59,60,61,62,63,64]8
B8[65,66,67,68,69,70,71,72]8
A9[73,74,75,76,77,78,79,80,81]9
B9[82,83,84,85,86,87,88,89,90]9
A10[91,92,93,94,95,96,97,98,99,100]10
B10[101,102,103,104,105,106,107,108,109,110]10

自然数模块可以无限延伸，可以包括所有自然数。
每一块自然数模块都有它自身的模值，我们都把它标注在模块右边。

不大于t的自然数，需要多少个模块才能得到，这处决于这些自然数包括在哪些模块中。

比如不大于25的自然数包括在
A1[1]1
B1[2]1
A2[3,4]2
B2[5,6]2
A3[7,8,9]3
B3[10,11,12]3
A4[13,14,15,16]4
B4[17,18,19,20]4
A5[21,22,23,24,25]5中
在这些模块中，它的模值是(2∑(1,5)5)-5,就是5^2.它的真值也是
5^2，模值=真值.

比如不大于29的自然数包括在
A1[1]1
B1[2]1
A2[3,4]2
B2[5,6]2
A3[7,8,9]3
B3[10,11,12]3
A4[13,14,15,16]4
B4[17,18,19,20]4
A5[21,22,23,24,25]5
B5[26,27,28,29,30]5中

在这些模块中，它的模值是(2∑(1,5)5,就是(5^2)+5.它的真值是
(5^2)+4，模值>真值.


2:埃拉托斯特尼筛法模块

A[1]1
B[2]1
p1[3,5]2
g1[4,6]2
p2[7,11,13]3
g2[9,15,21]3
g1[8,10,12,14]4
g1[16,18,20,22]4
p3[17,19,23,29,31]5
g3[25,35,55,65,85]5
g1[24,26,28,30,32,34]6
g1[36,38,40,42,44,46]6
p4[37,41,43,47,53,59,61]7
g4[49,77,91,119,133,161,203]7
g1[48,50,52,54,56,58,60,62]8
g1[64,66,68,70,72,74,76,78]8
g2[27,33,39,45,51,57,63,69,75]9
g2[81,87,93,99,105,111,117,123,129]9
g1[80,82,84,86,88,90,92,94,96,98]10
g1[100,102,104,106,108,110,112,114,116,118]10
p5[67,71,73,79,83,89,97,101,103,107,109]11
g5[121,143,187,209,253,319,341,407,451,473,517]11
g1[120,122,124,126,128,130,132,134,136,138,140,142]12
g1[144,146,148,150,152,154,156,158,160,162,164,166]12
p6[113,127,131,137,139,149,151,157,163,167,173,179,181]13

埃拉托斯特尼筛法模块由A[1]1，B[2]1，pk[]t,gk[]t组成。
其中A[1]1，B[2]1，分别代表1和2.pk[]t代表t个素数，gk[]t代表素因子不小于pk的t个合数。

埃拉托斯特尼筛法模块可以无限延伸，可以包括所有自然数,也包括所有素数和合数。

每一块埃拉托斯特尼筛法模块都有它自身的模值，我们都把它标注在模块右边。

不大于t的自然数，需要多少个埃拉托斯特尼筛法模块才能得到，这处决于这些自然数包括在哪些模块中。

比如不大于25的自然数模块，它有一个与它等模值的模块组合；

A[1]1
B[2]1
p1[3,5]2
g1[4,6]2
p2[7,11,13]3
g2[9,15,21]3
g1[8,10,12,14]4
g1[16,18,20,22]4
p3[17,19,23,29,31]5
它分别由A[1]1=1；p1[3,5]2，p2[7,11,13]3，p3[17,19,23,29,31]5
；g1[4,6]2，g1[8,10,12,14]4，g1[16,18,20,22]4，g2[9,15,21]3.
组成。

这时候
A[1]1.B[2]1，p1[3,5]2，p2[7,11,13]3，p3[17,19,23,29,31]5，素数个数=1+2+3+5=模值11.π(25)的
模值=11，π(25)的真值=9

g1[4,6]2，g1[8,10,12,14]4，g1[16,18,20,22]4，g1合数的个数=
2+4+4=模值10.真值=11

g2[9,15,21]3,g2的合数个数=模值3，真值=3.

共计模值25.合数个数G(25)模值13，真值15

但是不大于25的自然数只有1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23只有23个，而29,31>25.所以模块是不完整的。

它的完整的模块应该是：
t=25
A1[1]1      
B1[2]1      
p1[3,5]2
g1[4,6]2
p2[7,11,13]3
g2[9,15,21]3
g1[8,10,12,14]4
g1[16,18,20,22]4
p3[17,19,23,29,31]5
g3[25,35,55,65,85]5   
g1[24,26,28,30,32,34]6

其中g1合数的个数由模值10变成了模值16，还增加了模块g3[25,35,55,65,85]5.

总模值从原来的25变成了36，其中π(25)的模值=11，真值=9.
合数G(25)的模值=24.真值=15. 

小草

3素数模块

当我们只求素数不求合数时，我们就只要素数模块就够了。

素数模块
B[2]1
p1[3,5]2
p2[7,11,13]3
p3[17,19,23,29,31]5
p4[37,41,43,47,53,59,61]7
p5[67,71,73,79,83,89,97,101,103,107,109]11
p6[113,127,131,137,139,149,151,157,163,167,173,179,181]13

当t=2时
π(2^2)的模值是B[2]1，p1[3,5]2=1+2=3.真值=3-1=2.
π(3^2)的模值是B[2]1，p1[3,5]2,p2[7,11,13]3=1+2+3=6.真值=6-2=4.
π(5^2)的模值是B[2]1，p1[3,5]2,p2[7,11,13]3，p3[17,19,23,29,31]5=1+2+3+5=11.真值=11-2=9.

我们确知当真值小于模值时，一定存在一个T>t^2,使得π(T)>π(t^2)的模值。
现确定T=2t^2.
这时候
π(2*2^2)>π(2^2)模值=4>3.
π(2*3^2)>π(3^2)模值=7>6.
π(2*5^2)>π(5^2)模值=15>11.

我们确知当真值大于模值时，一定存在一个T<t^2,使得π(T)<π(t^2)的模值。
现确定T=t^2.模值=2*模值。
这时候
π(2^2)<2π(2^2)模值=2>6.
π(3^2)<2π(3^2)模值=4>12.
π(5^2)<2π(5^2)模值=9>22.


4孪生素数筛法模块

q1[(3,5),(5,7),(11,13)]3
q2[(17,19),(29,31),(41,43),(59,61),(71,73)]5
p4[7,13,19,23,31,37,43]7
q3[(101,103),(107,109),(137,139),(149,151),(179,181),
(191,193),(197,199),(227,229),(239,241),(269,271),
(281,283)]11
p6[47,53,61,67,73,79,83,89,97,103,109,113,127]13
q4[(311,313),(347,349),(419,421),(431,433),(461,463),
(521,523),(569,571),(599,601),(617,619),(641,643),
(659,661),(809,811),(821,823),(827,829),(857,859),
(881,883),(1019,1021]17
我们从孪生素数筛法模块中分离出孪生素数模块。

小草

5孪生素数模块

当我们只求孪生素数不素数数时，我们就只要孪生素数模块就够了。
q1[(3,5),(5,7),(11,13)]3
q2[(17,19),(29,31),(41,43),(59,61),(71,73)]5
q3[(101,103),(107,109),(137,139),(149,151),(179,181),
(191,193),(197,199),(227,229),(239,241),(269,271),
(281,283)]11
q4[(311,313),(347,349),(419,421),(431,433),(461,463),
(521,523),(569,571),(599,601),(617,619),(641,643),
(659,661),(809,811),(821,823),(827,829),(857,859),
(881,883),(1019,1021]17

我们用T(x)表不大于x的孪生素数对数。
当t=3时
2*3^2的模值是q1[(3,5),(5,7),(11,13)]3=3.真值是=3
当t=5时
2*5^2的模值是q1[(3,5),(5,7),(11,13)]3=3，q2[(17,19),(29,31),(41,43),(59,61),(71,73)]5=3+5=8，真值是
8-2=6
当t=11时
2*11^2的模值是q1[(3,5),(5,7),(11,13)]3=3，q2[(17,19),(29,31),(41,43),(59,61),(71,73)]5，
q3[(101,103),(107,109),(137,139),(149,151),(179,181),
(191,193),(197,199),(227,229),(239,241),(269,271),
(281,283)]11=3+5+11=19，真值是19-2=17
当T=3*3^2时
T(3*3^2)=4>3
当T=3*5^2时
T(3*5^2)=8=8
当T=3*11^2时
T(3*11^2)=21>19
当T=2*3^2不变,模值=2*模值时
T(2*3^2)=3<6
当T=2*5^2时
T(2*5^2)=8<16
当T=3*11^2时
T(3*11^2)=21<38


6偶数哥德巴赫筛法模块

T=4*3^2
36
B1[2]1
p1[3,11]2
q1[(5+31),(7+29),(13+23)]3
q2[(17+19),19,23,29,31]5

偶数36哥德巴赫素数模块
q1[(5+31),(7+29),(13+23)]3
q2[(17+19),19,23,29,31]5
模值3，真值4

T=4*5^2
100
B1[2]1
p1[5,7]2
q1[(3+97),(11+89),(17+83)]3
q2[(29+71),(41+59),(47+53),13,19]5
p4[23,31,37,43,53,59]7
q3[61,67,71,73,79,83,89,97,101,103]11

偶数100哥德巴赫素数模块
q1[(3+97),(11+89),(17+83)]3
q2[(29+71),(41+59),(47+53),13,19]5
模值3+5=8，真值8-2=6

当T=4*4qn^2时
D(5*4*3^2)=14>3
D(5*4*5^2)=13>8
D(5*4*11^2)=48>19

当T=4qn^2,模值=3*基本模值时
D(4*3^2)=4<9
D(4*5^2)=6<24
D(4*11^2)=14<57

小草

求π(5^2):
我们有不大于5^2的所有自然数模块
A1[1]1
B1[2]1
A2[3,4]2
B2[5,6]2
A3[7,8,9]3
B3[10,11,12]3
A4[13,14,15,16]4
B4[17,18,19,20]4
A5[21,22,23,24,25]5

利用埃拉托斯特尼筛法得到素数3,5,7,11,13,17,19,23.
交换素数3,5,7,11,13,17,19,23到素数模块。
将
B1[2]1
A2[3,4]2
A3[7,8,9]3
A5[21,22,23,24,25]5
变成
B1[2]1
p1[3,5]2
p2[7,11,13]3
p3[17,19,23,24,25]5
得到
A1[1]1
B1[2]1
p1[3,5]2
B2[4,6]2
p2[7,11,13]3
B3[10,8,12]3
A4[9,14,15,16]4
B4[21,18,22,20]4
p3[17,19,23,24,25]5
得到π(5^2)=9

经过埃拉托斯特尼筛法得到埃拉托斯特尼筛法模块
A[1]1
B[2]1
p1[3,5]2
g1[4,6]2
p2[7,11,13]3
g2[9,15,21]3
g1[8,10,12,14]4
g1[16,18,20,22]4
p3[17,19,23,29,31]5
分离出素数模块
B[2]1
p1[3,5]2
p2[7,11,13]3
p3[17,19,23,29,31]5
得到模值
1+2+3+5=11
用交换法得到
B1[2]1
p1[3,5]2
p2[7,11,13]3
p3[17,19,23,24,25]5
得到真值9

小草

我可以一辈子为数学做贡献，但是我不能为数学去牺牲我的快乐。如果我牺牲了自己的快乐，那么我的数学将随它一起牺牲。