数学研发论坛

 找回密码
 欢迎注册
查看: 360|回复: 26

[讨论] 最长素数链

[复制链接]
发表于 2019-7-5 09:42:49 | 显示全部楼层 |阅读模式

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

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

x
迭代序列 $q_{n+1}=2q_n+1$ ,要求该序列中的每一个数都是奇素数,求尽可能长的素数链

例如: (5, 11, 23, 47)
2·5+1=11,  2·11+1=23,  2·23+1=47,  2·47+1=95 ,这是首项为 5,长度为 3 的素数链.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-5 10:04:00 | 显示全部楼层
  1. NestWhileList[2#+1&, 5, PrimeQ]//Most
复制代码

out[1]={5, 11, 23, 47}
这个长度应该定义为 4 吧?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-5 12:15:35 | 显示全部楼层
记得当年搜到过9个的
思路是借助同余进行搜索
不管mod几,$q_{n+1}=2q_n+1$最终会收敛到一个不动点
然后用这个不动点进行搜索,可以省很多力气
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-5 12:57:28 | 显示全部楼层
容易看出末尾不是9的必然长度不超过5,所以只要判断末尾为9的情况,比如
89, 179, 359, 719,1439,2879
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-5 13:06:53 | 显示全部楼层
长度为6的有
63419 126839 253679 507359 1014719 2029439
长度为7的有
1122659 2245319 4490639 8981279 17962559 35925119 71850239
长度为8的有
19099919 38199839 76399679 152799359 305598719 611197439 1222394879 2444789759
长度为9的有
85864769 171729539 343459079 686918159 1373836319 2747672639 5495345279 10990690559 21981381119
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-5 13:15:41 | 显示全部楼层
长度为10的有
65639153579 131278307159 262556614319 525113228639 1050226457279 2100452914559 4200905829119 8401811658239 16803623316479 33607246632959
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-7-5 13:30:43 | 显示全部楼层
还有这个呢  $ q_{n+1}=2q_n-1$

如果是加一和减一相互交错呢

点评

不管是啥,都应该是先用同余筛一遍的吧……BTW,$2q_n+1$可以看成是safe prime(不易被p-1 method分解),$2q_n-1$是什么意思?  发表于 2019-7-5 17:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-5 21:29:34 | 显示全部楼层
受mathe的数据鼓舞,给出更多些数据,供参考
长度等于6:
        1                 {89,179,359,719,1439,2879}
        2                 {63419,126839,253679,507359,1014719,2029439}
        3                 {127139,254279,508559,1017119,2034239,4068479}
        4                 {405269,810539,1621079,3242159,6484319,12968639}
        5                 {810809,1621619,3243239,6486479,12972959,25945919}
        6                 {1069199,2138399,4276799,8553599,17107199,34214399}
        7                 {1122659,2245319,4490639,8981279,17962559,35925119}
        8                 {1178609,2357219,4714439,9428879,18857759,37715519}

长度等于7:
       
        1                 {1122659,2245319,4490639,8981279,17962559,35925119,71850239}
        2                 {2164229,4328459,8656919,17313839,34627679,69255359,138510719}
        3                 {2329469,4658939,9317879,18635759,37271519,74543039,149086079}
        4                 {10257809,20515619,41031239,82062479,164124959,328249919,656499839}
        5                 {10309889,20619779,41239559,82479119,164958239,329916479,659832959}
        6                 {12314699,24629399,49258799,98517599,197035199,394070399,788140799}
        7                 {14030309,28060619,56121239,112242479,224484959,448969919,897939839}
        8                 {14145539,28291079,56582159,113164319,226328639,452657279,905314559}

长度等于8:
没取模  {61.1721, {19099919, 52554569, 85864769, 171729539}} 耗时 61.1721秒
取模优化{44.1752, {19099919, 52554569, 85864769, 171729539}} 耗时 44.1752秒
1                 {19099919,38199839,76399679,152799359,305598719,611197439,1222394879,2444789759}
2                 {52554569,105109139,210218279,420436559,840873119,1681746239,3363492479,6726984959}
3                 {85864769,171729539,343459079,686918159,1373836319,2747672639,5495345279,10990690559}
4                 {171729539,343459079,686918159,1373836319,2747672639,5495345279,10990690559,21981381119}

长度等于9: 耗时 317.779秒
1                 {85864769,171729539,343459079,686918159,1373836319,2747672639,5495345279,10990690559,21981381119}
2                 {198479579,396959159,793918319,1587836639,3175673279,6351346559,12702693119,25405386239,50810772479}
3                 {305192579,610385159,1220770319,2441540639,4883081279,9766162559,19532325119,39064650239,78129300479}

10:

我的代码太丑:
1 长度<10 都可以得到多个给定长度的素数链
2 每增加1个迭代次数,运算时间增加10倍以上,10以上计算太耗时了
3 取模优化作用不明显
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-6 13:27:06 | 显示全部楼层
这要用筛选法加速,预先淘汰更多的可能。
若干各连续的这类数可以写成$q_h=2^h*(q_0+1)-1$
于是对于任意小素数p,我们要求$(q_0+1) != 2^{-h} (mod p), h=0,1,2,...,H-1$
所以对于$p<=H+1$时,只能要求$p|q_0+1$,而对于略大的p,这种方法也能预先淘汰掉大量的候选数。
比如一个简单的pari/gp代码可以得到:
n=2*3*5*7*11
getlen(x)={if(isprime(x), getlen(2*x+1)+1,0)}
for(x=1,10000000000, y=n*x-1;if(getlen(y)>=10, print(y" "getlen(y))))
65639153579 10
372339715439 10
570901515029 10
721438465439 10
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-6 13:37:36 来自手机 | 显示全部楼层
由于2可能不是某些素数原根(比如7),所以上述gp代码可能会漏解。但是如果不追求最小解,上面代码还是比较间接方便的。甚至我们还可以添加更多的额外素数增加搜索速度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-7-18 17:18 , Processed in 0.051140 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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