数学研发论坛

 找回密码
 欢迎注册
楼主: winxos

[猜想] 10^n+1素数问题

[复制链接]
发表于 2009-8-28 09:28:13 | 显示全部楼层
记录学习
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-28 11:16:08 | 显示全部楼层
我调用 HugeCalc 编程得到如下结论:

$N=10^r+1$ 在 $0<=r<=2^15$ 范围内,仅有 r=1 和 r=2 使 N 为素数;

考察 $N=n^(2^r)+1\quad(2<=n<1024, 0<=r<10)$ 中为素数的情况:
  • 素数数目最多的是n=2时,它有5个:r=0, 1, 2, 3, 4;
  • 素数数目达到4个的有:n=4, 156, 306, 430, 562, 690;
  • r=9时,有n=46;
  • r=8时,对应有n=278, 614, 892, 898;
  • r=7时,对应有n=120, 190, 234, 506, 532, 548, 960;
  • r=6时,对应有n=102, 162, 274, 300, 412, 562, 592, 728
推荐

P[n^(2^r)p1].zip

1.73 KB, 下载次数: 2, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

售价: 1 枚金币  [记录]

搜索 n^(2^r)+1 为素数的原始数据

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-28 11:30:07 | 显示全部楼层

一个新的问题

在上述结论中,r=9 的仅有 n=46 一个数,我后来检验了其对应的 r=10,11,12,13 均非素数。

请问:让 $n^(2^r)+1\quad(n,r in ZZ)$ 为素数的 r 可有上限?

悬赏:找出一个使 $n^(2^r)+1\quad(n,r in ZZ)$ 为素数的 $(n,r)$ 组合,但要求 $r>=10$,将额外奖励100枚金币!
(注:第一份悬赏奖励已给 21# wayne
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-28 14:12:49 | 显示全部楼层
Lucas's Primality Test With Factored N-1
n-1 tests and Pepin's Test for Fermats
mathe 发表于 2009-8-28 05:30

看了第一个的内容,怎么刚好和素数循环节求法一样。
前段时间写了个求循环数的程序,做法是先将P-1分解,然后利用mathe以前告诉我的$10^n-=1 (mod p)$的性质,将因子当做n从小往大算,第一个%=1 的就是循环节位数了,发现速度还是非常的快啊。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-28 14:15:06 | 显示全部楼层
根据第二个链接的定理2,对于$P=10^{2^k}+1$,只要找到一个数a,使得
$a^{P-1}-=1(mod P)$,
$gcd(a^{(P-1)/5}-1","P)=1$
那么P是素数.
mathe 发表于 2009-8-28 05:44

我直接用的GMP的素性测试来做的,不过数大了也非常慢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-28 14:43:25 | 显示全部楼层
我直接用的GMP的素性测试来做的,不过数大了也非常慢。
winxos 发表于 2009-8-28 14:15

主要是数字大了计算模幂就很慢.
不过上面这个结论最大的好处就是如果找到了一个伪素数,通常可以很快的确定是否是真正的素数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-29 01:44:25 | 显示全部楼层
在上述结论中,r=9 的仅有 n=46 一个数,我后来检验了其对应的 r=10,11,12,13 均非素数。

请问:让 $n^(2^r)+1\quad(n,r in ZZ)$ 为素数的 r 可有上限?

悬赏:找出一个使 $n^(2^r)+1\quad(n,r in ZZ)$ 为素 ...
gxqcn 发表于 2009-8-28 11:30

看来这个悬赏老大应该差不多算了比较大的范围吧,
我测了r=10时候,200以内无解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-9-8 21:35:38 | 显示全部楼层
好像有一个新的素数判定算法。
一个数满足十三个方程,则它是素数。
http://www.irgoc.org/Article/ShowArticle.asp?ArticleID=85
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-9-8 21:53:55 | 显示全部楼层
那不是13个方程,而是13行伪代码。
这是网上广为流传的由三个印度数学家发现的素数确定性判定算法,其算法复杂度比先前的要低。

但针对某些特殊数字,
可以有更快的判定算法(一样是确定性判定),
比如对 Mersenne number 可以用 Lucas-Lehmer Test 快速判定。

另,恭喜LS荣获“优秀新人奖”勋章!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-9-8 23:15:03 | 显示全部楼层
我调用 HugeCalc 编程得到如下结论:

$N=10^r+1$ 在 $0
gxqcn 发表于 2009-8-28 11:16


搜到了很多这样的广义费尔马素数
$70906^(2^15)+1$,$167176^(2^15)+1$,......

链接:
http://pagesperso-orange.fr/yves.gallot/primes/index.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-11-22 11:03 , Processed in 0.074453 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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