强伪循环素数

medie2005

我们称长度为k的数n是循环素数,当n按10进制向左逐次循环移位时,得到的数都是素数. 举例来说: 1193 是素数 1931 是素数 9311 是素数 3119 是素数 1193 回到开始了. 我们称长度为k的数n是强伪循环素数,当n按10进制向左逐次循环移位时,得到的数中只有一个不是素数. 例如: 9991313 是素数 9913139 是素数 9131399 是素数 1313999 是素数 3139991 是素数 1399913 是素数 3999131 = 17 * 235243 非素数 9991313 回到开始了. 能不能找出10^19内的所有强伪循环素数?

gxqcn

问题本身比较有趣，难度也不小，可否再多举几个例子？ 为什么这次把范围定到了10¹⁹ ？

medie2005

难死人才好嘛

medie2005

这个论坛本来就是追求难度,主打难度牌.

gxqcn

纯粹的难度并不是追求的目标， 而是希望在交流中把算法搞得更透彻，追求时间和空间上的极限， 合理的范围更能激发参与的热情。

无心人

我想纯粹的循环素数是极少的 记得俺高中曾经求过 反正每位数字必须是1, 3, 7, 9 如果求10位 那不过2^20个 其中还很多组合一次就淘汰

无心人

如果像楼主定到20位 其组合强度是很高的 而且这种数字是无法提前减枝的

mathe

我想到一种算法，不过还没有试验过，到底能够计算到多少位未知。 假设我们现在要计算k位强伪素数。（每个数至少代表k-1个素数） 我们将k位拆分成固定的两个部分,比如k=u+v,其中u比较小，比如u=7 然后我们限定查找的对象如果将前u位依次移到最后还都是素数(添加了这个限制后，每个数还是可能被重复搜索k-u-1次) 我们可以知道这u位数据都只能是1,3,7,9这四个之一。 现在我们需要枚举这u位情况，总共$4^u$种情况。 然后对于每一种情况，数据前u位已知，我们准备用筛选法来搜索余下的位置。 对于一个前u位已知的一个数据x,如果我们将它前t位(1<=t<=u)移动到最后，这个数据将变成 $(x-a*10^(k-t))*10^t+a$,其中a是一个已知的t位数 所以对于每个候选数，除了数据x本身以外，我们可以有u个伴随数据都可以写成$ax+b$的形式 然后对于每个小素数p,我们开始关于模p筛选 我们要求$x!=0(mod p)$,同样还有对于每个伴随数据我们要求$ax+b!=0(mod p)$,由于其中a和b都是常数，所以我们可以事先解这个同余方程，方程可以变成$x!=c(mod p)$这种形式。 所以通过这种方法，我们在筛选过程中，对于每个素数p,最多可以同时筛选u+1个同余项。 我估计对于每个模板，我们只需要使用一定量的小素数去筛选，就可以使余下没有多少数据了。接下去余下数据进行简单素数探测就可以了。

无心人

1000内素数是个不错的选择

mathe

那也应该分两次，不然$10^(20-u)$可能还是太大，内存是个问题 比如首先只用3*5*7*11*13*17去筛选。 得到x关于模3*5*7*11*13*17的可用余数（应该留下比例不高了） 然后对留下每个余下，再用更大的素数去筛选。不过这样分次筛选代码又要复杂了。