|
|

楼主 |
发表于 2026-5-16 16:53
|
显示全部楼层
好的,改为纯文本逐行格式,便于复制。
---
附录:结构常数递归去重算法完整演算
A.1 算法定义
设 N 为偶数,定义:
\begin{aligned}
S&=\frac{N}{2} \\
N(p)&=\frac{(p-1)^2}{2} \\
R(p)&=\left\lfloor \frac{S-N(p)}{p} \right\rfloor \\
\Delta(X,q)&=\left\lfloor \frac{X+\frac{q-1}{2}-N(q)}{q} \right\rfloor \\
\Delta^*(X,q)&=\Delta(X,q)-\sum_{r<q}\Delta^*(\Delta(X,q),r) \\
V(p)&=R(p)-\sum_{q<p}\Delta^*\left(R(p)+\frac{p-1}{2}-N(q),\ q\right) \\
\pi(N)&=S-\sum_{p\in\mathcal{P}} V(p)
\end{aligned}
其中 \mathcal{P}=\{p\mid 3\le p\le\sqrt{N},\ p\text{ 为奇素数}\}。
---
A.2 N=10000 完整演算
\sqrt{10000}=100,\mathcal{P}=\{3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97\},共24个。
S=5000
p=3
N(3)=2,\ R(3)=\lfloor(5000-2)/3\rfloor=1666
V(3)=1666
p=5
N(5)=8,\ R(5)=\lfloor(5000-8)/5\rfloor=998
X_3=998+2-2=998,\ \Delta_3=332,\ \Delta_3^*=332
V(5)=998-332=666
p=7
N(7)=18,\ R(7)=\lfloor(5000-18)/7\rfloor=711
X_3=711+3-2=712,\ \Delta_3=237,\ \Delta_3^*=237
X_5=711+3-8=706,\ \Delta_5=141,\ \Delta_5^*=141-47=94
V(7)=711-237-94=380
p=11
N(11)=50,\ R(11)=\lfloor(5000-50)/11\rfloor=450
X_3=450+5-2=453,\ \Delta_3=151,\ \Delta_3^*=150
X_5=450+5-8=447,\ \Delta_5=89,\ \Delta_5^*=89-29=60
V(11)=450-150-60=240
p=13
N(13)=72,\ R(13)=\lfloor(5000-72)/13\rfloor=379
X_3=379+6-2=383,\ \Delta_3=127,\ \Delta_3^*=126
X_5=379+6-8=377,\ \Delta_5=75,\ \Delta_5^*=75-25=50
V(13)=379-126-50=203
p=17
N(17)=128,\ R(17)=\lfloor(5000-128)/17\rfloor=286
X_3=286+8-2=292,\ \Delta_3=97,\ \Delta_3^*=95
X_5=286+8-8=286,\ \Delta_5=57,\ \Delta_5^*=57-19=38
V(17)=286-95-38=153
p=19
N(19)=162,\ R(19)=\lfloor(5000-162)/19\rfloor=254
X_3=254+9-2=261,\ \Delta_3=87,\ \Delta_3^*=85
X_5=254+9-8=255,\ \Delta_5=51,\ \Delta_5^*=51-17=34
V(19)=254-85-34=135
p=23
N(23)=242,\ R(23)=\lfloor(5000-242)/23\rfloor=206
X_3=206+11-2=215,\ \Delta_3=71,\ \Delta_3^*=68
X_5=206+11-8=209,\ \Delta_5=41,\ \Delta_5^*=41-13=28
V(23)=206-68-28=110
p=29
N(29)=392,\ R(29)=\lfloor(5000-392)/29\rfloor=158
X_3=158+14-2=170,\ \Delta_3=56,\ \Delta_3^*=52
X_5=158+14-8=164,\ \Delta_5=32,\ \Delta_5^*=32-10=22
V(29)=158-52-22=84
p=31
N(31)=450,\ R(31)=\lfloor(5000-450)/31\rfloor=146
X_3=146+15-2=159,\ \Delta_3=53,\ \Delta_3^*=49
X_5=146+15-8=153,\ \Delta_5=30,\ \Delta_5^*=30-10=20
V(31)=146-49-20=77
p=37
N(37)=648,\ R(37)=\lfloor(5000-648)/37\rfloor=117
X_3=117+18-2=133,\ \Delta_3=44,\ \Delta_3^*=39
X_5=117+18-8=127,\ \Delta_5=25,\ \Delta_5^*=25-8=17
V(37)=117-39-17=61
p=41
N(41)=800,\ R(41)=\lfloor(5000-800)/41\rfloor=102
X_3=102+20-2=120,\ \Delta_3=40,\ \Delta_3^*=34
X_5=102+20-8=114,\ \Delta_5=22,\ \Delta_5^*=22-7=15
V(41)=102-34-15=53
p=43
N(43)=882,\ R(43)=\lfloor(5000-882)/43\rfloor=95
X_3=95+21-2=114,\ \Delta_3=38,\ \Delta_3^*=32
X_5=95+21-8=108,\ \Delta_5=21,\ \Delta_5^*=21-7=14
V(43)=95-32-14=49
p=47
N(47)=1058,\ R(47)=\lfloor(5000-1058)/47\rfloor=83
X_3=83+23-2=104,\ \Delta_3=34,\ \Delta_3^*=27
X_5=83+23-8=98,\ \Delta_5=19,\ \Delta_5^*=19-6=13
V(47)=83-27-13=43
p=53
N(53)=1352,\ R(53)=\lfloor(5000-1352)/53\rfloor=68
X_3=68+26-2=92,\ \Delta_3=30,\ \Delta_3^*=22
X_5=68+26-8=86,\ \Delta_5=17,\ \Delta_5^*=17-5=12
V(53)=68-22-12=34
p=59
N(59)=1682,\ R(59)=\lfloor(5000-1682)/59\rfloor=56
X_3=56+29-2=83,\ \Delta_3=27,\ \Delta_3^*=18
X_5=56+29-8=77,\ \Delta_5=15,\ \Delta_5^*=15-5=10
V(59)=56-18-10=28
p=61
N(61)=1800,\ R(61)=\lfloor(5000-1800)/61\rfloor=52
X_3=52+30-2=80,\ \Delta_3=26,\ \Delta_3^*=17
X_5=52+30-8=74,\ \Delta_5=14,\ \Delta_5^*=14-4=10
V(61)=52-17-10=25
p=67
N(67)=2178,\ R(67)=\lfloor(5000-2178)/67\rfloor=42
X_3=42+33-2=73,\ \Delta_3=24,\ \Delta_3^*=14
X_5=42+33-8=67,\ \Delta_5=13,\ \Delta_5^*=13-4=9
V(67)=42-14-9=19
p=71
N(71)=2450,\ R(71)=\lfloor(5000-2450)/71\rfloor=35
X_3=35+35-2=68,\ \Delta_3=22,\ \Delta_3^*=12
X_5=35+35-8=62,\ \Delta_5=12,\ \Delta_5^*=12-4=8
V(71)=35-12-8=15
p=73
N(73)=2592,\ R(73)=\lfloor(5000-2592)/73\rfloor=33
X_3=33+36-2=67,\ \Delta_3=22,\ \Delta_3^*=11
X_5=33+36-8=61,\ \Delta_5=12,\ \Delta_5^*=12-4=8
V(73)=33-11-8=14
p=79
N(79)=3042,\ R(79)=\lfloor(5000-3042)/79\rfloor=24
X_3=24+39-2=61,\ \Delta_3=20,\ \Delta_3^*=8
X_5=24+39-8=55,\ \Delta_5=11,\ \Delta_5^*=11-3=8
V(79)=24-8-8=8
p=83
N(83)=3442,\ R(83)=\lfloor(5000-3442)/83\rfloor=18
X_3=18+41-2=57,\ \Delta_3=19,\ \Delta_3^*=7
X_5=18+41-8=51,\ \Delta_5=10,\ \Delta_5^*=10-3=7
V(83)=18-7-7=4
p=89
N(89)=3912,\ R(89)=\lfloor(5000-3912)/89\rfloor=12
X_3=12+44-2=54,\ \Delta_3=18,\ \Delta_3^*=6
X_5=12+44-8=48,\ \Delta_5=9,\ \Delta_5^*=9-3=6
V(89)=12-6-6=0
p=97
N(97)=4656,\ R(97)=\lfloor(5000-4656)/97\rfloor=3
X_3=3+48-2=49,\ \Delta_3=16,\ \Delta_3^*=4
X_5=3+48-8=43,\ \Delta_5=8,\ \Delta_5^*=8-2=6
V(97)=3-4-6=-7
求和
\sum V(p)=1666+666+380+240+203+153+135+110+84+77+61+53+49+43+34+28+25+19+15+14+8+4+0-7=4190
结果
\pi(10000)=5000-4190=1229
---
A.3 N=20000 完整演算
\sqrt{20000}\approx141.42,\mathcal{P}=\{3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139\},共34个。
S=10000
p=3
N(3)=2,\ R(3)=\lfloor(10000-2)/3\rfloor=3333
V(3)=3333
p=5
N(5)=8,\ R(5)=\lfloor(10000-8)/5\rfloor=1998
X_3=1998+2-2=1998,\ \Delta_3=666,\ \Delta_3^*=666
V(5)=1998-666=1332
p=7
N(7)=18,\ R(7)=\lfloor(10000-18)/7\rfloor=1426
X_3=1426+3-2=1427,\ \Delta_3=475,\ \Delta_3^*=475
X_5=1426+3-8=1421,\ \Delta_5=284,\ \Delta_5^*=284-94=190
V(7)=1426-475-190=761
p=11
N(11)=50,\ R(11)=\lfloor(10000-50)/11\rfloor=904
X_3=904+5-2=907,\ \Delta_3=302,\ \Delta_3^*=301
X_5=904+5-8=901,\ \Delta_5=180,\ \Delta_5^*=180-60=120
V(11)=904-301-120=483
p=13
N(13)=72,\ R(13)=\lfloor(10000-72)/13\rfloor=763
X_3=763+6-2=767,\ \Delta_3=255,\ \Delta_3^*=254
X_5=763+6-8=761,\ \Delta_5=152,\ \Delta_5^*=152-50=102
V(13)=763-254-102=407
p=17
N(17)=128,\ R(17)=\lfloor(10000-128)/17\rfloor=580
X_3=580+8-2=586,\ \Delta_3=195,\ \Delta_3^*=193
X_5=580+8-8=580,\ \Delta_5=116,\ \Delta_5^*=116-38=78
V(17)=580-193-78=309
p=19
N(19)=162,\ R(19)=\lfloor(10000-162)/19\rfloor=517
X_3=517+9-2=524,\ \Delta_3=174,\ \Delta_3^*=172
X_5=517+9-8=518,\ \Delta_5=103,\ \Delta_5^*=103-34=69
V(19)=517-172-69=276
p=23
N(23)=242,\ R(23)=\lfloor(10000-242)/23\rfloor=424
X_3=424+11-2=433,\ \Delta_3=144,\ \Delta_3^*=141
X_5=424+11-8=427,\ \Delta_5=85,\ \Delta_5^*=85-28=57
V(23)=424-141-57=226
p=29
N(29)=392,\ R(29)=\lfloor(10000-392)/29\rfloor=331
X_3=331+14-2=343,\ \Delta_3=114,\ \Delta_3^*=110
X_5=331+14-8=337,\ \Delta_5=67,\ \Delta_5^*=67-22=45
V(29)=331-110-45=176
p=31
N(31)=450,\ R(31)=\lfloor(10000-450)/31\rfloor=308
X_3=308+15-2=321,\ \Delta_3=107,\ \Delta_3^*=103
X_5=308+15-8=315,\ \Delta_5=63,\ \Delta_5^*=63-21=42
V(31)=308-103-42=163
p=37
N(37)=648,\ R(37)=\lfloor(10000-648)/37\rfloor=252
X_3=252+18-2=268,\ \Delta_3=89,\ \Delta_3^*=84
X_5=252+18-8=262,\ \Delta_5=52,\ \Delta_5^*=52-17=35
V(37)=252-84-35=133
p=41
N(41)=800,\ R(41)=\lfloor(10000-800)/41\rfloor=224
X_3=224+20-2=242,\ \Delta_3=80,\ \Delta_3^*=74
X_5=224+20-8=236,\ \Delta_5=47,\ \Delta_5^*=47-15=32
V(41)=224-74-32=118
p=43
N(43)=882,\ R(43)=\lfloor(10000-882)/43\rfloor=212
X_3=212+21-2=231,\ \Delta_3=77,\ \Delta_3^*=71
X_5=212+21-8=225,\ \Delta_5=45,\ \Delta_5^*=45-15=30
V(43)=212-71-30=111
p=47
N(47)=1058,\ R(47)=\lfloor(10000-1058)/47\rfloor=190
X_3=190+23-2=211,\ \Delta_3=70,\ \Delta_3^*=63
X_5=190+23-8=205,\ \Delta_5=41,\ \Delta_5^*=41-13=28
V(47)=190-63-28=99
p=53
N(53)=1352,\ R(53)=\lfloor(10000-1352)/53\rfloor=163
X_3=163+26-2=187,\ \Delta_3=62,\ \Delta_3^*=54
X_5=163+26-8=181,\ \Delta_5=36,\ \Delta_5^*=36-12=24
V(53)=163-54-24=85
p=59
N(59)=1682,\ R(59)=\lfloor(10000-1682)/59\rfloor=140
X_3=140+29-2=167,\ \Delta_3=55,\ \Delta_3^*=46
X_5=140+29-8=161,\ \Delta_5=32,\ \Delta_5^*=32-10=22
V(59)=140-46-22=72
p=61
N(61)=1800,\ R(61)=\lfloor(10000-1800)/61\rfloor=134
X_3=134+30-2=162,\ \Delta_3=54,\ \Delta_3^*=45
X_5=134+30-8=156,\ \Delta_5=31,\ \Delta_5^*=31-10=21
V(61)=134-45-21=68
p=67
N(67)=2178,\ R(67)=\lfloor(10000-2178)/67\rfloor=116
X_3=116+33-2=147,\ \Delta_3=49,\ \Delta_3^*=39
X_5=116+33-8=141,\ \Delta_5=28,\ \Delta_5^*=28-9=19
V(67)=116-39-19=58
p=71
N(71)=2450,\ R(71)=\lfloor(10000-2450)/71\rfloor=106
X_3=106+35-2=139,\ \Delta_3=46,\ \Delta_3^*=36
X_5=106+35-8=133,\ \Delta_5=26,\ \Delta_5^*=26-8=18
V(71)=106-36-18=52
p=73
N(73)=2592,\ R(73)=\lfloor(10000-2592)/73\rfloor=101
X_3=101+36-2=135,\ \Delta_3=45,\ \Delta_3^*=34
X_5=101+36-8=129,\ \Delta_5=25,\ \Delta_5^*=25-8=17
V(73)=101-34-17=50
p=79
N(79)=3042,\ R(79)=\lfloor(10000-3042)/79\rfloor=88
X_3=88+39-2=125,\ \Delta_3=41,\ \Delta_3^*=29
X_5=88+39-8=119,\ \Delta_5=23,\ \Delta_5^*=23-7=16
V(79)=88-29-16=43
p=83
N(83)=3442,\ R(83)=\lfloor(10000-3442)/83\rfloor=79
X_3=79+41-2=118,\ \Delta_3=39,\ \Delta_3^*=27
X_5=79+41-8=112,\ \Delta_5=22,\ \Delta_5^*=22-7=15
V(83)=79-27-15=37
p=89
N(89)=3912,\ R(89)=\lfloor(10000-3912)/89\rfloor=68
X_3=68+44-2=110,\ \Delta_3=36,\ \Delta_3^*=24
X_5=68+44-8=104,\ \Delta_5=20,\ \Delta_5^*=20-6=14
V(89)=68-24-14=30
p=97
N(97)=4656,\ R(97)=\lfloor(10000-4656)/97\rfloor=55
X_3=55+48-2=101,\ \Delta_3=33,\ \Delta_3^*=20
X_5=55+48-8=95,\ \Delta_5=19,\ \Delta_5^*=19-6=13
V(97)=55-20-13=22
p=101
N(101)=5000,\ R(101)=\lfloor(10000-5000)/101\rfloor=49
X_3=49+50-2=97,\ \Delta_3=32,\ \Delta_3^*=18
X_5=49+50-8=91,\ \Delta_5=18,\ \Delta_5^*=18-6=12
V(101)=49-18-12=19
p=103
N(103)=5202,\ R(103)=\lfloor(10000-5202)/103\rfloor=46
X_3=46+51-2=95,\ \Delta_3=31,\ \Delta_3^*=17
X_5=46+51-8=89,\ \Delta_5=17,\ \Delta_5^*=17-5=12
V(103)=46-17-12=17
p=107
N(107)=5618,\ R(107)=\lfloor(10000-5618)/107\rfloor=40
X_3=40+53-2=91,\ \Delta_3=30,\ \Delta_3^*=16
X_5=40+53-8=85,\ \Delta_5=17,\ \Delta_5^*=17-5=12
V(107)=40-16-12=12
p=109
N(109)=5832,\ R(109)=\lfloor(10000-5832)/109\rfloor=38
X_3=38+54-2=90,\ \Delta_3=30,\ \Delta_3^*=16
X_5=38+54-8=84,\ \Delta_5=16,\ \Delta_5^*=16-5=11
V(109)=38-16-11=11
p=113
N(113)=6272,\ R(113)=\lfloor(10000-6272)/113\rfloor=33
X_3=33+56-2=87,\ \Delta_3=29,\ \Delta_3^*=15
X_5=33+56-8=81,\ \Delta_5=16,\ \Delta_5^*=16-5=11
V(113)=33-15-11=7
p=127
N(127)=7938,\ R(127)=\lfloor(10000-7938)/127\rfloor=16
X_3=16+63-2=77,\ \Delta_3=25,\ \Delta_3^*=11
X_5=16+63-8=71,\ \Delta_5=14,\ \Delta_5^*=14-4=10
V(127)=16-11-10=-5
p=131
N(131)=8450,\ R(131)=\lfloor(10000-8450)/131\rfloor=11
X_3=11+65-2=74,\ \Delta_3=24,\ \Delta_3^*=10
X_5=11+65-8=68,\ \Delta_5=13,\ \Delta_5^*=13-4=9
V(131)=11-10-9=-8
p=137
N(137)=9248,\ R(137)=\lfloor(10000-9248)/137\rfloor=5
X_3=5+68-2=71,\ \Delta_3=23,\ \Delta_3^*=9
X_5=5+68-8=65,\ \Delta_5=13,\ \Delta_5^*=13-4=9
V(137)=5-9-9=-13
p=139
N(139)=9522,\ R(139)=\lfloor(10000-9522)/139\rfloor=3
X_3=3+69-2=70,\ \Delta_3=23,\ \Delta_3^*=9
X_5=3+69-8=64,\ \Delta_5=12,\ \Delta_5^*=12-4=8
V(139)=3-9-8=-14
求和
\sum V(p)=3333+1332+761+483+407+309+276+226+176+163+133+118+111+99+85+72+68+58+52+50+43+37+30+22+19+17+12+11+7-5-8-13-14=7742
结果
\pi(20000)=10000-7742=2262
---
A.4 验证结论
\pi(10000)=1229,\pi(20000)=2262,均与标准素数计数真值完全一致。 |
|