{mpz_class y=x; int r; string s="";

while (y!=0){r=mpz_class{y%10}.get_si();y=y/10;s=tr[r]+s;}

return s;

{mpz_class y=x; int r; string s="";if(x==0)return "0";

while (y!=0){r=mpz_class{y%b}.get_si();y=y/b;s=tr[r]+s;}

return s;

{string ss; sint i;

ss="";

for(i=0;i<f.size();i=i+2)ss=ss+f[i];

return(ss);

{sint i; string s;if(f.size()==1)return f[0];

if(f.size()==1){s=f[0];return s;}

for(i=0;i<f.size()-2;i=i+2)s=s+f[i]+"{"+f[i+1]+"}";

s=s+f[i];

return s;

{long long ii,jj,kk; if(i==0)return j;if(j==0)return i;

if(j>i){ii=j;jj=i;} else {ii=i;jj=j;}

while(jj!=0){kk=ii%jj;ii=jj;jj=kk;}

{mpz_class ii,jj,kk; if(i==0)return j;if(j==0)return i;

if(j>i){ii=j;jj=i;} else {ii=i;jj=j;}

while(jj!=0){kk=ii%jj;ii=jj;jj=kk;}

for(ii=0;ii<nbsmall;ii++)

{iff=fact[ii];n1=0;

for(i1=0;i1<ff.size();i1++)

{if(i1%2==0)

{for(i2=0;i2<ff[i1].size();i2++)n1=(n1*b+w[ff[i1][i2]])%iff;

}

else

{if(i1==i){if(n1!=((n1*dk+ddk)%iff))break;} else

{for(i2=0;i2<f[i1].size();i2++){if(n1!=((n1*b+w[f[i1][i2]])%iff))break;}

if(i2!=f[i1].size())break;

}

}

}

if(i1==ff.size()&&n1==0){cycles[j]=sb(iff);break;}

}

if(ii<nbsmall)continue;

if(f.size()!=3)break;

if(k>1&&difpowbb(ff[0],sddk,ff[2]))

{cycles[j]="diff of kth powers";continue;}

if((k==2||k==4)&&p4p4p4bb(ff[0],sddk,ff[2]))

{cycles[j]="Germain's rule";continue;}

break;

}

if(j==k){cout<<" cycle of factors of length "<<k<<" at position "<<i+1<<" :";

for(j=0;j<k;j++){cout<<cycles[j]<<",";}

cout<<" for "<<stringf(f)<<"\n"; cout.flush(); return true;

}

}

}

return false;

{if(f.size()<5)return false;

sint i1,i2,j1,j2,k1,k2,ii,ii2,iii,iff;mpz_class n1,dk1,dk2,ddk1,ddk2;

int cycles[cyclemax][cyclemax]; string pj1,pj2;family ff;

for(i1=1;i1<f.size();i1=i1+2)if(f[i1].size()==1)

for(i2=i1+2;i2<f.size();i2=i2+2)if(f[i2].size()==1)

{dk1=1;ddk1=0;ff=f;

for(k1=1;k1<cyclemax;k1++)

{pj1="";dk1=dk1*b;ddk1=ddk1*b+w[f[i1][0]];

for(j1=0;j1<k1;j1++) // fam= fam1(pj1){dk1}fam2

{ff[i1-1]=f[i1-1]+pj1; ff[i1]=sb(ddk1); dk2=1;ddk2=0;pj1=pj1+f[i1];

for(k2=1;k2<cyclemax;k2++)

{pj2="";dk2=dk2*b;ddk2=ddk2*b+w[f[i2][0]];

for(j2=0;j2<k2;j2++) // fam= fam1(pj1){dk1}fam2(pj2){dk2}fam3

{ff[i2-1]=f[i2-1]+pj2; ff[i2]=sb(ddk2);pj2=pj2+f[i2];

for(ii=0;ii<nbsmall;ii++)

{iff=fact[ii];n1=0;

for(iii=0;iii<ff.size();iii++)

{if(iii%2==0)

{for(ii2=0;ii2<ff[iii].size();ii2++)

n1=(n1*b+w[ff[iii][ii2]])%iff;}

else

{if(iii==i1){if(n1!=((n1*dk1+ddk1)%iff))break;} else

if(iii==i2){if(n1!=((n1*dk2+ddk2)%iff))break;} else

{for(ii2=0;ii2<f[iii].size();ii2++)

{if(n1!=((n1*b+w[f[iii][ii2]])%iff))break;}

if(ii2!=f[iii].size())break; } } }

if(iii==ff.size()&&n1==0){cycles[j1][j2]=iff;break;}}

if(ii==nbsmall)break;}

if(j2==k2)break;}

if(k2==cyclemax)break;}

if(j1==k1)break;}

if(k1!=cyclemax)

{cout<<" rectangular cycle of factors of length ("<<k1<<","<<k2<<") ";

cout<<"at positions (" <<i1<<","<<i2<<") :\n";

for(j1=0;j1<k1;j1++)

{cout<<"(";for(j2=0;j2<k2;j2++)cout<<cycles[j1][j2]<<",";

cout<<")\n";

}

return true;

}

}

return false;

{if(f.size()<7)return false;

sint i1,i2,i3,j1,j2,j3,ii,ii2,iii,iff;mpz_class n1,dk1,dk2,ddk1,ddk2;

int cycles[2][2][2]; string pj1,pj2;family ff;

for(i1=1;i1<f.size();i1=i1+2)if(f[i1].size()==1)

for(i2=i1+2;i2<f.size();i2=i2+2)if(f[i2].size()==1)

for(i3=i2+2;i3<f.size();i3=i3+2)if(f[i3].size()==1)

{

for(j1=0;j1<2;j1++){for(j2=0;j2<2;j2++){for(j3=0;j3<2;j3++)

{ff=f;ff[i1]=f[i1]+f[i1];ff[i2]=f[i2]+f[i2];ff[i3]=f[i3]+f[i3];

if(j1==1)ff[i1-1]=f[i1-1]+f[i1];

if(j2==1)ff[i2-1]=f[i2-1]+f[i2];

if(j3==1)ff[i3-1]=f[i3-1]+f[i3];

for(ii=0;ii<nbsmall;ii++)

{iff=fact[ii];n1=0;

for(iii=0;iii<ff.size();iii++)

{if(iii%2==0)

{for(ii2=0;ii2<ff[iii].size();ii2++)

n1=(n1*b+w[ff[iii][ii2]])%iff;}

else

{if(iii==i1){if(n1!=((n1*b*b+(b+1)*w[f[iii][0]])%iff))break;} else

if(iii==i2){if(n1!=((n1*b*b+(b+1)*w[f[iii][0]])%iff))break;} else

if(iii==i3){if(n1!=((n1*b*b+(b+1)*w[f[iii][0]])%iff))break;} else

{for(ii2=0;ii2<f[iii].size();ii2++)

if(n1!=((n1*b+w[f[iii][ii2]])%iff))break;

if(ii2!=f[iii].size())break; } } }

if(iii==ff.size()&&n1==0){

cycles[j1][j2][j3]=iff;break;}}

if(ii==nbsmall)break;}

if(j3!=2)break;} if(j2!=2)break;} if(j1==2)

{cout<<" ternary even/odd factors at positions (" <<i1<<","<<i2<<","<<i3<<") for : "<<stringf(f)<<"===>\n";

for(j1=0;j1<2;j1++) {cout<<"[";for(j2=0;j2<2;j2++){cout<<"(";for(j3=0;j3<2;j3++)cout<<cycles[j1][j2][j3]<<",";}

cout<<"),";}

cout<<"],";cout<<"\n"; return true;}

}

return false;

{family ff,fff; string s,s1,s2,p,p1,p2; bool test;

sint i,j,l,ic,jc,ic1,ic2,lc1,lc2,jc1,jc2,i1,i2,j1,j2;

cout<<stringf(f)<<"\n";cout.flush();fff=f;nt++;

for(j=1;j<f.size();j=j+2) // clean choices

{p="";

for(l=0;l<f[j].size();l++)

{ff=f;ff[j-1]=f[j-1]+f[j][l];s=familystrip(ff);

if(!cover(s))p.push_back(f[j][l]);

}

f[j]=p;

}

for(i=1;i<f.size();i=i+2)if(f[i].size()==0) // simplify void choices

{f[i-1]=f[i-1]+f[i+1];f.erase(f.begin()+i,f.begin()+i+2);i=i-2;}

for(i=1;i<f.size();i=i+2)if(f[i].size()==1&&f[i][0]==f[i+1][0])

{f[i-1]=f[i-1]+f[i];f[i+1].erase(0,1);} // simplify {a}a into a{a}

if(f.size()!=1)

for(i=1;i<f.size()-2;i=i+2){

if(f[i].size()==1&&f[i+1].size()==0&&f[i]==f[i+2])

{f.erase(f.begin()+i+1,f.begin()+i+3);}} // simplify {a}""{a} into {a}

if(f!=fff){cout<<"=======> ";cout<<stringf(f)<<"\n";}

s=familystrip(f);

if(cover(s)){cout<<"covered by "<<covering<<"\n";return;}

if(newprime(s)){return;}

if(f.size()==1)return; // single string

if(smallfactor(f))return;

if(cyclicfactors(f))return;

if(dcyclfact(f))return;

if(par3(f))return;

if(s.size()>lgmax){cout<<"still to analyze (too long)\n";nlong++;

reject<<stringf(f)<<"\n";reject.flush();return;}

if(s.size()<=lgmax/2)

for(i=1;i<f.size();i=i+2)for(j=0;j<f[i].size();j++)

{ff=f;ff[i]=ff[i].erase(j,1);p=f[i][j];

test=smallfactor(ff);

if(!test)test=cyclicfactors(ff);

if(!test)test=dcyclfact(ff);

if(!test)test=par3(ff);

if(test)

{if(f[i].size()==1){f[i-1]=f[i-1]+f[i];cout<<"needed extension ";handelf(f);return;}

ff.insert(ff.begin()+i+1,p);ff.insert(ff.begin()+i+2,f[i]);

cout<<"needed extension ";handelf(ff);return;

}

}

s=""; // if no covering

for(i=1;i<f.size();i=i+2)

{s=s+f[i-1];for(j=0;j<lgmax;j++)s=s+f[i];}

s=s+f.back();if(!cover(s)){cout<<"too long:"<<stringf(f)<<"\n";

reject<<stringf(f)<<"\n";reject.flush();return;}

lc1=1000;ic=1;jc=0;

for(i=1;i<f.size();i=i+2)

{s1="";s2="";

for(j=0;j<i;j=j+2)s1=s1+f[j];

for(j=i+1;j<f.size();j=j+2)s2=s2+f[j];

for(l=0;l<f[i].size();l++)

{p=f[i][l];for(j=0;j<10;j++)p=p+p;

if(cover(s1+p+s2)){if(covering.size()<lc1){lc1=covering.size();ic=i;jc=l;}}

}

}

lc2=lc1;

for(i1=1;i1<f.size();i1=i1+2) for(i2=i1+2;i2<f.size();i2=i2+2)

for(j1=0;j1<f[i1].size();j1++) for(j2=0;j2<f[i2].size();j2++)

{ff=f; p1=f[i1][j1];for(j=0;j<10;j++)p1=p1+p1;p2=f[i2][j2];for(j=0;j<10;j++)p2=p2+p2;

ff[i1-1]=ff[i1-1]+p1;ff[i2-1]=ff[i2-1]+p2;s=familystrip(ff);

if(cover(s)){if(covering.size()<lc2){ic1=i1;ic2=i2;jc1=j1;jc2=j2;lc2=covering.size();}}

}

for(i1=1;i1<f.size();i1=i1+2)

for(j1=0;j1<f[i1].size();j1++) for(j2=j1+1;j2<f[i2].size();j2++)

{ff=f;i2=i1;p1=f[i1][j1];for(j=0;j<10;j++)p1=p1+p1;p2=f[i2][j2];for(j=0;j<10;j++)p2=p2+p2;

ff[i1-1]=f[i1-1]+p1+p2;s=familystrip(ff);

if(!cover(s))continue;

l=covering.size();if(l>=lc2)continue;

ff[i1-1]=f[i1-1]+p2+p1;s=familystrip(ff);

if(!cover(s))continue;

if(l<covering.size())l=covering.size();

if(l>=lc2)continue;

ic1=i1;ic2=i2;jc1=j1;jc2=j2;lc2=l;

}

if(lc2>=lc1) // no pair is really interesting

{if(lc1==1000) // no digit is really selected: chose one randomly

{test=false;

if(f.size()>3){l=f.size()/2;uniform_int_distribution<> distri(0,l-1);test=true;

ic=1+2*(distri(gen));}

if(f[ic].length()>1){uniform_int_distribution<> distrj(0,f[ic].length()-1);jc=distrj(gen);test=true;}

if(test)cout<<"! "<<ic<<","<<jc<<"\n";

}

ff=f;p=f[ic][jc];ff[ic].erase(jc,1);

cout<<"split1 "<<stringf(f)<<" without ("<<ic<<","<<f[ic][jc]<<")-ext="<<lc1<<"\n";handelf(ff);

cout<<"extend1 "<<stringf(f)<<" with ("<<ic<<","<<f[ic][jc]<<")\n";

ff.insert(ff.begin()+ic+1,p);ff.insert(ff.begin()+ic+2,f[ic]); handelf(ff);

}

else // a pair should be handled

{p1=f[ic1][jc1];p2=f[ic2][jc2];

ff=f;ff[ic2].erase(jc2,1);ff[ic1].erase(jc1,1);

cout<<"split2 "<<stringf(f)<<" without ("<<ic1<<","<<f[ic1][jc1]<<") and ("<<ic2<<","<<f[ic2][jc2]<<")-ext="<<lc2<<"\n";

handelf(ff);fff=ff;

ff.insert(ff.begin()+ic1+1,p1);ff.insert(ff.begin()+ic1+2,ff[ic1]+f[ic1][jc1]);

cout<<"extend21 "<<stringf(f)<<" with ("<<ic1<<","<<f[ic1][jc1]<<

") and without ("<<ic2<<","<<f[ic2][jc2]<<")\n";

handelf(ff);ff=fff;

ff.insert(ff.begin()+ic2+1,p2);ff.insert(ff.begin()+ic2+2,ff[ic2]+f[ic2][jc2]);

cout<<"extend22 "<<stringf(f)<<" with ("<<ic2<<","<<f[ic2][jc2]<<

") and without ("<<ic1<<","<<f[ic1][jc1]<<")\n";

handelf(ff);ff=fff;

if(ic1!=ic2)

{ff.insert(ff.begin()+ic1+1,p1);ff.insert(ff.begin()+ic1+2,f[ic1]);

ff.insert(ff.begin()+ic2+3,p2);ff.insert(ff.begin()+ic2+4,f[ic2]);

cout<<"extend212 "<<stringf(f)<<" with ("<<ic1<<","<<f[ic1][jc1]<<

") and ("<<ic2<<","<<f[ic2][jc2]<<")\n";

handelf(ff);

} else

{ff[ic1]=ff[ic1]+p2;ff.insert(ff.begin()+ic1+1,p1);ff.insert(ff.begin()+ic1+2,fff[ic1]+p1);

ff.insert(ff.begin()+ic2+3,p2);ff.insert(ff.begin()+ic2+4,f[ic2]);

cout<<"extend212 "<<stringf(f)<<" with ("<<ic1<<","<<f[ic1][jc1]<<

") and ("<<ic2<<","<<f[ic2][jc2]<<")\n";

handelf(ff);ff=fff;

ff[ic1]=ff[ic1]+p1;ff.insert(ff.begin()+ic1+1,p2);ff.insert(ff.begin()+ic1+2,fff[ic2]+p2);

ff.insert(ff.begin()+ic2+3,p1);ff.insert(ff.begin()+ic2+4,f[ic1]);

cout<<"extend221 "<<stringf(f)<<" with ("<<ic1<<","<<f[ic1][jc2]<<

") and ("<<ic2<<","<<f[ic2][jc1]<<")\n";

handelf(ff);

}

}

{string ms,pref,prefms,p,ss,chunkl,chunkr; family f;

sint i,ilb,ilh,irb,irh,il,ir,j;

mpz_init(rtt); mpz_init(rt1); mpz_init(rt2);

ms=argv[1];b=atoi(argv[1]); lgmax=atoi(argv[2]);

pref="kernel"; prefms=pref+ms;

kern.open(prefms.c_str());

pref="result"; prefms=pref+ms;

result.open(prefms.c_str(),ios::out);

pref="newprimes"; prefms=pref+ms;

court.open(prefms.c_str(),ios::out);

pref="left"; prefms=pref+ms;

reject.open(prefms.c_str(),ios::out);

for(char c='0';c<='9';c++){w[c]=0+c-'0';tr[0+c-'0']=c;}

for(char c='A';c<='Z';c++){w[c]=10+c-'A';tr[10+c-'A']=c;}

for(char c='a';c<='z';c++){w[c]=36+c-'a';tr[36+c-'a']=c;}

buildfact();

cout<<"lgmax="<<lgmax<<"\n";cout.flush();

found.clear();nt=0;nprime=0;nlong=0;

while(kern>>p)

{found.push_back(p);

}

cpustarttime=clock();

while(cin>>p)

{f.clear();ss="";

for(i=0;i<p.length();i++)

{if(p[i]=='{'||p[i]=='}'){f.push_back(ss);ss="";} else ss=ss+p[i];}

f.push_back(ss);

handelf(f);

}

cputime = clock()-cpustarttime; cputime=cputime/1000000;

result<<"\nFinally, in "<<cputime<<" time units, we explored "

<<nt<<" families of numbers for base "<<b;

if(chunkl!="")result<<" and the initial digit "<<chunkl;

if(chunkr!="")result<<" and the terminal digit "<<chunkr;

result<<"\nthere remains "<<nprime<<" primes to incorporate in the kernel, and "

<<nlong<<" families to analyse\n";