e=1479414399394932002
e=2690526997513555202
e=2690526997513555202
e=2690526997513555202
e=6173829500412974402
e=6173829500412974402
e=6173829500412974402
e=6173829500412974402
e=40167003465777988802
e=40167003465777988802
e=68441507929450656002
e=195797066175538027202
e=195797066175538027202
e=195797066175538027202
e=195797066175538027202
e=195797066175538027202
e=616072054588129339202
e=616072054588129339202
e=616072054588129339202
e=11689927965263544796802
e=200413348268577717873602
e=200413348268577717873602
e=200413348268577717873602
e=1300882803083249632646402
e=1300882803083249632646402
e=1300882803083249632646402
e=2471436184401308960035202
e=2471436184401308960035202
e=2471436184401308960035202
e=2471436184401308960035202
e=2471436184401308960035202
e=425002077871009060888065602
e=425002077871009060888065602
e=425002077871009060888065602
e=562356157505626272053865602
e=1673620390251025045311081602
e=1673620390251025045311081602
e=1673620390251025045311081602
e=2034287189655174142001913602
e=2034287189655174142001913602
e=6497642650272411454440624002
e=6497642650272411454440624002
e=6497642650272411454440624002
e=293794470445062408741351432002
e=293794470445062408741351432002
e=293794470445062408741351432002
e=63316341740975305645497774139202
e=63316341740975305645497774139202
对于63以上的计算:
primetest(x,n)=
{
local(q,pass);
pass=1;
forprime(p=ceil(n/2),n,
q=p;
while(q<=n,
if(!isprime(x%q),pass=0;break());
q=q*p
)
);
pass
}
getevenr(n)=
{
local(r,mod,left,x);
r=Mod(2,4);
for(u=3,floor(n/2), r=chinese(r,Mod(2,2*u)));
mod=component(r,1); left=component(r,2);
x=left+mod;
while(1,
if(primetest(x,n),print("e["n"]="x);break());
x=x+mod
);
}
本帖最后由 .·.·. 于 2020-8-6 17:07 编辑
mathe 发表于 2020-8-6 13:10
e=1479414399394932002
e=2690526997513555202
e=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了
你们都太恐怖了。我的进度大大落后，对于$10^10$以内还行，超过了就失去了筛除的作用，内存不够用，优化不动了，代码先扔出来。
MAX = 10^7; n = 30;
ans = Nest[{Select[
DeleteCases[
Table], #[] + 1}], {p,
Flatten &, #[],
Prime] + 1, -1]]]]],
1]}], _ChineseRemainder], # < MAX &],
LCM @@ Range] + 1], #[] + 1} &, {{2}, 3, {3}},
n - 3];
Sort]]
我的代码后面有点错误，后面应该检查所有n/2到n之间素数或素数的幂，但是素数的幂我弄错了。另外，后面应该继续用筛法会更快些
mathe 发表于 2020-8-6 17:56
我的代码后面有点错误，后面应该检查所有n/2到n之间素数或素数的幂，但是素数的幂我弄错了。另外，后面应该 ...
我的内存都不够用了。我是 每往前推进一步，就用中国剩余定理 把前面的计算候选都合并，存起来。复杂度差不多是 素数个数的累计 阶乘。你们的讨论的我还需要消化。
本帖最后由 .·.·. 于 2020-8-6 18:41 编辑
wayne 发表于 2020-8-6 18:17
我的内存都不够用了。我是 每往前推进一步，就用中国剩余定理 把前面的计算候选都合并，存起来。复杂度差 ...
我也差不多
不过我会手动中止CRT的合并过程转而挨个测试
毕竟我的内存再多也有限度
BTW，我用的并不是CRT合并，而是展开循环节后过滤
对上千万的数据执行CRT理应是很慢很慢的
我也是，我算到$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$这种过滤解，是值得优化的地方。
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 的余数都是2
于是计算M=lcm(4,6,8,...,2), 那么它必然是 Mx+2的形式。
同样上面的结论说明这个数除以3,4,...,的余数也都是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之间的素数或素数的幂，查看余数是否是素数，如果都通过了，结果就会通过。
这种判断方法同样空间复杂度非常小。当然后面的判断方法同样可以采用筛法来加速
本帖最后由 .·.·. 于 2020-8-7 00:27 编辑
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就溢出了）
由于对于$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内存都大概半分钟