找回密码
 欢迎注册
查看: 20568|回复: 13

[提问] PrimeQ神奇,是否有重大bug?

[复制链接]
发表于 2019-8-18 11:38:18 | 显示全部楼层 |阅读模式

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

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

×
   据说 n=42618163402417*2^1290000 - 1是 388343位数字的素数
   用PrimeQ测试,不到1ms斩钉截铁的回答:False
   速度之快,令人称奇,"不是素数""的答案深感意外
   查 http://www.factordb.com  回答是未知
   用 HugeCalc8.0.0.0 计算器,长时间计算,没有得到答案
   n是不是素数? PrimeQ是否有重大bug? 我的代码有错误?
   
   不要求PrimeQ解决任意整数的素性测试,回答未知或得不到答案都正常
   如果给出错误答案则不该
  1.    n = 42618163402417*2^1290000 - 1;(* 略去显示整数 *)
  2.    Print["n: length="]
  3.    IntegerLength[n2]
  4.    PrimeQ[n] // AbsoluteTiming
复制代码


   n: length=
   388343
   {0.000127327, False}

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-18 12:08:07 | 显示全部楼层
很容易验证这个数不是素数
  1. Select[Prime@Range[10^5], Divisible[num, #] &]
复制代码

Output:
{3, 7, 113}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-18 12:15:21 | 显示全部楼层
本帖最后由 王守恩 于 2019-8-18 12:19 编辑

  n 是 3 的倍数。
n=42618163402417*2^1290000 - 1= n=4*2^2 - 1(mod,3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-18 14:04:46 | 显示全部楼层
即使有bug,但是这么成熟的函数,还是不可能让你发现有bug的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-18 14:13:25 | 显示全部楼层
mathematica确实有bug
比如下面的帖子,明明是两个解,结果算出来是四个解,这就是bug
https://bbs.emath.ac.cn/forum.ph ... 977&fromuid=865
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-8-18 20:00:46 | 显示全部楼层
谢谢大家的热心指正,学活不小
已找到出错原因: n数值前面因手误多了数字4
实际n= 2618163402417*2^1290000 - 1
修正后PrimeQ[n] 长时间运行,不停,(30分钟后放弃计算)虽然无法判断是否为素数,属正常,不属于bug
因子分解网站仍然不能分解,不能确定是否为素数
Result:
status (?)        digits        number
U        388342 (show)        2^1290000*2618163402417-1<388342> = 1295398183...91<388342>

有简单素性测试方法确认n是素数吗?期待!

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-19 14:11:13 | 显示全部楼层
dlpg070 发表于 2019-8-18 20:00
谢谢大家的热心指正,学活不小
已找到出错原因: n数值前面因手误多了数字4
实际n= 2618163402417*2^129000 ...

老人家,用分解的办法来判定素数太慢太慢了!
你把全宇宙的资源都消耗了,我敢说也分解不了!
只是你这个数太大了,软件算起来慢,
要是给个超级计算机,我敢说很快就能算出来!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-19 14:16:11 | 显示全部楼层
dlpg070 发表于 2019-8-18 20:00
谢谢大家的热心指正,学活不小
已找到出错原因: n数值前面因手误多了数字4
实际n= 2618163402417*2^129000 ...

https://bbs.emath.ac.cn/forum.ph ... 433&fromuid=865
这儿有个我写的miller rabin的mathematica子函数,你可以拿去用来计算一下,
但是估计算这个数也很慢!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-19 14:18:07 | 显示全部楼层
dlpg070 发表于 2019-8-18 20:00
谢谢大家的热心指正,学活不小
已找到出错原因: n数值前面因手误多了数字4
实际n= 2618163402417*2^129000 ...

https://primes.utm.edu/primes/page.php?id=121330

这个数确实是个素数,你不用折腾mathematica了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-8-19 20:29:04 | 显示全部楼层
mathematica 发表于 2019-8-19 14:18
https://primes.utm.edu/primes/page.php?id=121330

这个数确实是个素数,你不用折腾mathematica了

  谢Mathematica,所引用网页特好
  我不怀疑n=2^1290000*2618163402417-1是素数,而是关心如何做素性测试
  看来MMA有点难,但有可能.
  我为什么关心这个数?因为它是第一类CC(Cunningham_Chain)的最大素数:
  CC2, 1st kind:
  2618163402417*2^1290000-1, 388342 digits, 2016-FEB-29, Brown(PrimeGrid/TwinGen/LLR)
  后面括号内是所用工具软件,相当精彩,速度和功能都一流,求大素数必备!
  我提供其中2个:
   http://www.utm.edu/research/primes/programs/NewPGen/
   https://primes.utm.edu/programs/gallot/
   作为爱好者,我只是来欣赏这些杰作,创造新记录靠你们.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 13:40 , Processed in 0.078323 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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