郭有没有兴趣做出一个确定性的素性检测函数

mathe

由于
$p_{n+1}=2p_n+1$
我们可以有
$p_{n+1}-p_n=2(p_n-p_{n-1})=...=2^n(p_1-p_0)$
于是$p_n=(2^n-1)(p_1-p_0)+p_0=(2^n-1)(p_0+1)+p_0=2^n(p_0+1)-1$
如果2是素数P的原根，那么我们知道，上面序列长度最大P-2 ...
mathe 发表于 2010-7-8 15:50

利用$p_n=2^n(p_0+1)-1$,假设查找长度为L的序列
我们可以直接设计对应的筛法。
首先，对于特别的小素数，我们直接求解出允许的余数，特别是余数只能是-1的数字可以特殊处理。
而对于余下的数，那么对于任何素数P,如果$p_n!=P$,那么我们知道
$2^n(p_0+1)-1!=0(mod P)$,即$p_0!=2^-n-1(mod P)$,我们只要计算出2关于P的数论倒数h,然后筛除$h^0-1,h^1-1,...,h^{L-1}-1 (mod P)$
可以通过这种方法将大量较小的P(比如不超过10000)全部进行筛选，那么余下的候选数将会很少。然后可以再次逐一判断

gxqcn

$(2^10t-1)(Mod P)$未必是$2^10t-1$
mathe 发表于 2010-7-8 17:13

这句话没看明白。

我还是比较坚持昨天的“加强”说法（并且将先前2的指数加1，已在原帖修改）。

以“搜索连续长度为10以上的素数”来说，已有结论我们“需要搜索形式如2*3*5*11*k-1的素数”。
再加上 $p_n=2^n(p_0+1)-1$（注意： 我没把 $p_0$ 它作为素数序列中的一员，而是其前一个，但为整数），
即 $(2*3*5*11)|(p_10+1)$ 且 $2^10|(p_10+1)$，
所以 $(2^10*3*5*11)|(p_10+1)$
这样顺理成章即可得到加强版：“我们只需要搜索形式如2^10*3*5*11*k-1的素数”


实际上，上述结论用来检验 40# 得到的数据“13357981992959”也是成立的：

$13357981992959 = 2^11*3^2*5*11*19*61*11369 - 1$

mathe

怎样理解应该是对的。也就是说测试$p_n$而不是$p_0$.
不过搜索空间是一样的，只是素数检测先判断$p_n$而不是$p_0$

qianyb

26# 无心人


10^6内少了一组数据
[89,179,359,719,1439,2879]
10^6内其他三组6项的
[127139,254279,508559,1017119,2034239,4068479]
[405269,810539,1621079,3242159,6484319,12968639]
[810809,1621619,3243239,6486479,12972959,25945919]
漏掉的一组:63419 ,126839, 253679, 507359 ,1014719, 2029439

长度为7的一组里有一个不是素数
[164229,4328459,8656919,17313839,34627679,69255359,138510719]中的值
164229=3×13×4211

qianyb

11链的
665043081119,1330086162239,2660172324479,5320344648959,10640689297919,21281378595839,42562757191679,85125514383359,170251028766719,340502057533439,681004115066879

qianyb

12链
554688278429,1109376556859,2218753113719,4437506227439,8875012454879,17750024909759,35500049819519,71000099639039,142000199278079,284000398556159,568000797112319,1136001594224639
13链
4090932431513069,8181864863026139,16363729726052279,32727459452104559,65454918904209119,130909837808418239,261819675616836479,523639351233672959,1047278702467345919,2094557404934691839,4189114809869383679,8378229619738767359,16756459239477534719
14链
95405042230542329,190810084461084659,381620168922169319,763240337844338639,1526480675688677279,3052961351377354559,6105922702754709119,12211845405509418239,24423690811018836479,48847381622037672959,97694763244075345919,195389526488150691839,390779052976301383679,781558105952602767359

mathe

用的什么算法？这么大的范围应该是需要事先筛选一些较多的素数模了

无心人

64#不好意思，是我复制少了个数字2
应该是
[2164229,4328459,8656919,17313839,34627679,69255359,138510719]

无心人

第二组6个的我也忘记为什么漏掉了

无心人

最小的5， 6， 7链已经找到
后面的大家努力