强伪循环素数

无心人

那只可能是最高位有一个数字是
你能举一个例子么？

mathe

直接穷举所有$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

无心人

那就说明可能不如LZ的稀罕
但也是越来越少吧

mathe

使得，而且9位数就你找出来的那个解
所以用8#的算法筛到$10^19$应该问题不大。

无心人

还是神秘的127位回文素数最好求了
只要用1024 * 1024个IA64 1.2G CPU + 1024T内存
和万兆光网络连接
不到一个星期就能搜索完

特容易

mathe

其实大概估计一下就可以知道位数增加的时候强伪循环素数数目会急剧减少。
我们知道一个整数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$时显然越来越小。

mathe

上面的估计式同$k<=7$时实际搜索结果比较，可以发现仅k=6时误差比较大，这个是因为这个时候，因子7起到了特殊的作用，因为10关于7的次数正好是6，所以我们的估计公式需要乘上因子$(7/6)^{k-2}$。但是总体上趋势是没有错的，唯一的例外就是没有包含所有位数都是1的素数这个特例

无心人

那种素数至今发现的很少很少
可以不考虑

〇〇

好问题

manthanein

http://oeis.org/A068652