强伪循环素数

无心人

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

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