数学研发论坛

 找回密码
 欢迎注册
楼主: medie2005

[讨论] 强伪循环素数

[复制链接]
发表于 2008-8-28 15:45:26 | 显示全部楼层
那只可能是最高位有一个数字是
你能举一个例子么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-28 17:51:17 | 显示全部楼层
直接穷举所有$10^8$以内数据没有什么特别的难度:
11
14
16
31
32
34
35
38
71
73
74
76
91
92
95
97
98

118
316
712
715
914
131
331
731
736
935
176
373
772
775
778
971
973
191
194
398
793
794
797
991


1118
3112
1312
7318
9712
7912
7915
7132
9131
1336
1931
9931
9934
7376
9371
1774
3772
7771
9976
1195
7198
9194
3394
9392
3793
7793
9791
3992


99316
77131
37732
19738
13931
31174
97171
39175
17372
99371
39971
99971
33392
19391
99394
99793
97993

931118
997114
311312
773312
731914
991912
771131
337138
779131
731338
171331
393331
999331
311735
319934
939178
971371
779375
779378
317774
177776
797774
939775
731975
991972
991976
991196
913195
173198
319195
311398
137395
119395
939391
331798
993791
397792
119792


9317318
3737174
7131772
9777791

77739371
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-28 18:12:22 | 显示全部楼层


那就说明可能不如LZ的稀罕
但也是越来越少吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-28 18:21:38 | 显示全部楼层
使得,而且9位数就你找出来的那个解
所以用8#的算法筛到$10^19$应该问题不大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-28 20:48:48 | 显示全部楼层
还是神秘的127位回文素数最好求了
只要用1024 * 1024个IA64 1.2G CPU + 1024T内存
和万兆光网络连接
不到一个星期就能搜索完

特容易
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-29 11:31:34 | 显示全部楼层
其实大概估计一下就可以知道位数增加的时候强伪循环素数数目会急剧减少。
我们知道一个整数n是素数的概率为$1/{log(n)}$,而如果事先已经知道其末位数是1,3,7,9中的一个,那么我们知道它不是2和5的倍数,所以是素数的概率可以增加到$2.5/{log(n)}$,如果又事先知道这个整数不是3的倍数,那么是素数的概率可以增加到$15/{4log(n)}$。
所以对于所以的k位10进制强伪循环素数,我们可以构造一个最高为可以是1~9,其它k-1位都是1,3,7,9的数,这样的数有$9*4^{k-1}$个,如果我们再加上这个数不是3的倍数的条件,得到大概$6*4^{k-1}$个数。然后对于每个这样的数,通过循环移动,得到k-1个数,末位都是1,3,7,9,而且要求它们是素数才通过测试,所以通过测试的数的期望值大概在
$6*4^{k-1}*(15/{4log(n)})^{k-1}=6*(15/{log(n)})^{k-1}$,其中式子中所有的n都在$[10^{k-1},10^k]$
所以上面的概率P满足$6*(15/{klog(10)})^{k-1}<=P<=6*(15/{(k-1)log(10)})^{k-1}$,这个表达式大概为$6*(6.5/k)^{k-1}$
所以在$k>=7$时显然越来越小。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-29 11:40:00 | 显示全部楼层
上面的估计式同$k<=7$时实际搜索结果比较,可以发现仅k=6时误差比较大,这个是因为这个时候,因子7起到了特殊的作用,因为10关于7的次数正好是6,所以我们的估计公式需要乘上因子$(7/6)^{k-2}$。但是总体上趋势是没有错的,唯一的例外就是没有包含所有位数都是1的素数这个特例
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-29 13:20:25 | 显示全部楼层
那种素数至今发现的很少很少
可以不考虑
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-14 12:26:51 | 显示全部楼层
好问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-1-30 17:54:51 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-23 16:08 , Processed in 0.063341 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表