数学研发论坛

 找回密码
 欢迎注册
查看: 6621|回复: 29

[讨论] 强伪循环素数

[复制链接]
发表于 2008-4-2 21:24:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
我们称长度为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内的所有强伪循环素数?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 21:38:53 | 显示全部楼层
问题本身比较有趣,难度也不小,可否再多举几个例子?

为什么这次把范围定到了1019
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-2 21:43:10 | 显示全部楼层
难死人才好嘛
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-2 21:44:01 | 显示全部楼层
这个论坛本来就是追求难度,主打难度牌.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 22:25:37 | 显示全部楼层
纯粹的难度并不是追求的目标,
而是希望在交流中把算法搞得更透彻,追求时间和空间上的极限,
合理的范围更能激发参与的热情。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 08:01:30 | 显示全部楼层
我想纯粹的循环素数是极少的
记得俺高中曾经求过
反正每位数字必须是1, 3, 7, 9
如果求10位
那不过2^20个
其中还很多组合一次就淘汰
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 08:03:21 | 显示全部楼层
如果像楼主定到20位
其组合强度是很高的
而且这种数字是无法提前减枝的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 17:00:50 | 显示全部楼层
我想到一种算法,不过还没有试验过,到底能够计算到多少位未知。
假设我们现在要计算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个同余项。
我估计对于每个模板,我们只需要使用一定量的小素数去筛选,就可以使余下没有多少数据了。接下去余下数据进行简单素数探测就可以了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 17:13:11 | 显示全部楼层
1000内素数是个不错的选择
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 17:21:26 | 显示全部楼层
那也应该分两次,不然$10^(20-u)$可能还是太大,内存是个问题
比如首先只用3*5*7*11*13*17去筛选。
得到x关于模3*5*7*11*13*17的可用余数(应该留下比例不高了)
然后对留下每个余下,再用更大的素数去筛选。不过这样分次筛选代码又要复杂了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-12-11 11:59 , Processed in 0.057860 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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