Algorithm 版 (精华区)
发信人: Enigma (谜般男子), 信区: Algorithm
标 题: [合集]一个生成素数的奇妙方法(转载) llhhxht
发信站: 哈工大紫丁香 (2004年03月02日14:17:51 星期二), 站内信件
发信人: llhhxht (绿林好汉--努力学习中), 信区: Math
标 题: [合集]一个生成素数的奇妙方法(转载)
发信站: 哈工大紫丁香 (Sat Mar 22 15:24:34 2003) , 转信
文章阅读 北大未名站 ○ 数学 讨论区 [Mathematics]
------------------------------------------------------------------------------
--
发信人: caldream (我是小猪我怕谁:)), 信区: Mathematics
标 题: [合集]一个生成素数的奇妙方法(转载)
发信站: 北大未名站 (2003年03月14日22:13:51 星期五), 转信
发信人: symplectic (愁容骑士), 信区: Mathematics
给定14个分数，按以下顺序排列：
17/91 78/85 19/51 23/38 29/33 77/29 95/23
77/19 1/17 11/13 13/11 15/14 15/2 55/1
然后拿两张纸。在第一张上写下2。然后对照着以上14个分数，
按以下规定步骤产生两个数列：
如果 r 是你在第一张纸上写的上一个数，就从上面列出的14个分数中找出一个分数，
使得它乘上 r 以后得到一个整数(如果这样的分数不止一个，就取最前头的那个)。把
这个整数写在第一张纸上。如果产生的整数是 2 的方幂，比如说 2^n，就在第二张纸
上写下 n。
照这个方法做下去，你在第二张纸上将得到一个什么样的数列呢？嘿嘿，你算过以后会
很惊奇的。它们是：2，3，5，7，11，13，17，19，23，......
这个东东是我在 Mathematical Intelligencer 80年的一期上看来的。写明是由
J.H. Conway 提出的问题。他问的意思是：后面这个数列是什么数列？为什么？如果
要产生前1000个素数，用这个方法要算多久？
发信人: dntx (冬鸟听雪), 信区: Mathematics
试着用计算机算了一下，第二张纸上数列增长速度太慢，
第一张纸算到近 280 项时，第二张纸才刚写到 5
再往后算一些就溢出 32 位的整数上界了。
发信人: symplectic (愁容骑士), 信区: Mathematics
你真照他给定的方法去编程和计算啊？有点太天真了噢。
你应该看到这个问题的实质与那些分数并没有关系，只不过定义了一个
10元数组(对应于2，3，5，7，11，13，17，19，23，29在素因子分解中的幂次)
的递推关系。(序列中的每一项都是一个10元数组。)
这个数组可以进一步简化为8元数组，因为仔细看看原来那14个分数中的两对就会
发现，23 和29 两个素因子在计算过程中并没起什么作用，可以化约掉。
发信人: dntx (冬鸟听雪), 信区: Mathematics
hehe. 都是文中说的“你算过以后会很惊奇的……”惹的祸。
本来想用手算的，后来发现实在不可行，就编了程序。
结果没被计算结果“惊奇”，反被计算过程“惊奇”了一下。:)
发信人: symplectic (愁容骑士), 信区: Mathematics
你应该想到分解素因子，那样手算也可以做一做。
我用手算出了2和3，然后就不敢往下算了。:)
估计计算量成线性甚至是二次增长。
发信人: farad (A**2*s**4/kg/m**2), 信区: Mathematics
下面101个数用附件中test.bat生成的(解压缩到同一目录直接运行test.bat生成list.txt
)
源程序为main1.cpp, VC++6 Console Application(main.cpp较慢)
怀疑是筛法的变形，本意想算150个，
应该可以算到29的平方之后，也许会出现不是素数的结果.
在PII上算了10分钟实在忍不住中断运算，发现才算到100个左右，
还没有检验结果是否都是素数.
运算量太可怕了(后两列)
Step | List 2 | Multiplication(s) | list 1 element(s)
1 2 129 19
2 3 296 50
3 5 1138 211
4 7 2172 427
5 11 7939 1656
6 13 7137 1513
7 17 19199 4192
8 19 14844 3251
9 23 35280 7882
10 29 77936 17665
11 31 38505 8685
12 37 129356 29673
13 41 112575 25888
14 43 73050 16719
15 47 147940 34194
16 53 272687 63359
17 59 334477 77991
18 61 145275 33645
19 67 434044 101533
20 71 337694 78966
21 73 206988 48175
22 79 615006 144369
23 83 461413 108268
24 89 769917 181195
25 97 1204092 283964
26 101 683149 160876
27 103 408594 95847
28 107 766598 180710
29 109 457074 107331
30 113 854973 201708
31 127 3432107 813127
32 131 1148709 271596
33 137 1864597 441635
34 139 739911 174465
35 149 3493185 828933
36 151 872034 205863
37 157 2420578 574293
38 163 2648378 628529
39 167 1865970 442494
40 173 3031153 719611
41 179 3148203 747939
42 181 1249665 295705
43 191 5792201 1377833
44 193 1419609 336177
45 197 2595929 616612
46 199 1508610 357383
47 211 8481167 2019436
48 223 9510965 2265520
49 227 3445909 819532
50 229 1994325 473153
51 233 3630326 863574
52 239 5626864 1340029
53 241 2207637 524009
54 251 10097658 2406899
55 257 6688798 1593421
56 263 6916081 1648047
57 269 7134081 1700347
58 271 2787894 662463
59 277 7569942 1804557
60 281 5278567 1257392
61 283 3038922 722383
62 293 13964184 3331387
63 307 21028216 5019689
64 311 6464673 1540964
65 313 3713931 883541
66 317 6716332 1601138
67 331 24837553 5930667
68 337 11216107 2676775
69 347 19545611 4667501
70 349 4612920 1098303
71 353 8327149 1986380
72 359 12727005 3038367
73 367 18052311 4310706
74 373 13945876 3329825
75 379 14638469 3495031
76 383 9801339 2339080
77 389 14948516 3570073
78 397 21115941 5044222
79 401 10743705 2564548
80 409 22800850 5447208
81 419 28104993 6717601
82 421 6703170 1597875
83 431 29751759 7111989
84 433 7089240 1690199
85 439 19769685 4722951
86 443 13110265 3130932
87 449 19927101 4762011
88 457 27848095 6656762
89 461 14196484 3390946
90 463 8101917 1932373
91 467 14568143 3479920
92 479 44580503 10661436
93 487 31722881 7584606
94 491 16102968 3847354
95 499 33780833 8076870
96 503 16899044 4037970
97 509 25619791 6125319
98 521 52817137 12634720
99 523 10329876 2465331
100 541 85443110 20442555
101 547 29601915 7079139
发信人: dntx (冬鸟听雪), 信区: Mathematics
分解后得到14条规则如下：
7 13 ==> 17
5 17 ==> 2 3 13
3 17 ==> 19
2 19 ==> 23
3 11 ==> 29
29 ==> 7 11
23 ==> 5 19
19 ==> 7 11
17 ==>
13 ==> 11
11 ==> 13
2 7 ==> 3 5
2 ==> 3 5
==> 5 11
初值为 2, 依次变为 3 5 ==> 3 5 5 11 ==> 5 5 29 ==> 5 5 7 11
==> 5 5 7 13 ==> 5 5 17 ==> 2 3 5 13 ==> 2 3 5 11 ==> 2 5 29
==> 2 5 7 11 ==> 2 5 7 13 ==> 2 5 17 ==> 2 2 3 13 ==> 2 2 3 11
==> 2 2 29 ==> 2 2 7 11 ==> 2 2 7 13 ==> 2 2 17 ==> 2 2
经 19 步得第一个素数 2
继续如此用计算机求得1000以内的如下结果，全部正确，且无一遗漏
而且初值比如取为 2 2 2 2 也可得到之后的素数结果。
相信这样生成的 的确 就是素数列。
运算速度量增长很快，算得1000以内结果用时5分钟，源程序一并附后。
只是百思不解其原理啊。
排位 得数 步数
1 2 19
2 3 69
3 5 280
4 7 707
5 11 2363
6 13 3876
7 17 8068
8 19 11319
9 23 19201
10 29 36866
11 31 45551
12 37 75224
13 41 101112
14 43 117831
15 47 152025
16 53 215384
17 59 293375
18 61 327020
19 67 428553
20 71 507519
21 73 555694
22 79 700063
23 83 808331
24 89 989526
25 97 1273490
26 101 1434366
27 103 1530213
28 107 1710923
29 109 1818254
30 113 2019962
31 127 2833089
32 131 3104685
33 137 3546320
34 139 3720785
35 149 4549718
36 151 4755581
37 157 5329874
38 163 5958403
39 167 6400897
40 173 7120508
41 179 7868447
42 181 8164152
43 191 9541985
44 193 9878162
45 197 10494774
46 199 10852157
47 211 12871593
48 223 15137113
49 227 15956645
50 229 16429798
51 233 17293372
52 239 18633401
53 241 19157410
54 251 21564309
55 257 23157730
56 263 24805777
57 269 26506124
58 271 27168587
59 277 28973144
60 281 30230536
61 283 30952919
62 293 34284306
63 307 39303995
64 311 40844959
65 313 41728500
66 317 43329638
67 331 49260305
68 337 51937080
69 347 56604581
70 349 57702884
71 353 59689264
72 359 62727631
73 367 67038337
74 373 70368162
75 379 73863193
76 383 76202273
77 389 79772346
78 397 84816568
79 401 87381116
80 409 92828324
81 419 99545925
82 421 101143800
83 431 108255789
84 433 109945988
85 439 114668939
86 443 117799871
87 449 122561882
88 457 129218644
89 461 132609590
90 463 134541963
91 467 138021883
92 479 148683319
93 487 156267925
94 491 160115279
95 499 168192149
96 503 172230119
97 509 178355438
98 521 190990158
99 523 193455489
100 541 213898044
101 547 220977183
102 557 233171454
103 563 240902183
104 569 248562182
105 571 251500547
106 577 259379978
107 587 272854935
108 593 281485222
109 599 289976825
110 601 293231916
111 607 301954455
112 613 311127710
113 617 317206526
114 619 320659405
115 631 339334723
116 641 355154150
117 643 358879839
118 647 365564827
119 653 375938100
120 659 386221443
121 661 390158564
122 673 411602658
123 677 418922646
124 683 430129247
125 691 445453897
126 701 464638310
127 709 481015194
128 719 501247561
129 727 518006131
130 733 531192200
131 739 544490259
132 743 553308603
133 751 571198241
134 757 584779076
135 761 594030270
136 769 613224764
137 773 622770262
138 787 656798521
139 797 681774804
140 809 712758046
141 811 718683785
142 821 745063696
143 823 751166019
144 827 762092981
145 829 768284576
146 839 795458785
147 853 836008872
148 857 847743638
149 859 854391283
150 863 866291059
151 877 908499608
152 881 920901358
153 883 927925519
154 887 940496891
155 907 1004951845
156 911 1018213239
157 919 1045583975
158 929 1079267538
159 937 1107152724
160 941 1121302572
161 947 1143409923
162 953 1165616972
163 967 1216956891
164 971 1232023987
165 977 1254989902
166 983 1278538923
167 991 1310329037
168 997 1333910908
源程序:
#include <stdio.h>
#include <stdlib.h>
#define N 14
#define M 10
int pnFactors[M];
int ppnSrc[N][M];
int ppnDes[N][M];
int pnPrimeNum[M] =
{
2,3,5,7,11,13,17,19,23,29
};
bool IsPrime(int n) {
for (int i = 2; i*i < n; i++) {
if (n%i == 0) return false;
}
return true;
}
void main()
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
ppnSrc[i][j] = 0;
ppnDes[i][j] = 0;
}
}
ppnSrc[0][3] = ppnSrc[0][5] = 1;
ppnDes[0][6] = 1;
ppnSrc[1][2] = ppnSrc[1][6] = 1;
ppnDes[1][0] = ppnDes[1][1] = ppnDes[1][5] = 1;
ppnSrc[2][1] = ppnSrc[2][6] = 1;
ppnDes[2][7] = 1;
ppnSrc[3][0] = ppnSrc[3][7] = 1;
ppnDes[3][8] = 1;
ppnSrc[4][1] = ppnSrc[4][4] = 1;
ppnDes[4][9] = 1;
ppnSrc[5][9] = 1;
ppnDes[5][3] = ppnDes[5][4] = 1;
ppnSrc[6][8] = 1;
ppnDes[6][2] = ppnDes[6][7] = 1;
ppnSrc[7][7] = 1;
ppnDes[7][3] = ppnDes[7][4] = 1;
ppnSrc[8][6] = 1;
ppnSrc[9][5] = 1;
ppnDes[9][4] = 1;
ppnSrc[10][4] = 1;
ppnDes[10][5] = 1;
ppnSrc[11][0] = ppnSrc[11][3] = 1;
ppnDes[11][1] = ppnDes[11][2] = 1;
ppnSrc[12][0] = 1;
ppnDes[12][1] = ppnDes[12][2] = 1;
ppnDes[13][2] = ppnDes[13][4] = 1;
printf("rules:\n");
for (i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (ppnSrc[i][j] == 1) printf(" %d ", pnPrimeNum[j]);
}
printf("==>");
for (j = 0; j < M; j++) {
if (ppnDes[i][j] == 1) printf(" %d ", pnPrimeNum[j]);
}
printf("\n");
}
printf("\n");
for (i = 0; i < M; i++) {
pnFactors[i] = 0;
}
pnFactors[0] = 1;
int nPrimeNum = 0;
for (int nn = 0; ; nn++) {
for (int i = 0; i < N; i++) {
bool bCanUse = true;
for (int j = 0; j < M; j++) {
if (pnFactors[j] < ppnSrc[i][j]) {
bCanUse = false;
break;
}
}
if (bCanUse) break;
}
bool bOnly2 = true;
for (int j = 0; j < M; j++) {
pnFactors[j] -= ppnSrc[i][j];
pnFactors[j] += ppnDes[i][j];
if (pnFactors[j] > 0 && j > 0) bOnly2 = false;
}
if (bOnly2) {
printf("%d\t%d\t%d\t", ++nPrimeNum, pnFactors[0], nn+1);
if (!IsPrime(pnFactors[0])) printf("error");
printf("\n");
}
}
}
发信人: symplectic (诗亡然后春秋作), 信区: Mathematics
斑竹为什么不 m 上呢？
另外，有两对规则可以合并。
容易看出“3 11 ==> 29”“29 ==> 7 11”可以合并成“3 11 ==> 7 11”。
另外还有“2 19 ==> 23”“23 ==> 5 19”可以合并成“2 19 ==> 5 19”。
规则的先后次序在这里正好也没什么影响。
生成素数序列的理由，我也没想通。很奇怪。
发信人: caldream (我是小猪我怕谁:)), 信区: Mathematics
感觉这个主题好的帖子比较多
准备做合集算了
所以留着
发信人: farad (A**2*s**4/kg/m**2), 信区: Mathematics
最新的程序见附件.
我认为main3.cpp(conwaymore.exe)是在我最初程序(main.cpp)
的数据结构和流程上最大限度改进了.
(已经进行了循环展开!)
在我用的PII 400M上dntx的程序似乎不比我的快，
现在大家的机器都非常好吗?！
不过dntx的规则对我倒有些启发，也许可以在数据结构上再作改进.
但是这个东西的原理到底有没有人知道?
--
※ 转载:·北大未名站 bbs.pku.edu.cn·[FROM: 202.120.183.1]
------------------------------------------------------------------------------
--
本讨论区 主题模式 上一篇 下一篇 回信给作者 同主题展开
--
※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 218.9.120.174]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：200.190毫秒