139 (1m30s)
4188696294935413706934768125377042512002
140(1m37s)
4188696294935413706934768125377042512002
141(1m36s)
4188696294935413706934768125377042512002
142(23s)
71375535419096138855747944430720887776002
143(23s)
71375535419096138855747944430720887776002
144(25s)
71375535419096138855747944430720887776002
145(26s)
71375535419096138855747944430720887776002
146(0.6s)
71375535419096138855747944430720887776002
147(0.6s)
71375535419096138855747944430720887776002
148(0.6s)
71375535419096138855747944430720887776002
149(0.6s)
71375535419096138855747944430720887776002
150(0.6s)
71375535419096138855747944430720887776002
151(2m24s)
28466105341303483745606123156025578668368002
152(2m19s)
28466105341303483745606123156025578668368002
153~156
28466105341303483745606123156025578668368002
157
81849859751405924059843476855289279826496002
158~162
746294017377509464097706103446488143037568002
163~165
33635406647457932883180477167488271261164992002
166
154918018148228242519886464835636651505317472002
167~168
299084197184085790849033982186295000595719696002
169~172
3531371825353917671492584999407565716875889792002
173
116810701936766586361368933161051719437728630688002
本帖最后由 .·.·. 于 2020-8-9 09:48 编辑
mathe 发表于 2020-8-8 17:20
153~156
28466105341303483745606123156025578668368002
157
00:46:49> g=(a,b,c)->d=a*2^128+b*2^64+c;for(i=3,900,if(!isprime(d%i),print(i);break));d
%21 = (a,b,c)->d=a*2^128+b*2^64+c;for(i=3,900,if(!isprime(d%i),print(i);break));d
00:47:01> g(1040147161867, 7560342529706118980, 11446842006473251970)
179
%22 = 353943738186338730051340043852386052151622936272002
00:47:03> g(343275800605, 11767202774273793771, 15199516501634173186)
178
%23 = 116810701936766586361368933161051719437728630688002
(BigUInt=g)
01:40:11> BigUInt(336184657781948, 13060152521397031879, 17401726287141301250)
193
%57 = 114397711072547200623926739913773332504663121492864002
01:40:22> BigUInt(76640775490436, 17224944753369267051, 5535650887625968770)
191
%58 = 26079504486542128214527139484976208504732884352208002
01:40:27> BigUInt(21921671246381, 11662777460910458884, 7012004375286606722)
181
%59 = 7459558178581420991908368303782280420035186413104002
(194:)655569072883475643276379698332630870445125049195696002(code is incorrect thus do not generate the BigUInt form.)
01:40:35> BigUInt(21550470068748838, 14667185391198351420, 18069870029154129154)
197
%60 = 7333244963252694316979523001920058246398799258689312002
01:43:43> BigUInt(49238389357311262, 5374406407451916197, 11540656834366258178)
199
%61 = 16754955673880622369079802324257242816195831706070400002
01:48:23> BigUInt(3649368858081476934, 14762377635946019554, 17114688005815144834)
206
%68 = 1241815872795527340920909004524886711949273374627222000002
02:23:53> BigU256=(a,b,c,d)->e=a*2^192+b*2^128+c*2^64+d;for(i=3,900,if(!isprime(e%i),print(i);break));e
%102 = (a,b,c,d)->e=a*2^192+b*2^128+c*2^64+d;for(i=3,900,if(!isprime(e%i),print(i);break));e
02:24:15> BigU256(11, 9338117007605686109, 5914508867865278435, 9449427700573572482)
211
%103 = 72225715647186222395152227158525640349057726424522471280002
02:24:25> BigU256(13, 11922583201728322026, 11442997097915309871, 16504593912194840962)
214
%104 = 85659367391722784092607464197468049651961443566063782640002
02:24:34> BigU256(5045, 14915641366288941122, 12556338656733202238, 1357278714895837442)
218
%105 = 31673053784774069114917859005213870009008990233082429871008002
02:32:50> BigU256(105642, 4594879267310787348, 12542645452379590053, 6593728445292498434)
223
%107 = 663127145086112525715369034835863236326107289562909156940992002
02:33:13> BigU256(324382, 16707202402379446201, 2441149314094187990, 17344994933329711234)
226
%108 = 2036184500294580388401873354629853515994924364902165172748112002
02:35:06> BigU256(29594670, 3914874787019208054, 5083363177805329805, 9126329000077058178)
233
%111 = 185768755747358998327069097333443876936859437235420585132525904002
02:38:55> BigU256(769192496, 13818213026569080142, 10363200697496292489, 12843986744144596610)
242
%115 = 4828299556190106737188708726420164405880642740182586600077808144002
09:38:56> BigU256(229247836159, 2678296511289632618, 6941544924194096003, 919448886373386882)
251
%2 = 1439011990188211741334841754244394476887612560371605459101394720656002
(Pinyin IME is broken.. cannot type Pinyin, sorry..)
$ rustc main.rs -O && time ./main
i=87,len=12,rep=BigUInt(33, 17315042437149894138, 5041259723618722944)
i=88,len=12,rep=BigUInt(33, 17315042437149894138, 5041259723618722944)
i=89,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=90,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=91,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=92,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=93,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=94,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=95,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=96,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=97,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=98,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=99,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=100,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=101,len=165600,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=102,len=165600,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=103,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=104,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=105,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=106,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=107,len=116251200,rep=BigUInt(326135958006, 4044531529505551460, 1818271812586827904)
break at i=107,TO=108
SHOULD check `TO` and `i` carefully!
loop0 finished
found number= BigUInt(343275800605, 11767202774273793771, 15199516501634173186) for n<178!
loop1 finished
loop2 finished
found number= BigUInt(1040147161867, 7560342529706118980, 11446842006473251970) for n<179!
real 0m20.571s
user 0m20.024s
sys 0m0.546s
#!
/*
LENGTH=500
a=*(LENGTH+1)
a=a=False
for i in range(2,LENGTH+1):
if a:
for j in range(2,(LENGTH//i)+1):
a=False
print(("const ISPRIME:= "%(LENGTH+1))+str(a).lower().replace(" ","")+";")
aa=
for i in :
j=i*i;
while j<=LENGTH:
aa=True
j*=i
for i in range(1,200):
aa=True
#for u32
print("\n".join(["N=>(self.5%N+N1*(self.4%N)+N2*(self.3%N)+N3*(self.2%N)+N4*(self.1%N)+N5*(self.0%N))%N,".replace("N5",str(2**(32*5)%n)).replace("N4",str(2**(32*4)%n)).replace("N3",str(2**(32*3)%n)).replace("N2",str(2**(32*2)%n)).replace("N1",str(2**32%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
#for u64 array
print("\n".join([" N=>(N2*((self.0)%N)+N1*((self.0)%N)+(self.0)%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
#for u64
print("\n".join([" N=>(N2*(self.0%N)+N1*(self.1%N)+self.2%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
print("\n".join([" N=>(N3*(self.0%N)+N2*(self.1%N)+N1*(self.2%N)+self.3%N)%N,".replace("N3",str(2**(64*3)%n)).replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
*/
const ISPRIME:= ;
const UPPER:u32=173;
const HALF:u32=(UPPER>>1)+1;
const TO:u32=108;
fn main(){
let mut lcm=BigUInt(0,0,2);
for i in 3..HALF{
lcm=lcm.mul((i/gcd(i,lcm)) as u128)
}
let mut x=(vec!,lcm);
//x=search_roll(x.0,81,x.1);//3
//x=search_roll(x.0,49,x.1);//7
x=search_roll(x.0,121,x.1);//11
x=search_roll(x.0,125,x.1);//2
x=search_roll(x.0,128,x.1);//5
x=search_roll(x.0,169,x.1);//13
//x=search_roll(x.0,243,x.1);//3
//x=search_roll(x.0,289,x.1);//17
//x=search_roll(x.0,343,x.1);//7
for i in HALF..=TO{
x=search_roll(x.0,i,x.1);
println!("i={},len={},rep={:?}",i,(x.0).len(),x.1);
if (x.0).len()>10000000{println!("break at i={},TO={}",i,TO);break}
}
println!("SHOULD check `TO` and `i` carefully!");
let (mut b,lcm)=x;
b.sort_unstable();
let mut upper=search_once(&b,167);
for i in 0..3{
println!("loop{} finished",i);
b.iter_mut().for_each(|x|*x=x.add(lcm));
upper=search_once(&b,upper);
}
}
#
struct BigUInt(u64,u64,u64);
impl BigUInt{
#
pub fn add(self,other:Self)->Self{
//self+other
let l0=self.2 as u128+ other.2 as u128;
let (l0,g)=(l0 as u64,l0>>64);
let l1=self.1 as u128+g+other.1 as u128;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(self.0+g as u64+other.0 as u64,l1,l0)
}
#
pub fn expand(self,other:Self,b:u128)->Self{
//self+other*b
let l0=self.2 as u128+(other.2 as u128)*b;
let (l0,g)=(l0 as u64,l0>>64);
let l1=self.1 as u128+g+(other.1 as u128)*b;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(self.0+g as u64+other.0*b as u64,l1,l0)
}
#
pub fn mul(self,b:u128)->Self{
//self*b
let l0=(self.2 as u128)*b;
let (l0,g)=(l0 as u64,l0>>64);
let l1=g+(self.1 as u128)*b;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(g as u64+self.0*b as u64,l1,l0)
}
#
pub fn rem(self,b:u32)->usize{//match(x){...N=>t%N,...}is much faster than t%x if N is a constant.
(match b{
1=>0,
2=>(0*(self.0%2)+0*(self.1%2)+self.2%2)%2,
3=>(1*(self.0%3)+1*(self.1%3)+self.2%3)%3,
4=>(0*(self.0%4)+0*(self.1%4)+self.2%4)%4,
5=>(1*(self.0%5)+1*(self.1%5)+self.2%5)%5,
6=>(4*(self.0%6)+4*(self.1%6)+self.2%6)%6,
7=>(4*(self.0%7)+2*(self.1%7)+self.2%7)%7,
8=>(0*(self.0%8)+0*(self.1%8)+self.2%8)%8,
9=>(4*(self.0%9)+7*(self.1%9)+self.2%9)%9,
10=>(6*(self.0%10)+6*(self.1%10)+self.2%10)%10,
11=>(3*(self.0%11)+5*(self.1%11)+self.2%11)%11,
12=>(4*(self.0%12)+4*(self.1%12)+self.2%12)%12,
13=>(9*(self.0%13)+3*(self.1%13)+self.2%13)%13,
14=>(4*(self.0%14)+2*(self.1%14)+self.2%14)%14,
15=>(1*(self.0%15)+1*(self.1%15)+self.2%15)%15,
16=>(0*(self.0%16)+0*(self.1%16)+self.2%16)%16,
17=>(1*(self.0%17)+1*(self.1%17)+self.2%17)%17,
18=>(4*(self.0%18)+16*(self.1%18)+self.2%18)%18,
19=>(4*(self.0%19)+17*(self.1%19)+self.2%19)%19,
20=>(16*(self.0%20)+16*(self.1%20)+self.2%20)%20,
21=>(4*(self.0%21)+16*(self.1%21)+self.2%21)%21,
22=>(14*(self.0%22)+16*(self.1%22)+self.2%22)%22,
23=>(13*(self.0%23)+6*(self.1%23)+self.2%23)%23,
24=>(16*(self.0%24)+16*(self.1%24)+self.2%24)%24,
25=>(6*(self.0%25)+16*(self.1%25)+self.2%25)%25,
26=>(22*(self.0%26)+16*(self.1%26)+self.2%26)%26,
27=>(4*(self.0%27)+25*(self.1%27)+self.2%27)%27,
28=>(4*(self.0%28)+16*(self.1%28)+self.2%28)%28,
29=>(25*(self.0%29)+24*(self.1%29)+self.2%29)%29,
30=>(16*(self.0%30)+16*(self.1%30)+self.2%30)%30,
31=>(8*(self.0%31)+16*(self.1%31)+self.2%31)%31,
32=>(0*(self.0%32)+0*(self.1%32)+self.2%32)%32,
33=>(25*(self.0%33)+16*(self.1%33)+self.2%33)%33,
34=>(18*(self.0%34)+18*(self.1%34)+self.2%34)%34,
35=>(11*(self.0%35)+16*(self.1%35)+self.2%35)%35,
36=>(4*(self.0%36)+16*(self.1%36)+self.2%36)%36,
37=>(33*(self.0%37)+12*(self.1%37)+self.2%37)%37,
38=>(4*(self.0%38)+36*(self.1%38)+self.2%38)%38,
39=>(22*(self.0%39)+16*(self.1%39)+self.2%39)%39,
40=>(16*(self.0%40)+16*(self.1%40)+self.2%40)%40,
41=>(10*(self.0%41)+16*(self.1%41)+self.2%41)%41,
42=>(4*(self.0%42)+16*(self.1%42)+self.2%42)%42,
43=>(4*(self.0%43)+41*(self.1%43)+self.2%43)%43,
44=>(36*(self.0%44)+16*(self.1%44)+self.2%44)%44,
45=>(31*(self.0%45)+16*(self.1%45)+self.2%45)%45,
46=>(36*(self.0%46)+6*(self.1%46)+self.2%46)%46,
47=>(14*(self.0%47)+25*(self.1%47)+self.2%47)%47,
48=>(16*(self.0%48)+16*(self.1%48)+self.2%48)%48,
49=>(4*(self.0%49)+2*(self.1%49)+self.2%49)%49,
50=>(6*(self.0%50)+16*(self.1%50)+self.2%50)%50,
51=>(1*(self.0%51)+1*(self.1%51)+self.2%51)%51,
52=>(48*(self.0%52)+16*(self.1%52)+self.2%52)%52,
53=>(13*(self.0%53)+15*(self.1%53)+self.2%53)%53,
54=>(4*(self.0%54)+52*(self.1%54)+self.2%54)%54,
55=>(36*(self.0%55)+16*(self.1%55)+self.2%55)%55,
56=>(32*(self.0%56)+16*(self.1%56)+self.2%56)%56,
57=>(4*(self.0%57)+55*(self.1%57)+self.2%57)%57,
58=>(54*(self.0%58)+24*(self.1%58)+self.2%58)%58,
59=>(25*(self.0%59)+5*(self.1%59)+self.2%59)%59,
60=>(16*(self.0%60)+16*(self.1%60)+self.2%60)%60,
61=>(12*(self.0%61)+16*(self.1%61)+self.2%61)%61,
62=>(8*(self.0%62)+16*(self.1%62)+self.2%62)%62,
63=>(4*(self.0%63)+16*(self.1%63)+self.2%63)%63,
64=>(0*(self.0%64)+0*(self.1%64)+self.2%64)%64,
65=>(61*(self.0%65)+16*(self.1%65)+self.2%65)%65,
66=>(58*(self.0%66)+16*(self.1%66)+self.2%66)%66,
67=>(21*(self.0%67)+17*(self.1%67)+self.2%67)%67,
68=>(52*(self.0%68)+52*(self.1%68)+self.2%68)%68,
69=>(13*(self.0%69)+52*(self.1%69)+self.2%69)%69,
70=>(46*(self.0%70)+16*(self.1%70)+self.2%70)%70,
71=>(29*(self.0%71)+10*(self.1%71)+self.2%71)%71,
72=>(40*(self.0%72)+16*(self.1%72)+self.2%72)%72,
73=>(4*(self.0%73)+2*(self.1%73)+self.2%73)%73,
74=>(70*(self.0%74)+12*(self.1%74)+self.2%74)%74,
75=>(31*(self.0%75)+16*(self.1%75)+self.2%75)%75,
76=>(4*(self.0%76)+36*(self.1%76)+self.2%76)%76,
77=>(25*(self.0%77)+16*(self.1%77)+self.2%77)%77,
78=>(22*(self.0%78)+16*(self.1%78)+self.2%78)%78,
79=>(73*(self.0%79)+51*(self.1%79)+self.2%79)%79,
80=>(16*(self.0%80)+16*(self.1%80)+self.2%80)%80,
81=>(31*(self.0%81)+52*(self.1%81)+self.2%81)%81,
82=>(10*(self.0%82)+16*(self.1%82)+self.2%82)%82,
83=>(51*(self.0%83)+36*(self.1%83)+self.2%83)%83,
84=>(4*(self.0%84)+16*(self.1%84)+self.2%84)%84,
85=>(1*(self.0%85)+1*(self.1%85)+self.2%85)%85,
86=>(4*(self.0%86)+84*(self.1%86)+self.2%86)%86,
87=>(25*(self.0%87)+82*(self.1%87)+self.2%87)%87,
88=>(80*(self.0%88)+16*(self.1%88)+self.2%88)%88,
89=>(39*(self.0%89)+67*(self.1%89)+self.2%89)%89,
90=>(76*(self.0%90)+16*(self.1%90)+self.2%90)%90,
91=>(74*(self.0%91)+16*(self.1%91)+self.2%91)%91,
92=>(36*(self.0%92)+52*(self.1%92)+self.2%92)%92,
93=>(70*(self.0%93)+16*(self.1%93)+self.2%93)%93,
94=>(14*(self.0%94)+72*(self.1%94)+self.2%94)%94,
95=>(61*(self.0%95)+36*(self.1%95)+self.2%95)%95,
96=>(64*(self.0%96)+64*(self.1%96)+self.2%96)%96,
97=>(35*(self.0%97)+61*(self.1%97)+self.2%97)%97,
98=>(4*(self.0%98)+2*(self.1%98)+self.2%98)%98,
99=>(58*(self.0%99)+16*(self.1%99)+self.2%99)%99,
100=>(56*(self.0%100)+16*(self.1%100)+self.2%100)%100,
101=>(80*(self.0%101)+79*(self.1%101)+self.2%101)%101,
102=>(52*(self.0%102)+52*(self.1%102)+self.2%102)%102,
103=>(38*(self.0%103)+55*(self.1%103)+self.2%103)%103,
104=>(48*(self.0%104)+16*(self.1%104)+self.2%104)%104,
105=>(46*(self.0%105)+16*(self.1%105)+self.2%105)%105,
106=>(66*(self.0%106)+68*(self.1%106)+self.2%106)%106,
107=>(11*(self.0%107)+92*(self.1%107)+self.2%107)%107,
108=>(4*(self.0%108)+52*(self.1%108)+self.2%108)%108,
109=>(105*(self.0%109)+66*(self.1%109)+self.2%109)%109,
110=>(36*(self.0%110)+16*(self.1%110)+self.2%110)%110,
111=>(70*(self.0%111)+49*(self.1%111)+self.2%111)%111,
112=>(32*(self.0%112)+16*(self.1%112)+self.2%112)%112,
113=>(109*(self.0%113)+30*(self.1%113)+self.2%113)%113,
114=>(4*(self.0%114)+112*(self.1%114)+self.2%114)%114,
115=>(36*(self.0%115)+6*(self.1%115)+self.2%115)%115,
116=>(112*(self.0%116)+24*(self.1%116)+self.2%116)%116,
117=>(22*(self.0%117)+16*(self.1%117)+self.2%117)%117,
118=>(84*(self.0%118)+64*(self.1%118)+self.2%118)%118,
119=>(18*(self.0%119)+86*(self.1%119)+self.2%119)%119,
120=>(16*(self.0%120)+16*(self.1%120)+self.2%120)%120,
121=>(58*(self.0%121)+93*(self.1%121)+self.2%121)%121,
122=>(12*(self.0%122)+16*(self.1%122)+self.2%122)%122,
123=>(10*(self.0%123)+16*(self.1%123)+self.2%123)%123,
124=>(8*(self.0%124)+16*(self.1%124)+self.2%124)%124,
125=>(81*(self.0%125)+116*(self.1%125)+self.2%125)%125,
126=>(4*(self.0%126)+16*(self.1%126)+self.2%126)%126,
127=>(4*(self.0%127)+2*(self.1%127)+self.2%127)%127,
128=>(0*(self.0%128)+0*(self.1%128)+self.2%128)%128,
129=>(4*(self.0%129)+127*(self.1%129)+self.2%129)%129,
130=>(126*(self.0%130)+16*(self.1%130)+self.2%130)%130,
131=>(33*(self.0%131)+65*(self.1%131)+self.2%131)%131,
132=>(124*(self.0%132)+16*(self.1%132)+self.2%132)%132,
133=>(4*(self.0%133)+93*(self.1%133)+self.2%133)%133,
134=>(88*(self.0%134)+84*(self.1%134)+self.2%134)%134,
135=>(31*(self.0%135)+106*(self.1%135)+self.2%135)%135,
136=>(120*(self.0%136)+120*(self.1%136)+self.2%136)%136,
137=>(38*(self.0%137)+60*(self.1%137)+self.2%137)%137,
138=>(82*(self.0%138)+52*(self.1%138)+self.2%138)%138,
139=>(30*(self.0%139)+13*(self.1%139)+self.2%139)%139,
140=>(116*(self.0%140)+16*(self.1%140)+self.2%140)%140,
141=>(61*(self.0%141)+25*(self.1%141)+self.2%141)%141,
142=>(100*(self.0%142)+10*(self.1%142)+self.2%142)%142,
143=>(113*(self.0%143)+16*(self.1%143)+self.2%143)%143,
144=>(112*(self.0%144)+16*(self.1%144)+self.2%144)%144,
145=>(141*(self.0%145)+111*(self.1%145)+self.2%145)%145,
146=>(4*(self.0%146)+2*(self.1%146)+self.2%146)%146,
147=>(4*(self.0%147)+100*(self.1%147)+self.2%147)%147,
148=>(144*(self.0%148)+12*(self.1%148)+self.2%148)%148,
149=>(123*(self.0%149)+102*(self.1%149)+self.2%149)%149,
150=>(106*(self.0%150)+16*(self.1%150)+self.2%150)%150,
151=>(105*(self.0%151)+16*(self.1%151)+self.2%151)%151,
152=>(80*(self.0%152)+112*(self.1%152)+self.2%152)%152,
153=>(103*(self.0%153)+52*(self.1%153)+self.2%153)%153,
154=>(102*(self.0%154)+16*(self.1%154)+self.2%154)%154,
155=>(101*(self.0%155)+16*(self.1%155)+self.2%155)%155,
156=>(100*(self.0%156)+16*(self.1%156)+self.2%156)%156,
157=>(39*(self.0%157)+14*(self.1%157)+self.2%157)%157,
158=>(152*(self.0%158)+130*(self.1%158)+self.2%158)%158,
159=>(13*(self.0%159)+121*(self.1%159)+self.2%159)%159,
160=>(96*(self.0%160)+96*(self.1%160)+self.2%160)%160,
161=>(151*(self.0%161)+121*(self.1%161)+self.2%161)%161,
162=>(112*(self.0%162)+52*(self.1%162)+self.2%162)%162,
163=>(152*(self.0%163)+57*(self.1%163)+self.2%163)%163,
164=>(92*(self.0%164)+16*(self.1%164)+self.2%164)%164,
165=>(91*(self.0%165)+16*(self.1%165)+self.2%165)%165,
166=>(134*(self.0%166)+36*(self.1%166)+self.2%166)%166,
167=>(63*(self.0%167)+49*(self.1%167)+self.2%167)%167,
168=>(88*(self.0%168)+16*(self.1%168)+self.2%168)%168,
169=>(48*(self.0%169)+94*(self.1%169)+self.2%169)%169,
170=>(86*(self.0%170)+86*(self.1%170)+self.2%170)%170,
171=>(4*(self.0%171)+169*(self.1%171)+self.2%171)%171,
172=>(4*(self.0%172)+84*(self.1%172)+self.2%172)%172,
173=>(133*(self.0%173)+47*(self.1%173)+self.2%173)%173,
174=>(112*(self.0%174)+82*(self.1%174)+self.2%174)%174,
175=>(81*(self.0%175)+16*(self.1%175)+self.2%175)%175,
176=>(80*(self.0%176)+16*(self.1%176)+self.2%176)%176,
177=>(25*(self.0%177)+64*(self.1%177)+self.2%177)%177,
178=>(128*(self.0%178)+156*(self.1%178)+self.2%178)%178,
179=>(161*(self.0%179)+124*(self.1%179)+self.2%179)%179,
180=>(76*(self.0%180)+16*(self.1%180)+self.2%180)%180,
181=>(126*(self.0%181)+44*(self.1%181)+self.2%181)%181,
182=>(74*(self.0%182)+16*(self.1%182)+self.2%182)%182,
183=>(73*(self.0%183)+16*(self.1%183)+self.2%183)%183,
184=>(128*(self.0%184)+144*(self.1%184)+self.2%184)%184,
185=>(181*(self.0%185)+86*(self.1%185)+self.2%185)%185,
186=>(70*(self.0%186)+16*(self.1%186)+self.2%186)%186,
187=>(69*(self.0%187)+137*(self.1%187)+self.2%187)%187,
188=>(108*(self.0%188)+72*(self.1%188)+self.2%188)%188,
189=>(4*(self.0%189)+79*(self.1%189)+self.2%189)%189,
190=>(156*(self.0%190)+36*(self.1%190)+self.2%190)%190,
191=>(103*(self.0%191)+26*(self.1%191)+self.2%191)%191,
192=>(64*(self.0%192)+64*(self.1%192)+self.2%192)%192,
193=>(108*(self.0%193)+84*(self.1%193)+self.2%193)%193,
194=>(132*(self.0%194)+158*(self.1%194)+self.2%194)%194,
195=>(61*(self.0%195)+16*(self.1%195)+self.2%195)%195,
196=>(4*(self.0%196)+100*(self.1%196)+self.2%196)%196,
197=>(175*(self.0%197)+61*(self.1%197)+self.2%197)%197,
198=>(58*(self.0%198)+16*(self.1%198)+self.2%198)%198,
199=>(155*(self.0%199)+126*(self.1%199)+self.2%199)%199,
211=>(119*(self.0%211)+69*(self.1%211)+self.2%211)%211,
223=>(171*(self.0%223)+49*(self.1%223)+self.2%223)%223,
227=>(147*(self.0%227)+104*(self.1%227)+self.2%227)%227,
229=>(104*(self.0%229)+44*(self.1%229)+self.2%229)%229,
233=>(135*(self.0%233)+64*(self.1%233)+self.2%233)%233,
239=>(34*(self.0%239)+150*(self.1%239)+self.2%239)%239,
241=>(15*(self.0%241)+225*(self.1%241)+self.2%241)%241,
243=>(193*(self.0%243)+133*(self.1%243)+self.2%243)%243,
251=>(243*(self.0%251)+69*(self.1%251)+self.2%251)%251,
256=>(0*(self.0%256)+0*(self.1%256)+self.2%256)%256,
257=>(1*(self.0%257)+1*(self.1%257)+self.2%257)%257,
263=>(33*(self.0%263)+104*(self.1%263)+self.2%263)%263,
269=>(21*(self.0%269)+57*(self.1%269)+self.2%269)%269,
271=>(36*(self.0%271)+265*(self.1%271)+self.2%271)%271,
277=>(155*(self.0%277)+175*(self.1%277)+self.2%277)%277,
281=>(85*(self.0%281)+101*(self.1%281)+self.2%281)%281,
283=>(151*(self.0%283)+240*(self.1%283)+self.2%283)%283,
289=>(35*(self.0%289)+18*(self.1%289)+self.2%289)%289,
293=>(161*(self.0%293)+109*(self.1%293)+self.2%293)%293,
307=>(199*(self.0%307)+97*(self.1%307)+self.2%307)%307,
311=>(35*(self.0%311)+208*(self.1%311)+self.2%311)%311,
313=>(132*(self.0%313)+142*(self.1%313)+self.2%313)%313,
317=>(235*(self.0%317)+251*(self.1%317)+self.2%317)%317,
331=>(256*(self.0%331)+16*(self.1%331)+self.2%331)%331,
337=>(4*(self.0%337)+2*(self.1%337)+self.2%337)%337,
343=>(151*(self.0%343)+296*(self.1%343)+self.2%343)%343,
347=>(129*(self.0%347)+167*(self.1%347)+self.2%347)%347,
349=>(148*(self.0%349)+219*(self.1%349)+self.2%349)%349,
353=>(22*(self.0%353)+187*(self.1%353)+self.2%353)%353,
359=>(264*(self.0%359)+303*(self.1%359)+self.2%359)%359,
361=>(156*(self.0%361)+321*(self.1%361)+self.2%361)%361,
367=>(129*(self.0%367)+297*(self.1%367)+self.2%367)%367,
373=>(68*(self.0%373)+21*(self.1%373)+self.2%373)%373,
379=>(171*(self.0%379)+277*(self.1%379)+self.2%379)%379,
383=>(150*(self.0%383)+143*(self.1%383)+self.2%383)%383,
389=>(164*(self.0%389)+169*(self.1%389)+self.2%389)%389,
397=>(273*(self.0%397)+99*(self.1%397)+self.2%397)%397,
401=>(360*(self.0%401)+63*(self.1%401)+self.2%401)%401,
409=>(265*(self.0%409)+80*(self.1%409)+self.2%409)%409,
419=>(100*(self.0%419)+409*(self.1%419)+self.2%419)%419,
421=>(255*(self.0%421)+26*(self.1%421)+self.2%421)%421,
431=>(216*(self.0%431)+337*(self.1%431)+self.2%431)%431,
433=>(150*(self.0%433)+296*(self.1%433)+self.2%433)%433,
439=>(36*(self.0%439)+433*(self.1%439)+self.2%439)%439,
443=>(153*(self.0%443)+215*(self.1%443)+self.2%443)%443,
449=>(18*(self.0%449)+359*(self.1%449)+self.2%449)%449,
457=>(68*(self.0%457)+215*(self.1%457)+self.2%457)%457,
461=>(444*(self.0%461)+370*(self.1%461)+self.2%461)%461,
463=>(60*(self.0%463)+261*(self.1%463)+self.2%463)%463,
467=>(264*(self.0%467)+369*(self.1%467)+self.2%467)%467,
479=>(28*(self.0%479)+403*(self.1%479)+self.2%479)%479,
487=>(467*(self.0%487)+286*(self.1%487)+self.2%487)%487,
491=>(429*(self.0%491)+263*(self.1%491)+self.2%491)%491,
499=>(462*(self.0%499)+31*(self.1%499)+self.2%499)%499,
_=>2
}) as usize
}
}
type BIG=BigUInt;
#
fn gcd(i:u32,j:BIG)->u32{//ensure i<j for better performance
let (mut i,mut j)=(j.rem(i as u32) as u32,i);
while i != 0{
let t=j%i;
j=i;
i=t;
}
j
}
fn search_roll(b:Vec<BIG>,ix:u32,mut repeats:BIG)->(Vec<BIG>,BIG){
let i=ix/gcd(ix,repeats);
let b=if i>1{b.into_iter().map(|x|(0..i).map(|c|x.expand(repeats,c as u128)).filter(|x|ISPRIME).collect::<Vec<_>>()).flatten().collect::<Vec<_>>()}else{b};
if i>1 {repeats=repeats.mul(i as u128)}
(b,repeats)
}
fn search_once(b:&,mut upper:u32)->u32{
let mut c=b.into_iter();
c.next();
let mut gg=vec!;
let mut rem=vec!;
let mut h=rem.drain(..);
while let Some(hh)=h.next(){
gg.push(hh);
if hh>=upper{break}
}
for i in c{
while gg.iter().copied().all(|t|ISPRIME){
upper=h.next().unwrap();
println!("found number= {:?} for n<{}!",i,upper);
gg.push(upper);
}
}
upper
}
tuneing const
#!
/*
LENGTH=500
a=*(LENGTH+1)
a=a=False
for i in range(2,LENGTH+1):
if a:
for j in range(2,(LENGTH//i)+1):
a=False
print(("const ISPRIME:= "%(LENGTH+1))+str(a).lower().replace(" ","")+";")
aa=
for i in :
j=i*i;
while j<=LENGTH:
aa=True
j*=i
for i in range(1,200):
aa=True
#for u32
print("\n".join(["N=>(self.5%N+N1*(self.4%N)+N2*(self.3%N)+N3*(self.2%N)+N4*(self.1%N)+N5*(self.0%N))%N,".replace("N5",str(2**(32*5)%n)).replace("N4",str(2**(32*4)%n)).replace("N3",str(2**(32*3)%n)).replace("N2",str(2**(32*2)%n)).replace("N1",str(2**32%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
#for u64 array
print("\n".join([" N=>(N2*((self.0)%N)+N1*((self.0)%N)+(self.0)%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
#for u64
print("\n".join([" N=>(N2*(self.0%N)+N1*(self.1%N)+self.2%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
print("\n".join([" N=>(N3*(self.0%N)+N2*(self.1%N)+N1*(self.2%N)+self.3%N)%N,".replace("N3",str(2**(64*3)%n)).replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
*/
const ISPRIME:= ;
const UPPER:u32=180;
const HALF:u32=(UPPER>>1)+1;
const TO:u32=109;
fn main(){
let mut lcm=BigUInt(0,0,2);
for i in 3..HALF{
lcm=lcm.mul((i/gcd(i,lcm)) as u128)
}
let mut x=(vec!,lcm);
//x=search_roll(x.0,81,x.1);//3
//x=search_roll(x.0,49,x.1);//7
x=search_roll(x.0,121,x.1);//11
x=search_roll(x.0,125,x.1);//2
x=search_roll(x.0,128,x.1);//5
x=search_roll(x.0,169,x.1);//13
//x=search_roll(x.0,243,x.1);//3
//x=search_roll(x.0,289,x.1);//17
//x=search_roll(x.0,343,x.1);//7
for i in HALF..=TO{
x=search_roll(x.0,i,x.1);
println!("i={},len={},rep={:?}",i,(x.0).len(),x.1);
if (x.0).len()>10000000{println!("break at i={},TO={}",i,TO);break}
}
println!("SHOULD check `TO` and `i` carefully!");
let (mut b,lcm)=x;
b.sort_unstable();
let mut upper=search_once(&b,179);
for i in 0..10{
println!("loop{} finished",i);
b.iter_mut().for_each(|x|*x=x.add(lcm));
upper=search_once(&b,upper);
}
}
#
struct BigUInt(u64,u64,u64);
impl BigUInt{
#
pub fn add(self,other:Self)->Self{
//self+other
let l0=self.2 as u128+ other.2 as u128;
let (l0,g)=(l0 as u64,l0>>64);
let l1=self.1 as u128+g+other.1 as u128;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(self.0+g as u64+other.0 as u64,l1,l0)
}
#
pub fn expand(self,other:Self,b:u128)->Self{
//self+other*b
let l0=self.2 as u128+(other.2 as u128)*b;
let (l0,g)=(l0 as u64,l0>>64);
let l1=self.1 as u128+g+(other.1 as u128)*b;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(self.0+g as u64+other.0*b as u64,l1,l0)
}
#
pub fn mul(self,b:u128)->Self{
//self*b
let l0=(self.2 as u128)*b;
let (l0,g)=(l0 as u64,l0>>64);
let l1=g+(self.1 as u128)*b;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(g as u64+self.0*b as u64,l1,l0)
}
#
pub fn rem(self,b:u32)->usize{
(match b{
1=>0,
2=>(0*(self.0%2)+0*(self.1%2)+self.2%2)%2,
3=>(1*(self.0%3)+1*(self.1%3)+self.2%3)%3,
4=>(0*(self.0%4)+0*(self.1%4)+self.2%4)%4,
5=>(1*(self.0%5)+1*(self.1%5)+self.2%5)%5,
6=>(4*(self.0%6)+4*(self.1%6)+self.2%6)%6,
7=>(4*(self.0%7)+2*(self.1%7)+self.2%7)%7,
8=>(0*(self.0%8)+0*(self.1%8)+self.2%8)%8,
9=>(4*(self.0%9)+7*(self.1%9)+self.2%9)%9,
10=>(6*(self.0%10)+6*(self.1%10)+self.2%10)%10,
11=>(3*(self.0%11)+5*(self.1%11)+self.2%11)%11,
12=>(4*(self.0%12)+4*(self.1%12)+self.2%12)%12,
13=>(9*(self.0%13)+3*(self.1%13)+self.2%13)%13,
14=>(4*(self.0%14)+2*(self.1%14)+self.2%14)%14,
15=>(1*(self.0%15)+1*(self.1%15)+self.2%15)%15,
16=>(0*(self.0%16)+0*(self.1%16)+self.2%16)%16,
17=>(1*(self.0%17)+1*(self.1%17)+self.2%17)%17,
18=>(4*(self.0%18)+16*(self.1%18)+self.2%18)%18,
19=>(4*(self.0%19)+17*(self.1%19)+self.2%19)%19,
20=>(16*(self.0%20)+16*(self.1%20)+self.2%20)%20,
21=>(4*(self.0%21)+16*(self.1%21)+self.2%21)%21,
22=>(14*(self.0%22)+16*(self.1%22)+self.2%22)%22,
23=>(13*(self.0%23)+6*(self.1%23)+self.2%23)%23,
24=>(16*(self.0%24)+16*(self.1%24)+self.2%24)%24,
25=>(6*(self.0%25)+16*(self.1%25)+self.2%25)%25,
26=>(22*(self.0%26)+16*(self.1%26)+self.2%26)%26,
27=>(4*(self.0%27)+25*(self.1%27)+self.2%27)%27,
28=>(4*(self.0%28)+16*(self.1%28)+self.2%28)%28,
29=>(25*(self.0%29)+24*(self.1%29)+self.2%29)%29,
30=>(16*(self.0%30)+16*(self.1%30)+self.2%30)%30,
31=>(8*(self.0%31)+16*(self.1%31)+self.2%31)%31,
32=>(0*(self.0%32)+0*(self.1%32)+self.2%32)%32,
33=>(25*(self.0%33)+16*(self.1%33)+self.2%33)%33,
34=>(18*(self.0%34)+18*(self.1%34)+self.2%34)%34,
35=>(11*(self.0%35)+16*(self.1%35)+self.2%35)%35,
36=>(4*(self.0%36)+16*(self.1%36)+self.2%36)%36,
37=>(33*(self.0%37)+12*(self.1%37)+self.2%37)%37,
38=>(4*(self.0%38)+36*(self.1%38)+self.2%38)%38,
39=>(22*(self.0%39)+16*(self.1%39)+self.2%39)%39,
40=>(16*(self.0%40)+16*(self.1%40)+self.2%40)%40,
41=>(10*(self.0%41)+16*(self.1%41)+self.2%41)%41,
42=>(4*(self.0%42)+16*(self.1%42)+self.2%42)%42,
43=>(4*(self.0%43)+41*(self.1%43)+self.2%43)%43,
44=>(36*(self.0%44)+16*(self.1%44)+self.2%44)%44,
45=>(31*(self.0%45)+16*(self.1%45)+self.2%45)%45,
46=>(36*(self.0%46)+6*(self.1%46)+self.2%46)%46,
47=>(14*(self.0%47)+25*(self.1%47)+self.2%47)%47,
48=>(16*(self.0%48)+16*(self.1%48)+self.2%48)%48,
49=>(4*(self.0%49)+2*(self.1%49)+self.2%49)%49,
50=>(6*(self.0%50)+16*(self.1%50)+self.2%50)%50,
51=>(1*(self.0%51)+1*(self.1%51)+self.2%51)%51,
52=>(48*(self.0%52)+16*(self.1%52)+self.2%52)%52,
53=>(13*(self.0%53)+15*(self.1%53)+self.2%53)%53,
54=>(4*(self.0%54)+52*(self.1%54)+self.2%54)%54,
55=>(36*(self.0%55)+16*(self.1%55)+self.2%55)%55,
56=>(32*(self.0%56)+16*(self.1%56)+self.2%56)%56,
57=>(4*(self.0%57)+55*(self.1%57)+self.2%57)%57,
58=>(54*(self.0%58)+24*(self.1%58)+self.2%58)%58,
59=>(25*(self.0%59)+5*(self.1%59)+self.2%59)%59,
60=>(16*(self.0%60)+16*(self.1%60)+self.2%60)%60,
61=>(12*(self.0%61)+16*(self.1%61)+self.2%61)%61,
62=>(8*(self.0%62)+16*(self.1%62)+self.2%62)%62,
63=>(4*(self.0%63)+16*(self.1%63)+self.2%63)%63,
64=>(0*(self.0%64)+0*(self.1%64)+self.2%64)%64,
65=>(61*(self.0%65)+16*(self.1%65)+self.2%65)%65,
66=>(58*(self.0%66)+16*(self.1%66)+self.2%66)%66,
67=>(21*(self.0%67)+17*(self.1%67)+self.2%67)%67,
68=>(52*(self.0%68)+52*(self.1%68)+self.2%68)%68,
69=>(13*(self.0%69)+52*(self.1%69)+self.2%69)%69,
70=>(46*(self.0%70)+16*(self.1%70)+self.2%70)%70,
71=>(29*(self.0%71)+10*(self.1%71)+self.2%71)%71,
72=>(40*(self.0%72)+16*(self.1%72)+self.2%72)%72,
73=>(4*(self.0%73)+2*(self.1%73)+self.2%73)%73,
74=>(70*(self.0%74)+12*(self.1%74)+self.2%74)%74,
75=>(31*(self.0%75)+16*(self.1%75)+self.2%75)%75,
76=>(4*(self.0%76)+36*(self.1%76)+self.2%76)%76,
77=>(25*(self.0%77)+16*(self.1%77)+self.2%77)%77,
78=>(22*(self.0%78)+16*(self.1%78)+self.2%78)%78,
79=>(73*(self.0%79)+51*(self.1%79)+self.2%79)%79,
80=>(16*(self.0%80)+16*(self.1%80)+self.2%80)%80,
81=>(31*(self.0%81)+52*(self.1%81)+self.2%81)%81,
82=>(10*(self.0%82)+16*(self.1%82)+self.2%82)%82,
83=>(51*(self.0%83)+36*(self.1%83)+self.2%83)%83,
84=>(4*(self.0%84)+16*(self.1%84)+self.2%84)%84,
85=>(1*(self.0%85)+1*(self.1%85)+self.2%85)%85,
86=>(4*(self.0%86)+84*(self.1%86)+self.2%86)%86,
87=>(25*(self.0%87)+82*(self.1%87)+self.2%87)%87,
88=>(80*(self.0%88)+16*(self.1%88)+self.2%88)%88,
89=>(39*(self.0%89)+67*(self.1%89)+self.2%89)%89,
90=>(76*(self.0%90)+16*(self.1%90)+self.2%90)%90,
91=>(74*(self.0%91)+16*(self.1%91)+self.2%91)%91,
92=>(36*(self.0%92)+52*(self.1%92)+self.2%92)%92,
93=>(70*(self.0%93)+16*(self.1%93)+self.2%93)%93,
94=>(14*(self.0%94)+72*(self.1%94)+self.2%94)%94,
95=>(61*(self.0%95)+36*(self.1%95)+self.2%95)%95,
96=>(64*(self.0%96)+64*(self.1%96)+self.2%96)%96,
97=>(35*(self.0%97)+61*(self.1%97)+self.2%97)%97,
98=>(4*(self.0%98)+2*(self.1%98)+self.2%98)%98,
99=>(58*(self.0%99)+16*(self.1%99)+self.2%99)%99,
100=>(56*(self.0%100)+16*(self.1%100)+self.2%100)%100,
101=>(80*(self.0%101)+79*(self.1%101)+self.2%101)%101,
102=>(52*(self.0%102)+52*(self.1%102)+self.2%102)%102,
103=>(38*(self.0%103)+55*(self.1%103)+self.2%103)%103,
104=>(48*(self.0%104)+16*(self.1%104)+self.2%104)%104,
105=>(46*(self.0%105)+16*(self.1%105)+self.2%105)%105,
106=>(66*(self.0%106)+68*(self.1%106)+self.2%106)%106,
107=>(11*(self.0%107)+92*(self.1%107)+self.2%107)%107,
108=>(4*(self.0%108)+52*(self.1%108)+self.2%108)%108,
109=>(105*(self.0%109)+66*(self.1%109)+self.2%109)%109,
110=>(36*(self.0%110)+16*(self.1%110)+self.2%110)%110,
111=>(70*(self.0%111)+49*(self.1%111)+self.2%111)%111,
112=>(32*(self.0%112)+16*(self.1%112)+self.2%112)%112,
113=>(109*(self.0%113)+30*(self.1%113)+self.2%113)%113,
114=>(4*(self.0%114)+112*(self.1%114)+self.2%114)%114,
115=>(36*(self.0%115)+6*(self.1%115)+self.2%115)%115,
116=>(112*(self.0%116)+24*(self.1%116)+self.2%116)%116,
117=>(22*(self.0%117)+16*(self.1%117)+self.2%117)%117,
118=>(84*(self.0%118)+64*(self.1%118)+self.2%118)%118,
119=>(18*(self.0%119)+86*(self.1%119)+self.2%119)%119,
120=>(16*(self.0%120)+16*(self.1%120)+self.2%120)%120,
121=>(58*(self.0%121)+93*(self.1%121)+self.2%121)%121,
122=>(12*(self.0%122)+16*(self.1%122)+self.2%122)%122,
123=>(10*(self.0%123)+16*(self.1%123)+self.2%123)%123,
124=>(8*(self.0%124)+16*(self.1%124)+self.2%124)%124,
125=>(81*(self.0%125)+116*(self.1%125)+self.2%125)%125,
126=>(4*(self.0%126)+16*(self.1%126)+self.2%126)%126,
127=>(4*(self.0%127)+2*(self.1%127)+self.2%127)%127,
128=>(0*(self.0%128)+0*(self.1%128)+self.2%128)%128,
129=>(4*(self.0%129)+127*(self.1%129)+self.2%129)%129,
130=>(126*(self.0%130)+16*(self.1%130)+self.2%130)%130,
131=>(33*(self.0%131)+65*(self.1%131)+self.2%131)%131,
132=>(124*(self.0%132)+16*(self.1%132)+self.2%132)%132,
133=>(4*(self.0%133)+93*(self.1%133)+self.2%133)%133,
134=>(88*(self.0%134)+84*(self.1%134)+self.2%134)%134,
135=>(31*(self.0%135)+106*(self.1%135)+self.2%135)%135,
136=>(120*(self.0%136)+120*(self.1%136)+self.2%136)%136,
137=>(38*(self.0%137)+60*(self.1%137)+self.2%137)%137,
138=>(82*(self.0%138)+52*(self.1%138)+self.2%138)%138,
139=>(30*(self.0%139)+13*(self.1%139)+self.2%139)%139,
140=>(116*(self.0%140)+16*(self.1%140)+self.2%140)%140,
141=>(61*(self.0%141)+25*(self.1%141)+self.2%141)%141,
142=>(100*(self.0%142)+10*(self.1%142)+self.2%142)%142,
143=>(113*(self.0%143)+16*(self.1%143)+self.2%143)%143,
144=>(112*(self.0%144)+16*(self.1%144)+self.2%144)%144,
145=>(141*(self.0%145)+111*(self.1%145)+self.2%145)%145,
146=>(4*(self.0%146)+2*(self.1%146)+self.2%146)%146,
147=>(4*(self.0%147)+100*(self.1%147)+self.2%147)%147,
148=>(144*(self.0%148)+12*(self.1%148)+self.2%148)%148,
149=>(123*(self.0%149)+102*(self.1%149)+self.2%149)%149,
150=>(106*(self.0%150)+16*(self.1%150)+self.2%150)%150,
151=>(105*(self.0%151)+16*(self.1%151)+self.2%151)%151,
152=>(80*(self.0%152)+112*(self.1%152)+self.2%152)%152,
153=>(103*(self.0%153)+52*(self.1%153)+self.2%153)%153,
154=>(102*(self.0%154)+16*(self.1%154)+self.2%154)%154,
155=>(101*(self.0%155)+16*(self.1%155)+self.2%155)%155,
156=>(100*(self.0%156)+16*(self.1%156)+self.2%156)%156,
157=>(39*(self.0%157)+14*(self.1%157)+self.2%157)%157,
158=>(152*(self.0%158)+130*(self.1%158)+self.2%158)%158,
159=>(13*(self.0%159)+121*(self.1%159)+self.2%159)%159,
160=>(96*(self.0%160)+96*(self.1%160)+self.2%160)%160,
161=>(151*(self.0%161)+121*(self.1%161)+self.2%161)%161,
162=>(112*(self.0%162)+52*(self.1%162)+self.2%162)%162,
163=>(152*(self.0%163)+57*(self.1%163)+self.2%163)%163,
164=>(92*(self.0%164)+16*(self.1%164)+self.2%164)%164,
165=>(91*(self.0%165)+16*(self.1%165)+self.2%165)%165,
166=>(134*(self.0%166)+36*(self.1%166)+self.2%166)%166,
167=>(63*(self.0%167)+49*(self.1%167)+self.2%167)%167,
168=>(88*(self.0%168)+16*(self.1%168)+self.2%168)%168,
169=>(48*(self.0%169)+94*(self.1%169)+self.2%169)%169,
170=>(86*(self.0%170)+86*(self.1%170)+self.2%170)%170,
171=>(4*(self.0%171)+169*(self.1%171)+self.2%171)%171,
172=>(4*(self.0%172)+84*(self.1%172)+self.2%172)%172,
173=>(133*(self.0%173)+47*(self.1%173)+self.2%173)%173,
174=>(112*(self.0%174)+82*(self.1%174)+self.2%174)%174,
175=>(81*(self.0%175)+16*(self.1%175)+self.2%175)%175,
176=>(80*(self.0%176)+16*(self.1%176)+self.2%176)%176,
177=>(25*(self.0%177)+64*(self.1%177)+self.2%177)%177,
178=>(128*(self.0%178)+156*(self.1%178)+self.2%178)%178,
179=>(161*(self.0%179)+124*(self.1%179)+self.2%179)%179,
180=>(76*(self.0%180)+16*(self.1%180)+self.2%180)%180,
181=>(126*(self.0%181)+44*(self.1%181)+self.2%181)%181,
182=>(74*(self.0%182)+16*(self.1%182)+self.2%182)%182,
183=>(73*(self.0%183)+16*(self.1%183)+self.2%183)%183,
184=>(128*(self.0%184)+144*(self.1%184)+self.2%184)%184,
185=>(181*(self.0%185)+86*(self.1%185)+self.2%185)%185,
186=>(70*(self.0%186)+16*(self.1%186)+self.2%186)%186,
187=>(69*(self.0%187)+137*(self.1%187)+self.2%187)%187,
188=>(108*(self.0%188)+72*(self.1%188)+self.2%188)%188,
189=>(4*(self.0%189)+79*(self.1%189)+self.2%189)%189,
190=>(156*(self.0%190)+36*(self.1%190)+self.2%190)%190,
191=>(103*(self.0%191)+26*(self.1%191)+self.2%191)%191,
192=>(64*(self.0%192)+64*(self.1%192)+self.2%192)%192,
193=>(108*(self.0%193)+84*(self.1%193)+self.2%193)%193,
194=>(132*(self.0%194)+158*(self.1%194)+self.2%194)%194,
195=>(61*(self.0%195)+16*(self.1%195)+self.2%195)%195,
196=>(4*(self.0%196)+100*(self.1%196)+self.2%196)%196,
197=>(175*(self.0%197)+61*(self.1%197)+self.2%197)%197,
198=>(58*(self.0%198)+16*(self.1%198)+self.2%198)%198,
199=>(155*(self.0%199)+126*(self.1%199)+self.2%199)%199,
211=>(119*(self.0%211)+69*(self.1%211)+self.2%211)%211,
223=>(171*(self.0%223)+49*(self.1%223)+self.2%223)%223,
227=>(147*(self.0%227)+104*(self.1%227)+self.2%227)%227,
229=>(104*(self.0%229)+44*(self.1%229)+self.2%229)%229,
233=>(135*(self.0%233)+64*(self.1%233)+self.2%233)%233,
239=>(34*(self.0%239)+150*(self.1%239)+self.2%239)%239,
241=>(15*(self.0%241)+225*(self.1%241)+self.2%241)%241,
243=>(193*(self.0%243)+133*(self.1%243)+self.2%243)%243,
251=>(243*(self.0%251)+69*(self.1%251)+self.2%251)%251,
256=>(0*(self.0%256)+0*(self.1%256)+self.2%256)%256,
257=>(1*(self.0%257)+1*(self.1%257)+self.2%257)%257,
263=>(33*(self.0%263)+104*(self.1%263)+self.2%263)%263,
269=>(21*(self.0%269)+57*(self.1%269)+self.2%269)%269,
271=>(36*(self.0%271)+265*(self.1%271)+self.2%271)%271,
277=>(155*(self.0%277)+175*(self.1%277)+self.2%277)%277,
281=>(85*(self.0%281)+101*(self.1%281)+self.2%281)%281,
283=>(151*(self.0%283)+240*(self.1%283)+self.2%283)%283,
289=>(35*(self.0%289)+18*(self.1%289)+self.2%289)%289,
293=>(161*(self.0%293)+109*(self.1%293)+self.2%293)%293,
307=>(199*(self.0%307)+97*(self.1%307)+self.2%307)%307,
311=>(35*(self.0%311)+208*(self.1%311)+self.2%311)%311,
313=>(132*(self.0%313)+142*(self.1%313)+self.2%313)%313,
317=>(235*(self.0%317)+251*(self.1%317)+self.2%317)%317,
331=>(256*(self.0%331)+16*(self.1%331)+self.2%331)%331,
337=>(4*(self.0%337)+2*(self.1%337)+self.2%337)%337,
343=>(151*(self.0%343)+296*(self.1%343)+self.2%343)%343,
347=>(129*(self.0%347)+167*(self.1%347)+self.2%347)%347,
349=>(148*(self.0%349)+219*(self.1%349)+self.2%349)%349,
353=>(22*(self.0%353)+187*(self.1%353)+self.2%353)%353,
359=>(264*(self.0%359)+303*(self.1%359)+self.2%359)%359,
361=>(156*(self.0%361)+321*(self.1%361)+self.2%361)%361,
367=>(129*(self.0%367)+297*(self.1%367)+self.2%367)%367,
373=>(68*(self.0%373)+21*(self.1%373)+self.2%373)%373,
379=>(171*(self.0%379)+277*(self.1%379)+self.2%379)%379,
383=>(150*(self.0%383)+143*(self.1%383)+self.2%383)%383,
389=>(164*(self.0%389)+169*(self.1%389)+self.2%389)%389,
397=>(273*(self.0%397)+99*(self.1%397)+self.2%397)%397,
401=>(360*(self.0%401)+63*(self.1%401)+self.2%401)%401,
409=>(265*(self.0%409)+80*(self.1%409)+self.2%409)%409,
419=>(100*(self.0%419)+409*(self.1%419)+self.2%419)%419,
421=>(255*(self.0%421)+26*(self.1%421)+self.2%421)%421,
431=>(216*(self.0%431)+337*(self.1%431)+self.2%431)%431,
433=>(150*(self.0%433)+296*(self.1%433)+self.2%433)%433,
439=>(36*(self.0%439)+433*(self.1%439)+self.2%439)%439,
443=>(153*(self.0%443)+215*(self.1%443)+self.2%443)%443,
449=>(18*(self.0%449)+359*(self.1%449)+self.2%449)%449,
457=>(68*(self.0%457)+215*(self.1%457)+self.2%457)%457,
461=>(444*(self.0%461)+370*(self.1%461)+self.2%461)%461,
463=>(60*(self.0%463)+261*(self.1%463)+self.2%463)%463,
467=>(264*(self.0%467)+369*(self.1%467)+self.2%467)%467,
479=>(28*(self.0%479)+403*(self.1%479)+self.2%479)%479,
487=>(467*(self.0%487)+286*(self.1%487)+self.2%487)%487,
491=>(429*(self.0%491)+263*(self.1%491)+self.2%491)%491,
499=>(462*(self.0%499)+31*(self.1%499)+self.2%499)%499,
_=>2
}) as usize
}
}
type BIG=BigUInt;
#
fn gcd(i:u32,j:BIG)->u32{//ensure i<j for better performance
let (mut i,mut j)=(j.rem(i as u32) as u32,i);
while i != 0{
let t=j%i;
j=i;
i=t;
}
j
}
fn search_roll(b:Vec<BIG>,ix:u32,mut repeats:BIG)->(Vec<BIG>,BIG){
let i=ix/gcd(ix,repeats);
let b=if i>1{b.into_iter().map(|x|(0..i).map(|c|x.expand(repeats,c as u128)).filter(|x|ISPRIME).collect::<Vec<_>>()).flatten().collect::<Vec<_>>()}else{b};
if i>1 {repeats=repeats.mul(i as u128)}
(b,repeats)
}
fn search_once(b:&,mut upper:u32)->u32{
let mut c=b.into_iter();
c.next();
let mut gg=vec!;
let mut rem=vec!;
let mut h=rem.drain(..);
while let Some(hh)=h.next(){
gg.push(hh);
if hh>=upper{break}
}
for i in c{
while gg.iter().copied().all(|t|ISPRIME){
upper=h.next().unwrap();
println!("found number= {:?} for n<{}!",i,upper);
gg.push(upper);
}
}
upper
}
i=91,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=92,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=93,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=94,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=95,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=96,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=97,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=98,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=99,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=100,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=101,len=7200,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=102,len=7200,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=103,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=104,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=105,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=106,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=107,len=5054400,rep=BigUInt(326135958006, 4044531529505551460, 1818271812586827904)
i=108,len=5054400,rep=BigUInt(326135958006, 4044531529505551460, 1818271812586827904)
i=109,len=141523200,rep=BigUInt(35548819422677, 16578823020785421982, 13724186834868725376)
break at i=109,TO=109
SHOULD check `TO` and `i` carefully!
found number= BigUInt(21921671246381, 11662777460910458884, 7012004375286606722) for n<181!
loop0 finished
loop1 finished
found number= BigUInt(76640775490436, 17224944753369267051, 5535650887625968770) for n<191!
loop2 finished
loop3 finished
loop4 finished
loop5 finished
loop6 finished
loop7 finished
loop8 finished
found number= BigUInt(336184657781948, 13060152521397031879, 17401726287141301250) for n<193!
loop9 finished
real 0m37.568s
user 0m36.894s
sys 0m0.674s
using Rayon to the 194 gap(n%97 thus = 2)
header
/*
LENGTH=500
a=*(LENGTH+1)
a=a=False
for i in range(2,LENGTH+1):
if a:
for j in range(2,(LENGTH//i)+1):
a=False
print(("const ISPRIME:= "%(LENGTH+1))+str(a).lower().replace(" ","")+";")
aa=
for i in :
j=i*i;
while j<=LENGTH:
aa=True
j*=i
for i in range(1,200):
aa=True
#for u32
print("\n".join(["N=>(self.5%N+N1*(self.4%N)+N2*(self.3%N)+N3*(self.2%N)+N4*(self.1%N)+N5*(self.0%N))%N,".replace("N5",str(2**(32*5)%n)).replace("N4",str(2**(32*4)%n)).replace("N3",str(2**(32*3)%n)).replace("N2",str(2**(32*2)%n)).replace("N1",str(2**32%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
#for u64 array
print("\n".join([" N=>(N2*((self.0)%N)+N1*((self.0)%N)+(self.0)%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
#for u64
print("\n".join([" N=>(N2*(self.0%N)+N1*(self.1%N)+self.2%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
print("\n".join([" N=>(N3*(self.0%N)+N2*(self.1%N)+N1*(self.2%N)+self.3%N)%N,".replace("N3",str(2**(64*3)%n)).replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
*/
const ISPRIME:= ;
#
struct BigUInt(u64,u64,u64);
impl BigUInt{
#
pub fn add(self,other:Self)->Self{
//self+other
let l0=self.2 as u128+ other.2 as u128;
let (l0,g)=(l0 as u64,l0>>64);
let l1=self.1 as u128+g+other.1 as u128;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(self.0+g as u64+other.0 as u64,l1,l0)
}
#
pub fn expand(self,other:Self,b:u128)->Self{
//self+other*b
let l0=self.2 as u128+(other.2 as u128)*b;
let (l0,g)=(l0 as u64,l0>>64);
let l1=self.1 as u128+g+(other.1 as u128)*b;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(self.0+g as u64+other.0*b as u64,l1,l0)
}
#
pub fn mul(self,b:u128)->Self{
//self*b
let l0=(self.2 as u128)*b;
let (l0,g)=(l0 as u64,l0>>64);
let l1=g+(self.1 as u128)*b;
let (l1,g)=(l1 as u64,l1>>64);
BigUInt(g as u64+self.0*b as u64,l1,l0)
}
#
pub fn rem(self,b:u32)->usize{
(match b{
1=>0,
2=>(0*(self.0%2)+0*(self.1%2)+self.2%2)%2,
3=>(1*(self.0%3)+1*(self.1%3)+self.2%3)%3,
4=>(0*(self.0%4)+0*(self.1%4)+self.2%4)%4,
5=>(1*(self.0%5)+1*(self.1%5)+self.2%5)%5,
6=>(4*(self.0%6)+4*(self.1%6)+self.2%6)%6,
7=>(4*(self.0%7)+2*(self.1%7)+self.2%7)%7,
8=>(0*(self.0%8)+0*(self.1%8)+self.2%8)%8,
9=>(4*(self.0%9)+7*(self.1%9)+self.2%9)%9,
10=>(6*(self.0%10)+6*(self.1%10)+self.2%10)%10,
11=>(3*(self.0%11)+5*(self.1%11)+self.2%11)%11,
12=>(4*(self.0%12)+4*(self.1%12)+self.2%12)%12,
13=>(9*(self.0%13)+3*(self.1%13)+self.2%13)%13,
14=>(4*(self.0%14)+2*(self.1%14)+self.2%14)%14,
15=>(1*(self.0%15)+1*(self.1%15)+self.2%15)%15,
16=>(0*(self.0%16)+0*(self.1%16)+self.2%16)%16,
17=>(1*(self.0%17)+1*(self.1%17)+self.2%17)%17,
18=>(4*(self.0%18)+16*(self.1%18)+self.2%18)%18,
19=>(4*(self.0%19)+17*(self.1%19)+self.2%19)%19,
20=>(16*(self.0%20)+16*(self.1%20)+self.2%20)%20,
21=>(4*(self.0%21)+16*(self.1%21)+self.2%21)%21,
22=>(14*(self.0%22)+16*(self.1%22)+self.2%22)%22,
23=>(13*(self.0%23)+6*(self.1%23)+self.2%23)%23,
24=>(16*(self.0%24)+16*(self.1%24)+self.2%24)%24,
25=>(6*(self.0%25)+16*(self.1%25)+self.2%25)%25,
26=>(22*(self.0%26)+16*(self.1%26)+self.2%26)%26,
27=>(4*(self.0%27)+25*(self.1%27)+self.2%27)%27,
28=>(4*(self.0%28)+16*(self.1%28)+self.2%28)%28,
29=>(25*(self.0%29)+24*(self.1%29)+self.2%29)%29,
30=>(16*(self.0%30)+16*(self.1%30)+self.2%30)%30,
31=>(8*(self.0%31)+16*(self.1%31)+self.2%31)%31,
32=>(0*(self.0%32)+0*(self.1%32)+self.2%32)%32,
33=>(25*(self.0%33)+16*(self.1%33)+self.2%33)%33,
34=>(18*(self.0%34)+18*(self.1%34)+self.2%34)%34,
35=>(11*(self.0%35)+16*(self.1%35)+self.2%35)%35,
36=>(4*(self.0%36)+16*(self.1%36)+self.2%36)%36,
37=>(33*(self.0%37)+12*(self.1%37)+self.2%37)%37,
38=>(4*(self.0%38)+36*(self.1%38)+self.2%38)%38,
39=>(22*(self.0%39)+16*(self.1%39)+self.2%39)%39,
40=>(16*(self.0%40)+16*(self.1%40)+self.2%40)%40,
41=>(10*(self.0%41)+16*(self.1%41)+self.2%41)%41,
42=>(4*(self.0%42)+16*(self.1%42)+self.2%42)%42,
43=>(4*(self.0%43)+41*(self.1%43)+self.2%43)%43,
44=>(36*(self.0%44)+16*(self.1%44)+self.2%44)%44,
45=>(31*(self.0%45)+16*(self.1%45)+self.2%45)%45,
46=>(36*(self.0%46)+6*(self.1%46)+self.2%46)%46,
47=>(14*(self.0%47)+25*(self.1%47)+self.2%47)%47,
48=>(16*(self.0%48)+16*(self.1%48)+self.2%48)%48,
49=>(4*(self.0%49)+2*(self.1%49)+self.2%49)%49,
50=>(6*(self.0%50)+16*(self.1%50)+self.2%50)%50,
51=>(1*(self.0%51)+1*(self.1%51)+self.2%51)%51,
52=>(48*(self.0%52)+16*(self.1%52)+self.2%52)%52,
53=>(13*(self.0%53)+15*(self.1%53)+self.2%53)%53,
54=>(4*(self.0%54)+52*(self.1%54)+self.2%54)%54,
55=>(36*(self.0%55)+16*(self.1%55)+self.2%55)%55,
56=>(32*(self.0%56)+16*(self.1%56)+self.2%56)%56,
57=>(4*(self.0%57)+55*(self.1%57)+self.2%57)%57,
58=>(54*(self.0%58)+24*(self.1%58)+self.2%58)%58,
59=>(25*(self.0%59)+5*(self.1%59)+self.2%59)%59,
60=>(16*(self.0%60)+16*(self.1%60)+self.2%60)%60,
61=>(12*(self.0%61)+16*(self.1%61)+self.2%61)%61,
62=>(8*(self.0%62)+16*(self.1%62)+self.2%62)%62,
63=>(4*(self.0%63)+16*(self.1%63)+self.2%63)%63,
64=>(0*(self.0%64)+0*(self.1%64)+self.2%64)%64,
65=>(61*(self.0%65)+16*(self.1%65)+self.2%65)%65,
66=>(58*(self.0%66)+16*(self.1%66)+self.2%66)%66,
67=>(21*(self.0%67)+17*(self.1%67)+self.2%67)%67,
68=>(52*(self.0%68)+52*(self.1%68)+self.2%68)%68,
69=>(13*(self.0%69)+52*(self.1%69)+self.2%69)%69,
70=>(46*(self.0%70)+16*(self.1%70)+self.2%70)%70,
71=>(29*(self.0%71)+10*(self.1%71)+self.2%71)%71,
72=>(40*(self.0%72)+16*(self.1%72)+self.2%72)%72,
73=>(4*(self.0%73)+2*(self.1%73)+self.2%73)%73,
74=>(70*(self.0%74)+12*(self.1%74)+self.2%74)%74,
75=>(31*(self.0%75)+16*(self.1%75)+self.2%75)%75,
76=>(4*(self.0%76)+36*(self.1%76)+self.2%76)%76,
77=>(25*(self.0%77)+16*(self.1%77)+self.2%77)%77,
78=>(22*(self.0%78)+16*(self.1%78)+self.2%78)%78,
79=>(73*(self.0%79)+51*(self.1%79)+self.2%79)%79,
80=>(16*(self.0%80)+16*(self.1%80)+self.2%80)%80,
81=>(31*(self.0%81)+52*(self.1%81)+self.2%81)%81,
82=>(10*(self.0%82)+16*(self.1%82)+self.2%82)%82,
83=>(51*(self.0%83)+36*(self.1%83)+self.2%83)%83,
84=>(4*(self.0%84)+16*(self.1%84)+self.2%84)%84,
85=>(1*(self.0%85)+1*(self.1%85)+self.2%85)%85,
86=>(4*(self.0%86)+84*(self.1%86)+self.2%86)%86,
87=>(25*(self.0%87)+82*(self.1%87)+self.2%87)%87,
88=>(80*(self.0%88)+16*(self.1%88)+self.2%88)%88,
89=>(39*(self.0%89)+67*(self.1%89)+self.2%89)%89,
90=>(76*(self.0%90)+16*(self.1%90)+self.2%90)%90,
91=>(74*(self.0%91)+16*(self.1%91)+self.2%91)%91,
92=>(36*(self.0%92)+52*(self.1%92)+self.2%92)%92,
93=>(70*(self.0%93)+16*(self.1%93)+self.2%93)%93,
94=>(14*(self.0%94)+72*(self.1%94)+self.2%94)%94,
95=>(61*(self.0%95)+36*(self.1%95)+self.2%95)%95,
96=>(64*(self.0%96)+64*(self.1%96)+self.2%96)%96,
97=>(35*(self.0%97)+61*(self.1%97)+self.2%97)%97,
98=>(4*(self.0%98)+2*(self.1%98)+self.2%98)%98,
99=>(58*(self.0%99)+16*(self.1%99)+self.2%99)%99,
100=>(56*(self.0%100)+16*(self.1%100)+self.2%100)%100,
101=>(80*(self.0%101)+79*(self.1%101)+self.2%101)%101,
102=>(52*(self.0%102)+52*(self.1%102)+self.2%102)%102,
103=>(38*(self.0%103)+55*(self.1%103)+self.2%103)%103,
104=>(48*(self.0%104)+16*(self.1%104)+self.2%104)%104,
105=>(46*(self.0%105)+16*(self.1%105)+self.2%105)%105,
106=>(66*(self.0%106)+68*(self.1%106)+self.2%106)%106,
107=>(11*(self.0%107)+92*(self.1%107)+self.2%107)%107,
108=>(4*(self.0%108)+52*(self.1%108)+self.2%108)%108,
109=>(105*(self.0%109)+66*(self.1%109)+self.2%109)%109,
110=>(36*(self.0%110)+16*(self.1%110)+self.2%110)%110,
111=>(70*(self.0%111)+49*(self.1%111)+self.2%111)%111,
112=>(32*(self.0%112)+16*(self.1%112)+self.2%112)%112,
113=>(109*(self.0%113)+30*(self.1%113)+self.2%113)%113,
114=>(4*(self.0%114)+112*(self.1%114)+self.2%114)%114,
115=>(36*(self.0%115)+6*(self.1%115)+self.2%115)%115,
116=>(112*(self.0%116)+24*(self.1%116)+self.2%116)%116,
117=>(22*(self.0%117)+16*(self.1%117)+self.2%117)%117,
118=>(84*(self.0%118)+64*(self.1%118)+self.2%118)%118,
119=>(18*(self.0%119)+86*(self.1%119)+self.2%119)%119,
120=>(16*(self.0%120)+16*(self.1%120)+self.2%120)%120,
121=>(58*(self.0%121)+93*(self.1%121)+self.2%121)%121,
122=>(12*(self.0%122)+16*(self.1%122)+self.2%122)%122,
123=>(10*(self.0%123)+16*(self.1%123)+self.2%123)%123,
124=>(8*(self.0%124)+16*(self.1%124)+self.2%124)%124,
125=>(81*(self.0%125)+116*(self.1%125)+self.2%125)%125,
126=>(4*(self.0%126)+16*(self.1%126)+self.2%126)%126,
127=>(4*(self.0%127)+2*(self.1%127)+self.2%127)%127,
128=>(0*(self.0%128)+0*(self.1%128)+self.2%128)%128,
129=>(4*(self.0%129)+127*(self.1%129)+self.2%129)%129,
130=>(126*(self.0%130)+16*(self.1%130)+self.2%130)%130,
131=>(33*(self.0%131)+65*(self.1%131)+self.2%131)%131,
132=>(124*(self.0%132)+16*(self.1%132)+self.2%132)%132,
133=>(4*(self.0%133)+93*(self.1%133)+self.2%133)%133,
134=>(88*(self.0%134)+84*(self.1%134)+self.2%134)%134,
135=>(31*(self.0%135)+106*(self.1%135)+self.2%135)%135,
136=>(120*(self.0%136)+120*(self.1%136)+self.2%136)%136,
137=>(38*(self.0%137)+60*(self.1%137)+self.2%137)%137,
138=>(82*(self.0%138)+52*(self.1%138)+self.2%138)%138,
139=>(30*(self.0%139)+13*(self.1%139)+self.2%139)%139,
140=>(116*(self.0%140)+16*(self.1%140)+self.2%140)%140,
141=>(61*(self.0%141)+25*(self.1%141)+self.2%141)%141,
142=>(100*(self.0%142)+10*(self.1%142)+self.2%142)%142,
143=>(113*(self.0%143)+16*(self.1%143)+self.2%143)%143,
144=>(112*(self.0%144)+16*(self.1%144)+self.2%144)%144,
145=>(141*(self.0%145)+111*(self.1%145)+self.2%145)%145,
146=>(4*(self.0%146)+2*(self.1%146)+self.2%146)%146,
147=>(4*(self.0%147)+100*(self.1%147)+self.2%147)%147,
148=>(144*(self.0%148)+12*(self.1%148)+self.2%148)%148,
149=>(123*(self.0%149)+102*(self.1%149)+self.2%149)%149,
150=>(106*(self.0%150)+16*(self.1%150)+self.2%150)%150,
151=>(105*(self.0%151)+16*(self.1%151)+self.2%151)%151,
152=>(80*(self.0%152)+112*(self.1%152)+self.2%152)%152,
153=>(103*(self.0%153)+52*(self.1%153)+self.2%153)%153,
154=>(102*(self.0%154)+16*(self.1%154)+self.2%154)%154,
155=>(101*(self.0%155)+16*(self.1%155)+self.2%155)%155,
156=>(100*(self.0%156)+16*(self.1%156)+self.2%156)%156,
157=>(39*(self.0%157)+14*(self.1%157)+self.2%157)%157,
158=>(152*(self.0%158)+130*(self.1%158)+self.2%158)%158,
159=>(13*(self.0%159)+121*(self.1%159)+self.2%159)%159,
160=>(96*(self.0%160)+96*(self.1%160)+self.2%160)%160,
161=>(151*(self.0%161)+121*(self.1%161)+self.2%161)%161,
162=>(112*(self.0%162)+52*(self.1%162)+self.2%162)%162,
163=>(152*(self.0%163)+57*(self.1%163)+self.2%163)%163,
164=>(92*(self.0%164)+16*(self.1%164)+self.2%164)%164,
165=>(91*(self.0%165)+16*(self.1%165)+self.2%165)%165,
166=>(134*(self.0%166)+36*(self.1%166)+self.2%166)%166,
167=>(63*(self.0%167)+49*(self.1%167)+self.2%167)%167,
168=>(88*(self.0%168)+16*(self.1%168)+self.2%168)%168,
169=>(48*(self.0%169)+94*(self.1%169)+self.2%169)%169,
170=>(86*(self.0%170)+86*(self.1%170)+self.2%170)%170,
171=>(4*(self.0%171)+169*(self.1%171)+self.2%171)%171,
172=>(4*(self.0%172)+84*(self.1%172)+self.2%172)%172,
173=>(133*(self.0%173)+47*(self.1%173)+self.2%173)%173,
174=>(112*(self.0%174)+82*(self.1%174)+self.2%174)%174,
175=>(81*(self.0%175)+16*(self.1%175)+self.2%175)%175,
176=>(80*(self.0%176)+16*(self.1%176)+self.2%176)%176,
177=>(25*(self.0%177)+64*(self.1%177)+self.2%177)%177,
178=>(128*(self.0%178)+156*(self.1%178)+self.2%178)%178,
179=>(161*(self.0%179)+124*(self.1%179)+self.2%179)%179,
180=>(76*(self.0%180)+16*(self.1%180)+self.2%180)%180,
181=>(126*(self.0%181)+44*(self.1%181)+self.2%181)%181,
182=>(74*(self.0%182)+16*(self.1%182)+self.2%182)%182,
183=>(73*(self.0%183)+16*(self.1%183)+self.2%183)%183,
184=>(128*(self.0%184)+144*(self.1%184)+self.2%184)%184,
185=>(181*(self.0%185)+86*(self.1%185)+self.2%185)%185,
186=>(70*(self.0%186)+16*(self.1%186)+self.2%186)%186,
187=>(69*(self.0%187)+137*(self.1%187)+self.2%187)%187,
188=>(108*(self.0%188)+72*(self.1%188)+self.2%188)%188,
189=>(4*(self.0%189)+79*(self.1%189)+self.2%189)%189,
190=>(156*(self.0%190)+36*(self.1%190)+self.2%190)%190,
191=>(103*(self.0%191)+26*(self.1%191)+self.2%191)%191,
192=>(64*(self.0%192)+64*(self.1%192)+self.2%192)%192,
193=>(108*(self.0%193)+84*(self.1%193)+self.2%193)%193,
194=>(132*(self.0%194)+158*(self.1%194)+self.2%194)%194,
195=>(61*(self.0%195)+16*(self.1%195)+self.2%195)%195,
196=>(4*(self.0%196)+100*(self.1%196)+self.2%196)%196,
197=>(175*(self.0%197)+61*(self.1%197)+self.2%197)%197,
198=>(58*(self.0%198)+16*(self.1%198)+self.2%198)%198,
199=>(155*(self.0%199)+126*(self.1%199)+self.2%199)%199,
211=>(119*(self.0%211)+69*(self.1%211)+self.2%211)%211,
223=>(171*(self.0%223)+49*(self.1%223)+self.2%223)%223,
227=>(147*(self.0%227)+104*(self.1%227)+self.2%227)%227,
229=>(104*(self.0%229)+44*(self.1%229)+self.2%229)%229,
233=>(135*(self.0%233)+64*(self.1%233)+self.2%233)%233,
239=>(34*(self.0%239)+150*(self.1%239)+self.2%239)%239,
241=>(15*(self.0%241)+225*(self.1%241)+self.2%241)%241,
243=>(193*(self.0%243)+133*(self.1%243)+self.2%243)%243,
251=>(243*(self.0%251)+69*(self.1%251)+self.2%251)%251,
256=>(0*(self.0%256)+0*(self.1%256)+self.2%256)%256,
257=>(1*(self.0%257)+1*(self.1%257)+self.2%257)%257,
263=>(33*(self.0%263)+104*(self.1%263)+self.2%263)%263,
269=>(21*(self.0%269)+57*(self.1%269)+self.2%269)%269,
271=>(36*(self.0%271)+265*(self.1%271)+self.2%271)%271,
277=>(155*(self.0%277)+175*(self.1%277)+self.2%277)%277,
281=>(85*(self.0%281)+101*(self.1%281)+self.2%281)%281,
283=>(151*(self.0%283)+240*(self.1%283)+self.2%283)%283,
289=>(35*(self.0%289)+18*(self.1%289)+self.2%289)%289,
293=>(161*(self.0%293)+109*(self.1%293)+self.2%293)%293,
307=>(199*(self.0%307)+97*(self.1%307)+self.2%307)%307,
311=>(35*(self.0%311)+208*(self.1%311)+self.2%311)%311,
313=>(132*(self.0%313)+142*(self.1%313)+self.2%313)%313,
317=>(235*(self.0%317)+251*(self.1%317)+self.2%317)%317,
331=>(256*(self.0%331)+16*(self.1%331)+self.2%331)%331,
337=>(4*(self.0%337)+2*(self.1%337)+self.2%337)%337,
343=>(151*(self.0%343)+296*(self.1%343)+self.2%343)%343,
347=>(129*(self.0%347)+167*(self.1%347)+self.2%347)%347,
349=>(148*(self.0%349)+219*(self.1%349)+self.2%349)%349,
353=>(22*(self.0%353)+187*(self.1%353)+self.2%353)%353,
359=>(264*(self.0%359)+303*(self.1%359)+self.2%359)%359,
361=>(156*(self.0%361)+321*(self.1%361)+self.2%361)%361,
367=>(129*(self.0%367)+297*(self.1%367)+self.2%367)%367,
373=>(68*(self.0%373)+21*(self.1%373)+self.2%373)%373,
379=>(171*(self.0%379)+277*(self.1%379)+self.2%379)%379,
383=>(150*(self.0%383)+143*(self.1%383)+self.2%383)%383,
389=>(164*(self.0%389)+169*(self.1%389)+self.2%389)%389,
397=>(273*(self.0%397)+99*(self.1%397)+self.2%397)%397,
401=>(360*(self.0%401)+63*(self.1%401)+self.2%401)%401,
409=>(265*(self.0%409)+80*(self.1%409)+self.2%409)%409,
419=>(100*(self.0%419)+409*(self.1%419)+self.2%419)%419,
421=>(255*(self.0%421)+26*(self.1%421)+self.2%421)%421,
431=>(216*(self.0%431)+337*(self.1%431)+self.2%431)%431,
433=>(150*(self.0%433)+296*(self.1%433)+self.2%433)%433,
439=>(36*(self.0%439)+433*(self.1%439)+self.2%439)%439,
443=>(153*(self.0%443)+215*(self.1%443)+self.2%443)%443,
449=>(18*(self.0%449)+359*(self.1%449)+self.2%449)%449,
457=>(68*(self.0%457)+215*(self.1%457)+self.2%457)%457,
461=>(444*(self.0%461)+370*(self.1%461)+self.2%461)%461,
463=>(60*(self.0%463)+261*(self.1%463)+self.2%463)%463,
467=>(264*(self.0%467)+369*(self.1%467)+self.2%467)%467,
479=>(28*(self.0%479)+403*(self.1%479)+self.2%479)%479,
487=>(467*(self.0%487)+286*(self.1%487)+self.2%487)%487,
491=>(429*(self.0%491)+263*(self.1%491)+self.2%491)%491,
499=>(462*(self.0%499)+31*(self.1%499)+self.2%499)%499,
_=>2
}) as usize
}
}
main
#!
include!("main.header");
extern crate rayon;
use rayon::prelude::*;
const UPPER:u32=193;
const HALF:u32=(UPPER>>1)+1;
const TO:u32=109;
fn main(){
let mut lcm=BigUInt(0,0,2);
for i in 3..HALF{
lcm=lcm.mul((i/gcd(i,lcm)) as u128)
}
let mut x=(vec!,lcm);
//x=search_roll(x.0,81,x.1);//3
//x=search_roll(x.0,49,x.1);//7
x=search_roll(x.0,121,x.1);//11
x=search_roll(x.0,125,x.1);//2
x=search_roll(x.0,128,x.1);//5
x=search_roll(x.0,169,x.1);//13
//x=search_roll(x.0,243,x.1);//3
//x=search_roll(x.0,289,x.1);//17
//x=search_roll(x.0,343,x.1);//7
for i in HALF..=TO{
x=search_roll(x.0,i,x.1);
println!("i={},len={},rep={:?}",i,(x.0).len(),x.1);
if (x.0).len()>10000000{println!("break at i={},TO={}",i,TO);break}
}
let (mut b,lcm)=x;
b.sort_unstable();
println!("SHOULD check `TO` and `i` carefully!");
(0..100).into_par_iter().for_each(|i|{
search_rayon(&b,193,lcm.mul(i as u128));
});
}
type BIG=BigUInt;
#
fn gcd(i:u32,j:BIG)->u32{//ensure i<j for better performance
let (mut i,mut j)=(j.rem(i as u32) as u32,i);
while i != 0{
let t=j%i;
j=i;
i=t;
}
j
}
fn search_roll(b:Vec<BIG>,ix:u32,mut repeats:BIG)->(Vec<BIG>,BIG){
let i=ix/gcd(ix,repeats);
let b=if i>1{b.into_iter().map(|x|(0..i).map(|c|x.expand(repeats,c as u128)).filter(|x|ISPRIME).collect::<Vec<_>>()).flatten().collect::<Vec<_>>()}else{b};
if i>1 {repeats=repeats.mul(i as u128)}
(b,repeats)
}
fn search_rayon(b:&,mut upper:u32,mp:BIG)->u32{
let mut c=b.into_iter();
c.next();
let mut gg=vec!;
let mut rem=vec!;
let mut h=rem.drain(..);
while let Some(hh)=h.next(){
gg.push(hh);
if hh>=upper{break}
}
for i in c{
while gg.iter().copied().all(|t|ISPRIME){
upper=h.next().unwrap();
println!("found number= {:?} for n<{}!",i.add(mp),upper);
gg.push(upper);
}
}
upper
}
finally found 655569072883475643276379698332630870445125049195696002
using gp:
ff=(d)->for(i=3,900,if(!isprime(d%i),print(i);break))
ff(655569072883475643276379698332630870445125049195696002)
194
to calculate a BigUInt:
BigUInt=(a,b,c)->d=a*2^128+b*2^64+c;for(i=3,900,if(!isprime(d%i),print(i);break));d
verify and calculate the BigUInt
今天把63以前结果补充一下：
? getlast(1395515070407)
56
? getlast(2345173940567)
58
? getlast(3018245755367)
60
? getlast(7985415341207)
62