被连续自然数取模后全为质数的最小整数

mathe

e[63]=1479414399394932002
e[64]=2690526997513555202
e[65]=2690526997513555202
e[66]=2690526997513555202
e[67]=6173829500412974402
e[68]=6173829500412974402
e[69]=6173829500412974402
e[70]=6173829500412974402
e[71]=40167003465777988802
e[72]=40167003465777988802
e[73]=68441507929450656002
e[74]=195797066175538027202
e[75]=195797066175538027202
e[76]=195797066175538027202
e[77]=195797066175538027202
e[78]=195797066175538027202
e[79]=616072054588129339202
e[80]=616072054588129339202
e[81]=616072054588129339202
e[82]=11689927965263544796802
e[83]=200413348268577717873602
e[84]=200413348268577717873602
e[85]=200413348268577717873602
e[86]=1300882803083249632646402
e[87]=1300882803083249632646402
e[88]=1300882803083249632646402
e[89]=2471436184401308960035202
e[90]=2471436184401308960035202
e[91]=2471436184401308960035202
e[92]=2471436184401308960035202
e[93]=2471436184401308960035202
e[94]=425002077871009060888065602
e[95]=425002077871009060888065602
e[96]=425002077871009060888065602
e[97]=562356157505626272053865602
e[98]=1673620390251025045311081602
e[99]=1673620390251025045311081602
e[100]=1673620390251025045311081602
e[101]=2034287189655174142001913602
e[102]=2034287189655174142001913602
e[103]=6497642650272411454440624002
e[104]=6497642650272411454440624002
e[105]=6497642650272411454440624002
e[106]=293794470445062408741351432002
e[107]=293794470445062408741351432002
e[108]=293794470445062408741351432002
e[109]=63316341740975305645497774139202
e[110]=63316341740975305645497774139202
对于63以上的计算:

1. primetest(x,n)=
   
2. {
   
3.     local(q,pass);
   
4.     pass=1;
   
5.     forprime(p=ceil(n/2),n,
   
6.         q=p;
   
7.         while(q<=n,
   
8.            if(!isprime(x%q),pass=0;break());
   
9.            q=q*p
   
10.         )
    
11.     );
    
12.     pass
    
13. }
    
14. 
    
15. getevenr(n)=
    
16. {
    
17.     local(r,mod,left,x);
    
18.     r=Mod(2,4);
    
19.     for(u=3,floor(n/2), r=chinese(r,Mod(2,2*u)));
    
20.     mod=component(r,1); left=component(r,2);
    
21.     x=left+mod;
    
22.     while(1,
    
23.       if(primetest(x,n),print("e["n"]="x);break());
    
24.       x=x+mod
    
25.     );
    
26. }
    

复制代码

.·.·.

mathe 发表于 2020-8-6 13:10
e[63]=1479414399394932002
e[64]=2690526997513555202
e[65]=2690526997513555202

我之前算到过130
131因为i128爆了需要绕过
found number=63316341740975305645497774139202 for n=111!
found number=63316341740975305645497774139202 for n=112!
found number=315317221876783126525319154360002 for n=113!
found number=315317221876783126525319154360002 for n=114!
found number=315317221876783126525319154360002 for n=115!
found number=315317221876783126525319154360002 for n=116!
found number=315317221876783126525319154360002 for n=117!
found number=359391980206726313623343310744002 for n=118!
found number=359391980206726313623343310744002 for n=119!
found number=359391980206726313623343310744002 for n=120!
found number=359391980206726313623343310744002 for n=121!
found number=173044793183066045276433017693673602 for n=122!
found number=173044793183066045276433017693673602 for n=123!
found number=173044793183066045276433017693673602 for n=124!
found number=393565946202528402313011298817520002 for n=125!
found number=393565946202528402313011298817520002 for n=126!
found number=4437387269491025869779373423874064002 for n=127!
found number=4437387269491025869779373423874064002 for n=128!
found number=4437387269491025869779373423874064002 for n=129!
found number=4437387269491025869779373423874064002 for n=130!
绕过之后可以算得
found number=26628491970767443062229473376178352002 for n=131!
found number=26628491970767443062229473376178352002 for n=132!
found number=26628491970767443062229473376178352002 for n=133!
found number=259613540181287584989772406543516304002 for n=134!
found number=259613540181287584989772406543516304002 for n=135!
found number=259613540181287584989772406543516304002 for n=136!
found number=259613540181287584989772406543516304002 for n=137!
found number=259613540181287584989772406543516304002 for n=138!
然后真的爆u128了

wayne

你们都太恐怖了。我的进度大大落后，对于$10^10$以内还行，超过了就失去了筛除的作用，内存不够用，优化不动了，代码先扔出来。

1. MAX = 10^7; n = 30;
   
2. ans = Nest[{Select[
   
3.       DeleteCases[
   
4.        Table[ChineseRemainder[p, {#[[2]], #[[3, 1]] + 1}], {p,
   
5.          Flatten[Outer[List[#1, #2] &, #[[1]],
   
6.            Prime[Range[PrimePi[NextPrime[#[[3, 1]] + 1, -1]]]]],
   
7.           1]}], _ChineseRemainder], # < MAX &],
   
8.      LCM @@ Range[3, #[[3, 1]] + 1], #[[3]] + 1} &, {{2}, 3, {3}},
   
9.    n - 3];
   
10. Sort[ans[[1]]]
    

复制代码

mathe

我的代码后面有点错误，后面应该检查所有n/2到n之间素数或素数的幂，但是素数的幂我弄错了。另外，后面应该继续用筛法会更快些

wayne

mathe 发表于 2020-8-6 17:56
我的代码后面有点错误，后面应该检查所有n/2到n之间素数或素数的幂，但是素数的幂我弄错了。另外，后面应该 ...

我的内存都不够用了。我是 每往前推进一步，就用中国剩余定理 把前面的计算候选都合并，存起来。复杂度差不多是 素数个数的累计 阶乘。你们的讨论的我还需要消化。

.·.·.

wayne 发表于 2020-8-6 18:17
我的内存都不够用了。我是 每往前推进一步，就用中国剩余定理 把前面的计算候选都合并，存起来。复杂度差 ...

我也差不多
不过我会手动中止CRT的合并过程转而挨个测试
毕竟我的内存再多也有限度

BTW，我用的并不是CRT合并，而是展开循环节后过滤
对上千万的数据执行CRT理应是很慢很慢的

wayne

我也是，我算到$n=30$的时候，候选解有几十万个，然后投机取巧，并没有继续算$n=31$，而是在$n=30$的候选解里再筛选出$n=40,50$的最小候选解。

对于给定的$n$,小于$n$的素数的个数是$p_n$，那么我的空间复杂度和时间复杂度好像 都是$\prod_{k=3}^np_k$,你们的复杂度是多少。

我感觉问题的关键是 从$n=3$开始，一直到$n=50,60,80,100,120$,这中间的计算路径的合并也罢，删除也罢，或者通过门槛值$MAX<10^20$这种过滤解，是值得优化的地方。

mathe

n<63时其实复杂度比$n>=63$的要大一些，其复杂度也更加难以估计.
原始思路是先找出一些只会余下小量合法余数的除数，然后利用它们的最小公倍数为模，关于这个模的余数也必然只有少数是合法的。
而.·.·.发现这个最小公倍数的所有素因子都会很小，于是我们干脆总是从某个只含小素因子的模，比如M=166320出发
然后我们可以对所有3到n之间的M的因子做过滤
   对于任意整数b,0<b<M
       对于3到n之间M的任意一个因子d
          如果整数集合b除以d的余数不是素数，我们可以淘汰集合$E_b$={Mx+b| x是任意整数}
  通过这样，我们可以把M-1个集合$E_b$淘汰掉大部分。接下去再在余下的集合中依次顺序搜索，那么空间复杂度会极小。
  当然后面如果对每个留下的$E_b$继续通过筛法，可能计算会更快，但是需要更大的临时空间。

而对于上面的M=166320, 当选择n=63时，发现所有的奇数b对应的集合都被删除，这说明在$n>=63$时，没有奇数解。

而对于偶数解，我们知道对于所有的偶数除数得出的余数都只能为2，这说明这个偶数解除以4,6,8,...,2[n/2] 的余数都是2
于是计算M=lcm(4,6,8,...,2[n/2]), 那么它必然是 Mx+2的形式。
同样上面的结论说明这个数除以3,4,...,[n/2]的余数也都是2，均已经不需要判断了。
同样如果对于一个n/2和n之间的奇数h它有两个互素的真因子a,b即h=ab而且(a,b)=1,而且$a,b>=3$,
那么a,b都小于n/2,所以这个数除以a的余数为2，除以b的余数也为2,所以这个数除以h的余数也必然是2，也不需要在判断了。
所以我们接下去只要判断n/2和n之间素数或素数的幂即可。
也就是对于每个Mx+2形式的数，依次除以n/2和n之间的素数或素数的幂，查看余数是否是素数，如果都通过了，结果就会通过。
这种判断方法同样空间复杂度非常小。当然后面的判断方法同样可以采用筛法来加速

.·.·.

mathe 发表于 2020-8-6 20:03
n=63$的要大一些，其复杂度也更加难以估计.
原始思路是先找出一些只会余下小量合法余数的除数，然后利用它 ...

也就是对于每个Mx+2形式的数，依次除以n/2和n之间的素数或素数的幂，查看余数是否是素数

其实这个算法略有些低效。在计算Mx+2时，x可能重复了上万甚至上千万次，而这些重复中有不少其实是多余的。

我的算法更进一步，将M扩展为BM，每BM个数字中有若干个数字，每个数字除以BM的（某个大于2小于n的约数）的余数均为素数
如果对素数p,p不整除M，那么，如果循环节为M的数列中有m个符合题意的选项可以直接推得循环节为pM的数列中有primepi(p)*m个符合题意的选项。
注意到primepi(p)/p很小，所以多次引入新素数可以筛选掉大部分不需要的结果。
这回增加很多内存占用，但会节省更多的时间。
类似的预处理可以预先筛选掉更多的数字，而之后的验证可以从一个比n/2更大的m开始，验证m~n之间的素数或素数的幂

（反正用这个方法我已经加速到n=138，再大一点u128就溢出了）

mathe

由于对于$n>=63$,我们知道结果必然形如Mx+2, 所以与其直接将M扩展为BM,然后依次判断BM内的数除以BM的因子后余数是否为素数，
我们其实只需要大小为BM/M的缓冲区，分别记录各形如Mx+2的BM以内的数除以BM的因子后余数是否都是素数。由于M很大，这可以节省很多空间
比如n=63,M=144403552893600，数字形如Mx+2,我们还需要使用37,41,43,49,53,59,61做筛选。
其中Mx+2 模37是素数共有pi(37)=12中，我们比如可以事先查看$x (\mod 37\times 41\times 43)$对于素数37,41,43的筛选结果。
于是需要一个大小为$37\times 41\times 43=65231$比特的缓冲区，其中通过的应该有$12\times13\times14=2184$种，也就是只余下3.3%的数据
如果我们继续将模49也添加进来，由于M是7的倍数，Mx+2 (mod 49)只有7种情况，所以缓冲区大小需要继续扩大到7倍，为456617比特。而通过的情况有2184*3,于是只留下1.4%的数据了。
修改了以后，搜索131在我的笔记本上，使用1M~10M内存都大概半分钟