#include<iostream>
#include<set>
#include<vector>
#include<array>
#include<chrono>
#include<map>
#include<boost/multiprecision/cpp_int.hpp>
#include<thread>
#include<future>
using namespace boost::multiprecision;using namespace std;int S(set<int>&x){return x.size()?*x.begin(): 0;}void M(vector<array<int1024_t,2>>*f,vector<int>*nr,vector<array<int1024_t,2>>*q,int x,int ct,int nt,promise<int1024_t>*pr){int1024_t m=0;for(size_t i=0;i<f->size();i++){if(i%nt==ct){array<int1024_t,2>h={1,1};for(int j=0;j<2;j++){int1024_t c=(*f)[i][j];int k=0;while(c>0){if(c%2){h[j]*=(*nr)[k];}c>>=1;k++;}}for(auto j=q->begin();j!=q->end();j++){int1024_t g0,g1,f0,f1;int64_t f2,f3;g0=h[0]*(*j)[0];g1=h[1]*(*j)[1];vector<int1024_t>d;vector<int64_t>e;if(g0>g1){swap(g0,g1);}f0=g0;f1=g1;while(f0>1&&(f0>=INT32_MAX/2||f1>=INT32_MAX/2)){int1024_t n=f0;d.push_back(f1/f0);f0=f1%f0;f1=n;}if(f0>1){f2=(int64_t)f0;f3=(int64_t)f1;while(f2>1){int64_t n2=f2;e.push_back(f3/f2);f2=f3%f2;f3=n2;}}f2=0;f3=1;for(auto k=e.rbegin();k!=e.rend();k++){int64_t n2=f3;f3=*k*f3+f2;f2=n2;}f0=f2;f1=f3;for(auto k=d.rbegin();k!=d.rend();k++){int1024_t n=f1;f1=*k*f1+f0;f0=n;}int1024_t K=(x*f0+g0/2)/g0;int1024_t o=min(abs(f1*x-g1*K)*g0,abs(f0*x-g0*K)*g1);if(!m||o<m){m=o;}}}}pr->set_value(m);}int main(){int nt=8;double tt=0;int x;while(cin>>x){auto start=chrono::system_clock::now();vector<array<set<int>,2>>v(x-1),nv;vector<pair<array<int1024_t,2>,int>>r,s;vector<array<int1024_t,2>>f;map<int,int>c;set<int>y;int1024_t t=1;int mp=0;for(int i=2;i<x;i++){if(!v[i-1][0].size()){for(int j=1;j<(x-1)/i+1;j++){v[i*j-1][0].insert(i);v[x-i*j-1][1].insert(i);}if(x%i==0){t*=i;}else if(!mp){mp=i;}}}if(v[0][1].size()==1){continue;}for(auto i=v.begin();i!=v.end();i++){bool e=0;if((*i)[0].size()){for(auto j=(*i)[0].begin();j!=(*i)[0].end();j++){if(t%*j==0){e=1;break;}}}if(e){continue;}if(S((*i)[0])!=mp){nv.push_back(*i);}for(int j=0;j<2;j++){for(auto k=(*i)[j].begin();k!=(*i)[j].end();k++){auto ci=c.find(*k);if(ci==c.end()){c.insert(make_pair(*k,1));}else{ci->second++;}}}}v=nv;map<int,int>ns;vector<int>nr;vector<array<pair<int1024_t,vector<int1024_t>>,2>>bs;int cn=0;for(auto i=v.begin();i!=v.end();i++){if(((*i)[0].size()==1&&(*i)[0].size()==1&&c[*((*i)[0].begin())]<3&&c[*((*i)[1].begin())]<3)){int z=*((*i)[0].begin());if(z!=*((*i)[1].begin())){z*=*((*i)[1].begin());};if(!y.count(z)){y.insert(z);}}else{array<pair<int1024_t,vector<int1024_t>>,2>b;for(int j=0;j<2;j++){b[j].first=0;for(auto k=(*i)[j].begin();k!=(*i)[j].end();k++){auto ni=ns.find(*k);int1024_t c;if(ni==ns.end()){ns.insert(make_pair(*k,cn));nr.push_back(*k);c=((int1024_t)1)<<cn;cn++;}else{c=((int1024_t)1)<<ni->second;}b[j].second.push_back(c);b[j].first|=c;}}bs.push_back(b);}}sort(bs.begin(),bs.end(),[](array<pair<int1024_t,vector<int1024_t>>,2>&x,array<pair<int1024_t,vector<int1024_t>>,2>&y){return min(x[0].first,x[1].first)<min(y[0].first,y[1].first);});r.push_back(make_pair(array<int1024_t,2>{((int1024_t)1)<<ns[mp],0},0));bool D=false,D2=false;while(!D&&r.size()>0){if(D&&!D2){D2=true;}s.clear();for(auto i=r.begin();i!=r.end();i++){for(;i->second<bs.size();i->second++){bool e=0;if(!((i->first[0]&bs[i->second][0].first)||(i->first[1]&bs[i->second][1].first))){break;}}if(i->second==bs.size()){D=true;f.push_back(i->first);}else{for(int j=0;j<2;j++){for(auto k=bs[i->second][j].second.begin();k!=bs[i->second][j].second.end();k++){if(!(i->first[0]&*k||i->first[1]&*k)){array<int1024_t,2>b{i->first[0],i->first[1]};b[j]|=*k;bool e=true;if(D2){for(auto l=f.begin();l!=f.end();l++){if((*l)[0]&b[0]==(*l)[0]&&(*l)[0]&b[1]==(*l)[0]){e=false;break;}}}if(e){s.push_back(make_pair(b,i->second+1));}}}}}}sort(s.begin(),s.end());s.erase(unique(s.begin(),s.end()),s.end());r=s;}if(!D){continue;}size_t w=y.size();vector<array<int1024_t,2>>q(((size_t)1)<<w);for(int j=0;j<(int)(1<<w);j++){q[j]={1,1};auto l=y.begin();for(int k=0;k<w;k++,l++){q[j][(j&(1<<k))/(1<<k)]*=*l;}q[j][0]*=t;}vector<thread>ts(min(f.size(),(size_t)nt));vector<promise<int1024_t>>ps(ts.size());for(size_t i=0;i<ts.size();i++){ts[i]=thread(&M,&f,&nr,&q,x,i,nt,&ps[i]);}int1024_t m=0;for(size_t i=0;i<ts.size();i++){ts[i].join();int1024_t o=ps[i].get_future().get();if(!m||o<m){m=o;}}double rt=(double)((chrono::duration<double>)(std::chrono::system_clock::now()-start)).count();tt+=rt;cout<<x<<"->"<<m<<" : "<<rt<<" secs;total "<<tt<<" secs"<<endl;}}
Try it online!
This C++ version is primarily written to maximise the speed of generating results. It is loosely based on the approach of my Jelly solution, but includes further optimisations. The version on TIO can produce the minimal \$a(n)\$ for all Erdős–Woods numbers <= 538 within about 30 seconds in total, not including the compilation time.
It initially assumed that all Erdos-Woods numbers were even, but they're not - the smallest non-even one is 903 (OEIS A111042). The code posted should handle odd Erdos-Woods numbers too.
Below is a slightly expanded version that will also generate the Erdos-Woods numbers themselves from scratch (i.e. doesn't use a presupplied list). Here's some more results (from an older version for now):
16 -> 2184 : 0.0023778 secs; total 0.0023778 secs
22 -> 3521210 : 0.0007892 secs; total 0.003167 secs
34 -> 47563752566 : 0.0007036 secs; total 0.0038706 secs
36 -> 12913165320 : 0.0008207 secs; total 0.0046913 secs
46 -> 21653939146794 : 0.0011214 secs; total 0.0058127 secs
56 -> 172481165966593120 : 0.0013218 secs; total 0.0071345 secs
64 -> 808852298577787631376 : 0.0011176 secs; total 0.0082521 secs
66 -> 91307018384081053554 : 0.0006865 secs; total 0.0089386 secs
70 -> 1172783000213391981960 : 0.0009034 secs; total 0.009842 secs
76 -> 26214699169906862478864 : 0.001472 secs; total 0.011314 secs
78 -> 27070317575988954996883440 : 0.0016488 secs; total 0.0129628 secs
86 -> 92274830076590427944007586984 : 0.0032485 secs; total 0.0162113 secs
88 -> 3061406404565905778785058155412 : 0.0008836 secs; total 0.0170949 secs
92 -> 549490357654372954691289040 : 0.001961 secs; total 0.0190559 secs
94 -> 38646299993451631575358983576 : 0.0012295 secs; total 0.0202854 secs
96 -> 50130345826827726114787486830 : 0.007897 secs; total 0.0281824 secs
100 -> 35631233179526020414978681410 : 0.0255103 secs; total 0.0536927 secs
106 -> 200414275126007376521127533663324 : 0.0011955 secs; total 0.0548882 secs
112 -> 1022681262163316216977769066573892020 : 0.0016636 secs; total 0.0565518 secs
116 -> 199354011780827861571272685278371171794 : 0.0068985 secs; total 0.0634503 secs
118 -> 5084808394825008411597027854612265320 : 0.0140484 secs; total 0.0774987 secs
120 -> 33088145229978950006171841905081799893430 : 0.0282395 secs; total 0.105738 secs
124 -> 9132534211053896168120244510786592061314796 : 0.0119749 secs; total 0.117713 secs
130 -> 1010223786859974709684811231603116447862010 : 0.0085169 secs; total 0.12623 secs
134 -> 918536092326116746940802093225005168208856 : 0.0080068 secs; total 0.134237 secs
142 -> 326415290503067481481262636553276300760538971418633970 : 0.0097704 secs; total 0.144007 secs
144 -> 12519236270374172120152530393181563366703899726 : 0.0104701 secs; total 0.154477 secs
146 -> 30102196727419035397352263664971701624550 : 0.001873 secs; total 0.15635 secs
154 -> 250086121511153463601017992836053431027953173230156 : 0.0128302 secs; total 0.169181 secs
160 -> 16823726350582448550419008635093980344211195490 : 0.0121503 secs; total 0.181331 secs
162 -> 971838598937769539765770921839883750903640741790 : 0.0048932 secs; total 0.186224 secs
186 -> 1794082996332254346315702546582790195234663527026144577149550 : 0.0059784 secs; total 0.192202 secs
190 -> 100043328863825836942691086460363243931180087197722910850 : 0.0080825 secs; total 0.200285 secs
196 -> 17018920629980040075969105511895180448985253900154238700 : 0.0085788 secs; total 0.208864 secs
204 -> 481578279081960788203960306279407682980396228758026204933056959715840 : 0.0472954 secs; total 0.256159 secs
210 -> 29225782603870300544827882241040291898185518589118372486421537923611871170 : 5.60295 secs; total 5.85911 secs
216 -> 440200183843647241078327939248364204862519711650712622914040841410 : 0.0077262 secs; total 5.86683 secs
218 -> 67518017451793349875086631136663331002689144202850547609381398525979202451060 : 0.0092965 secs; total 5.87613 secs
220 -> 1459104994350090197385240721881419804872579186868731078959002070 : 0.0179516 secs; total 5.89408 secs
222 -> 398425392772309365488991662748906112633693445300311983234641390568 : 0.0085589 secs; total 5.90264 secs
232 -> 907378346149256277304071914319955007121813704909147483268086111540 : 0.0361636 secs; total 5.9388 secs
238 -> 45894107313965996638570818463974089099761314947922544200331971462236682 : 0.0174366 secs; total 5.95624 secs
246 -> 127209574731840814488699664382213489925455290327133090193663688070010069772464 : 0.14518 secs; total 6.10142 secs
248 -> 87349027419299768189875606566564845285333219860920999198422625577318053831430260 : 0.0417115 secs; total 6.14313 secs
250 -> 1274769952223858733770020211602403840979999894289407226855668118167657960120 : 0.0177074 secs; total 6.16084 secs
256 -> 211337714604794757725712768305031523837613606852887423808080138155983960657486438548840080 : 0.0095592 secs; total 6.1704 secs
260 -> 611379532364397862318258986724238889055579879595343134082300581949384481717350 : 0.0143897 secs; total 6.18479 secs
262 -> 457385261010485284248495193082983704923527433029112880026848488309914263938871758209640697245248 : 0.0057613 secs; total 6.19055 secs
268 -> 3837924875435446453632171348188362753950788432477364059540845274930576542794383781497646020913032 : 0.0041049 secs; total 6.19466 secs
276 -> 690516469573823892560050501225021813072395907134207867385994632898243111919015752071367994 : 0.133966 secs; total 6.32862 secs
280 -> 47182555594339904819679927877406287035566782878354969819901299764693418800067961552340 : 0.0912517 secs; total 6.41987 secs
286 -> 120610684017694120228701154065517023464640987099534560151170016560718941441263176114 : 0.0114873 secs; total 6.43136 secs
288 -> 138971473108541248222606578801479253148138919955516661540809691054255010511185699956086224052870 : 0.0775585 secs; total 6.50892 secs
292 -> 185675662432708092090998266897578702332183677920758773231493308055529123987258619622978284717475820 : 0.012051 secs; total 6.52097 secs
296 -> 528072426832989018489058277937146939019285808979376200830352699489792774867918795228285244 : 0.0120736 secs; total 6.53304 secs
298 -> 7925959560314994619176238662647274773767908511981401648794904625493728870549039264807892534696970055800 : 0.0128203 secs; total 6.54586 secs
300 -> 3830358397632282878932144419312617888493673029003334276706856317887318564286779642788172700903966820 : 2.7098 secs; total 9.25566 secs
302 -> 40657328466375053173917761727511056770288784946750010931930738501228836738754637506437259099070010911712995558 : 0.0027574 secs; total 9.25842 secs
306 -> 40577677425253871035899827941839786555247037625668392197716461967627850030740187779049330460230 : 0.413231 secs; total 9.67165 secs
310 -> 538488606541428281546338121909778865003615807576612791533987823960965825028425066849096657000 : 0.0080856 secs; total 9.67973 secs
316 -> 7872867140686218605593823674909333997835782911606331664298338788801081063003828117779226595689776787167680 : 0.0036166 secs; total 9.68335 secs
320 -> 151976414541647699016758460810943108138612297987590453341893209833547476537041052081981397479713129600 : 0.0557666 secs; total 9.73912 secs
324 -> 26361986955675918481699797183223411546429483863365717815976219805637972415698978214362140147547701812766 : 0.0969804 secs; total 9.8361 secs
326 -> 3789841018118926364678300055227311891347014053695801630069508088470681947289010244266304599643061195254304 : 0.002667 secs; total 9.83877 secs
328 -> 10928038824030068766469302266515597858847366735722411591364684152289531562139922070667848114860 : 0.0040279 secs; total 9.84279 secs
330 -> 32164328124314699652501607056033487951959073966795652571372554775412926044029553406890067889637692284566807340 : 93.6157 secs; total 103.458 secs
336 -> 3106020225275080429219264134875355687747745764370605877192451827687782320288332577944406977489148953164 : 0.246205 secs; total 103.705 secs
340 -> 29825269805686870505819604699502725220723406983445751308008620959839573168190344914196554174050824118754330 : 0.0289699 secs; total 103.734 secs
342 -> 240212844654937042612584799122424026485025869333251741199943878938676548397965251130234996068893280600 : 0.22941 secs; total 103.963 secs
346 -> 543096578713377998688537214746167217275303559738471072780629061333582537465383342959631810586241474719593516160 : 0.0062745 secs; total 103.969 secs
356 -> 16954869911528757517125591203874504442168457692764697546479952706970406480165191259262577720757385141714267796770657531340 : 0.002579 secs; total 103.972 secs
366 -> 4389659730095193754318655326327264752833785100279687859257349610267590708369010442448055310835588452360330889210894 : 0.0927121 secs; total 104.065 secs
372 -> 7377842100032579096970847665137405200105289987277245889432100309989104285888041825332110324561692968177624974176800 : 0.336335 secs; total 104.401 secs
378 -> 973134143857711984548808752932685151707551919556522506881076061012440046791171659775408389749625215164909147269668871280 : 2.50325 secs; total 106.904 secs
382 -> 672269870455295752749941691733331442902745781790421727886817450524410833032155123359740686629763506140323192428376385310 : 0.0025048 secs; total 106.907 secs
394 -> 221289329584737900269172059924096886744337194160035374991996053169800056881835752028310810922527670054056514781556013120958243152651198947795931415976 : 0.0032405 secs; total 106.91 secs
396 -> 1962986156270498590837428040271644141937106717996208244700227775952029989686778918949868920441390965913892352842577184164989322280 : 0.357485 secs; total 107.267 secs
400 -> 7487622941447424114189400327301794212912996211997720849199184913543025205738725722282996789897024593595594873848452690 : 0.0106362 secs; total 107.278 secs
404 -> 104988944031640566696876252223159702218634054291721114053942362103943547825159449331266825026341053836613626131254908908390059949340029727927290 : 0.0068556 secs; total 107.285 secs
406 -> 3140483434894111885957811121301682079786715171339614782737909232797671719266043287171188825464389608552117061317022641877667150 : 0.0183488 secs; total 107.303 secs
408 -> 211579081971284319753516661852997477765586890005276537318680476829494942508856533853247237516980759776245938593513888662281476762 : 0.484314 secs; total 107.788 secs
414 -> 184227830045234549016502848638570064283232747405972675492625247428967117610127137967793024207389649680803110124047199844886032416070 : 1.70146 secs; total 109.489 secs
416 -> 89716593469689252073694377593991599925396252252128033061971555378192612549403678662751600278716749636229262016871937541224901670587864 : 0.0045737 secs; total 109.494 secs
424 -> 190621313082002759082457531048983736857933425199317500309526460260480903992578039696090385642014886318893763859405914277246805656256382726421852130 : 0.0129013 secs; total 109.507 secs
426 -> 93728800773978265556429683027376173974950491906681697895736778157191134689503042887570278926594182170446133332560163856227637704274 : 0.160621 secs; total 109.667 secs
428 -> 2931848991408268124639635840008496586773506309953806810487482744551349578602533515984624684883631658704332317293256288264488948110946767780308172 : 0.0070358 secs; total 109.674 secs
430 -> 27478709895719298365755297812017619883221248788103553267387547041210617817326144730386583943696714770371394850963566107511565760 : 0.183163 secs; total 109.857 secs
438 -> 10912133713738946485738976131261562575408798493640821012109929982555297357336779342832390534219583446609310610201415309129133752660304392 : 0.447402 secs; total 110.305 secs
446 -> 1140646211956922665110130943268802509462711871461936692317977656567336777075905111559102852981167574234825226618883638636541407433356327827292857571679143420 : 0.0030787 secs; total 110.308 secs
454 -> 32778488604746971516107026989471786134873496259639072415065379151165026246089617762655468453355618291470712565631400415148976402188426870828927155076332524667888122690930 : 0.0045086 secs; total 110.312 secs
456 -> 151096680791287555145708840203295091586008659656829222140415372024546189048930084841422098326639382479146980605530110525787281920838306339978674 : 30.045 secs; total 140.357 secs
466 -> 1567036107936517776618947389958745525432586256910736346537512869766866036596967674195302350096711059648145953613686739267169651942922997304140534784421838930674 : 0.0076627 secs; total 140.365 secs
470 -> 442636529132068806081734237157206434836968006423546114466573521440524351421895912515760783653974315127885405849361383716546069303602606144594769938590 : 0.039894 secs; total 140.405 secs
472 -> 10184617044462151138890133863697369948628720643109450174383206953743306700307307177810890693876133203419020147232151560327552759086619074348 : 0.0036374 secs; total 140.409 secs
474 -> 1617367866042184847828111911826113198686256982420665156527057977530672664118556420609597651648637558677521232503264167513016194613324137370193144481380920 : 2.84999 secs; total 143.259 secs
476 -> 236014456526751889817622944694390965881058524509721339611383876800307554765688174182401020296857582255254583552096165354006185460487674653777209920 : 0.0580355 secs; total 143.317 secs
484 -> 141976867395758552861787541457927126724538937293609458854032925303046910754958179365387268701118922730055897358394006290803374658100681262033519449099698126678176542426356 : 0.0118532 secs; total 143.328 secs
486 -> 356334501749931789484943782741090710258398678714033932161852193144903024991207070454724045209936833184480106332413355129475649065855116232678542708710 : 0.331206 secs; total 143.66 secs
490 -> 61142856427699216317652651451852676228906233471655696309019956924256750472168114478752815319180103091541437573463446889733710647242210167431263330 : 0.500067 secs; total 144.16 secs
494 -> 13360851385477005746836609396303165290377765108365352964375482734646350283757930339054998760291263161974941451315337859589050340422814787615218791854992672068532376 : 0.0281845 secs; total 144.188 secs
498 -> 37136456756237928456333082900289626867300753740238089774205977596971973140622723718171174705485552866608478552058362711323479010006038966108413071907792830 : 1.73238 secs; total 145.92 secs
512 -> 3056747870887228098274237048029194850161865139074924724362956728582114272246014987352232242442837952089404728413292444253101127040775837013188315154874080676006495913028031281141819149290683720 : 0.0070583 secs; total 145.927 secs
516 -> 1131555242873749534137274770219505280389897328648902629475343634265231956226997190950103242905773228961039181493470861979226757872075973587099786609188514377605334 : 7.83639 secs; total 153.764 secs
518 -> 477900440773544256479262259016273308559590588598496935263961967987794124526804855066381826565156468459813846151185097284888144391947088957185250310387800 : 0.0518673 secs; total 153.816 secs
520 -> 53295397262268776453849317832027361287530404818968588036673281812052585944521470485678375302855137955202286016365201707282088250452598123166205568775120 : 0.531242 secs; total 154.347 secs
526 -> 19424119374445642412403413515452767870220141285947188050541538624609193256956205716630247444614560168795810201142653834560712410450343710094164276418543086083594 : 0.005264 secs; total 154.352 secs
528 -> 30694089378160770896860118764822753631340537417762572149219922646503153282141487639750918973387074051444909686447639044669850144084746728440401948616591058733242 : 4.03965 secs; total 158.392 secs
532 -> 13459822155848911563783687954011789407239432497812485476640425254665924231709912955546596483553340050690865588404870256974711800204194799241717025037756572273760675620938682735309504734045828 : 0.0423439 secs; total 158.434 secs
534 -> 117525677123012146851504206773256702574127049792880307128940336050833225345490730514792535209749918559665667573312048870436744825997262807901807331654750578881556 : 2.11484 secs; total 160.549 secs
536 -> 37953035901675033874082777749737339776908186726114170955384846260192326022205601462847134971612903086043582609431025333685948238062884527557649582702731422543516117121509592615405126096626578954525664 : 0.0192415 secs; total 160.568 secs
538 -> 16196651398204425343126936097310356120271733322915212745417863402087632834855106079328035191739382581211211313371102200810776477533999356496876819775145135505886294417405826796677815167202187231226380 : 0.042992 secs; total 160.611 secs
540 -> 7457024203430025045000252745986378288257798055712938914631895114617942193302064491548616645193114952485328586549524995017851549385933748399627674884768699761301176072240176523890 : 2386.21 secs; total 2546.82 secs
546 -> 906090109321101729491726881541053979178972487361799219712590335175522483559909203865941393722108527136430394867372834736293604286304634557871670431017044124429073624820 : 420.93 secs; total 2967.75 secs
550 -> 197490094160544395396549305368226880292622861915466587917449780781018793491009064512769135161880021395235171684350281153672504648514849424450310672780491899440 : 0.067318 secs; total 2967.82 secs
552 -> 38282359610231628282831498788938209861245275810769012526965243452818895402093285406329236081174607890226405739681916179312332654073751190321978668248231301342117758090838 : 5.12497 secs; total 2972.94 secs
554 -> 23771229990533688222255135237644396999826197982957529226466440286239303888103093086197321252728038657983679097634246530566372011748924965172231144135340117582179405787427960559356 : 0.0090439 secs; total 2972.95 secs
556 -> 4857603802034637317375127547951669382523516071838990950169026514282756467102928060519727335056584226078970170169997806868256439476020543753338168433279838045467101152377717213736949622910183068526164222761690 : 0.0185084 secs; total 2972.97 secs
560 -> 272208909506156925953839876645187050133348076516401932496369349850650627386265629609139875758757383483902068443401226921109116925430747778344298173444558100717973475040 : 4.8772 secs; total 2977.85 secs
574 -> 1275435375517115512897300542185833966066491035597727224272604123011644504993482909778354167419041389947805448830560987552251025577696795933590399032890985110764978616637169064008224056 : 0.247191 secs; total 2978.1 secs
576 -> 298179859257470177908263364628436856057468391489349634019593712133109176917547027197861721857175410707099262876487528771785466600654551807115456199471239220370627625375591985253094 : 5.12889 secs; total 2983.22 secs
580 -> 21873582157258215963234358946291447731672986994580045624239305366301962394860230998609841412492534091851025222512678649387067473981514527023124860468541170665880381031035147283606967668817905144610277505238789780220 : 0.102718 secs; total 2983.33 secs
582 -> 4016161829994147748845913407152041076046399031071578083952592814719712711657040785664701106746617570126732355008201518684816875880016705765815939547243584178063162124164510986182282668 : 30.3593 secs; total 3013.69 secs
584 -> 45236247400020666480545468726212341723354946922526038432436575755942047488070730224099526255539687116442535538297431957422886242989193405914582974720765434432095661188486323999254703593523324436166436 : 0.0333996 secs; total 3013.72 secs
590 -> 6889383848839915217298949398094374036081630617210157374425520209355276133085552242919621853522810182287592498800627273029020556556839621250456907629276436543675881587810593393893172922948383090 : 0.220044 secs; total 3013.94 secs
604 -> 184620358713498811801944896187295122445956608695311712336954912905293602586260534536882742021739645300399687912768638069331331947240622029962453788103384878521654162484119512065511477948572693795158016 : 0.0051752 secs; total 3013.94 secs
606 -> 89109072215348433817469024454151710803903802285944117425044464435650940985590337051487256308784368328494208624852157573845648189779542064325949845825271360650274235846701393496355129321994 : 162.689 secs; total 3176.63 secs
612 -> 1321055404144574513003582655172280650647793869743403412906828920247108131151252250102075322103991976505400372137998390669329045466134906760071523081549148156083653841941857156040536507968 : 38.5042 secs; total 3215.14 secs
616 -> 9666621445450430777433009930239370627075507536582044785966540594215112757983327047885354306763860678983983146559225232690773501091711583869809931872697919620408682024744046390333114740 : 0.56366 secs; total 3215.7 secs
624 -> 5787931117691527449382170368040556978905353865643472593867302507531631417320117806460428790429845594369595233599226031846058723763606389486025690470528950041577838749110533253673486411705923136 : 111.509 secs; total 3327.21 secs
#include<iostream>
#include<set>
#include<vector>
#include<array>
#include<chrono>
#include<map>
#include<boost/multiprecision/cpp_int.hpp>
#include<thread>
#include<future>
using namespace boost::multiprecision;
using namespace std;
int S(set<int> &x) {
return x.size() ? *x.begin() : 0;
}
void M(vector<array<int1024_t, 2>> * f, vector<int> * nr, vector<array<int1024_t, 2>> * q, int x, int ct, int nt, promise<int1024_t> * pr) {
int1024_t m = 0;
for (size_t i = 0; i < f->size(); i++) {
if (i % nt == ct) {
array<int1024_t, 2> h = { 1,1 };
for (int j = 0; j < 2; j++) {
int1024_t c = (*f)[i][j];
// cout << "c: " << c << endl;
int k = 0;
while(c > 0) {
if (c % 2) {
h[j] *= (*nr)[k];
}
//cout << k << " " << c << " " << (*nr)[k] << " " << c % 2 << " " << h[j] << endl;
c >>= 1;
k++;
}
//cout << "h: " << h[j] << endl;
// cout<< "-";
}
// cout<<endl;
for (auto j = q->begin(); j != q->end(); j++) {
int1024_t g0, g1, f0, f1;
int64_t f2, f3;
g0 = h[0] * (*j)[0]; g1 = h[1] * (*j)[1];
//cout << g0 << " " << g1 << " " << h[0] << " " << h[1] << " " << (*j)[0] << " " << (*j)[1] << endl;
vector<int1024_t>d;
vector<int64_t>e;
if (g0 > g1) { swap(g0, g1); }
f0 = g0; f1 = g1;
while (f0 > 1 && (f0 >= INT32_MAX / 2 || f1 >= INT32_MAX / 2)) {
int1024_t n = f0;
d.push_back(f1 / f0);
f0 = f1 % f0;
f1 = n;
}
if (f0 > 1) {
f2 = (int64_t)f0;
f3 = (int64_t)f1;
while (f2 > 1) {
int64_t n2 = f2;
e.push_back(f3 / f2);
f2 = f3 % f2;
f3 = n2;
}
}
f2 = 0; f3 = 1;
for (auto k = e.rbegin(); k != e.rend(); k++) {
int64_t n2 = f3;
f3 = *k * f3 + f2;
f2 = n2;
}
f0 = f2; f1 = f3;
for (auto k = d.rbegin(); k != d.rend(); k++) {
//cout<<f[0]<<" "<<f[1]<<" "<<(*j)<<endl;
int1024_t n = f1;
f1 = *k * f1 + f0;
f0 = n;
}
int1024_t K = (x * f0 + g0 / 2) / g0;
int1024_t o = min(abs(f1 * x - g1 * K) * g0, abs(f0 * x - g0 * K) * g1);
//cout << x << " " << f0 << " " << f1 << " " << g0 << " " << g1 << " " << K << " " << o << endl;
//cout<<o<<" m "<<m<<endl;
if (!m || o < m) { m = o; }
}
}
//cout<<endl;
}
pr->set_value(m);
}
int main()
{
int nt = 8;
double tt = 0;
for (int x = 36; x < 1000; x++) {
auto start = chrono::system_clock::now();
vector<array<set<int>, 2>>v(x - 1), nv;
vector<pair<array<int1024_t, 2>, int>>r, s;
vector<array<int1024_t, 2>>f;
map<int, int>c;
set<int>y;
int1024_t t = 1;
int mp = 0;
for (int i = 2; i < x; i ++) {
if (!v[i - 1][0].size()) {
for (int j = 1; j < (x - 1) / i + 1; j++) {
v[i * j - 1][0].insert(i);
v[x - i * j - 1][1].insert(i);
}
if (x % i == 0) {
t *= i;
}
else if (!mp) {
mp = i;
}
}
}
if (v[0][1].size() == 1) {
continue;
}
for (auto i = v.begin(); i != v.end(); i++) {
bool e = 0;
if ((*i)[0].size()) {
for (auto j = (*i)[0].begin(); j != (*i)[0].end(); j++) {
if (t % *j == 0) {
e = 1;
break;
}
}
}
if (e) { continue; }
if (S((*i)[0]) != mp) {
nv.push_back(*i);
}
for (int j = 0; j < 2; j++) {
for (auto k = (*i)[j].begin(); k != (*i)[j].end(); k++) {
auto ci = c.find(*k);
if (ci == c.end()) {
c.insert(make_pair(*k, 1));
}
else {
ci->second++;
}
//cout << *k << " ";
}
//cout << "-";
}
//cout << endl;
}
v = nv;
map<int, int>ns;
vector<int>nr;
vector<array<pair<int1024_t,vector<int1024_t>>,2>>bs;
int cn = 0;
for (auto i = v.begin(); i != v.end(); i++) {
if (((*i)[0].size() == 1 && (*i)[0].size() == 1 && c[*((*i)[0].begin())] < 3 && c[*((*i)[1].begin())] < 3)) {
int z = *((*i)[0].begin());
if (z != *((*i)[1].begin())) { z *= *((*i)[1].begin()); };
if (!y.count(z)) {
y.insert(z);
//cout<<z<<endl;
}
}
else {
array<pair<int1024_t,vector<int1024_t>>,2>b;
for (int j = 0; j < 2; j++) {
b[j].first = 0;
for (auto k = (*i)[j].begin(); k != (*i)[j].end(); k++) {
auto ni = ns.find(*k);
int1024_t c;
if (ni == ns.end()) {
ns.insert(make_pair(*k, cn));
nr.push_back(*k);
c = ((int1024_t)1) << cn;
cn++;
}
else {
c = ((int1024_t)1) << ni->second;
}
b[j].second.push_back(c);
b[j].first |= c;
}
}
bs.push_back(b);
}
}
sort(bs.begin(), bs.end(), [](array<pair<int1024_t, vector<int1024_t>>, 2>&x, array<pair<int1024_t, vector<int1024_t>>, 2>&y) {
return min(x[0].first, x[1].first) < min(y[0].first, y[1].first);
});
//cout << "bs size: " << bs.size() << endl;
//for (auto i = bs.begin(); i != bs.end(); i++) {
// for (auto j = 0; j < 2; j++) {
// int k = 0;
// int1024_t c = (*i)[j].first;
// while (c > 0) {
// if (c % 2) {
// cout << nr[k] << " ";
// }
// c >>= 1;
// k++;
// }
// cout << "-";
// }
// cout << endl;
//}
//cout << endl;
//for (auto i = v.begin(); i != v.end(); i++) {
// for (auto j = 0; j < 2; j++) {
// for (auto k = (*i)[j].begin(); k != (*i)[j].end(); k++) {
// cout << *k << " ";
// }
// cout << " - ";
// }
// cout << endl;
//}
r.push_back(make_pair(array<int1024_t, 2>{((int1024_t)1) << ns[mp], 0}, 0));
// cout << "v size: " << v.size();
//int ii = 0;
bool D = false, D2 = false;
while (!D && r.size() > 0 && r.size() < 40000000) { // memory issues above this
//cout << "ii: " << ii << endl;
//for (auto j = 0; j < 2; j++) {
// for (auto k = (*i)[j].begin(); k != (*i)[j].end(); k++) {
// cout << *k << " ";
// }
// cout << " - ";
//}
//cout << endl;
if (D && !D2) {
D2 = true;
}
s.clear();
for (auto i = r.begin(); i != r.end(); i++) {
// for (auto j = 0; j < 2; j++) {
// int k = 0;
// int1024_t c = (*i).first[j];
// while (c > 0) {
// if (c % 2) {
// cout << nr[k] << " ";
// }
// c >>= 1;
// k++;
// }
// cout << "-";
// }
// cout << endl;
for (; i->second < bs.size(); i->second++) {
bool e = 0;
// Check bitmap for left or right set of primes
if (!((i->first[0] & bs[i->second][0].first) || (i->first[1] & bs[i->second][1].first))) {
break;
}
}
if (i->second == bs.size()) {
// Reached the end for this path
D = true;
f.push_back(i->first);
} else if (!D) {
for (int j = 0; j < 2; j++) {
for (auto k = bs[i->second][j].second.begin(); k != bs[i->second][j].second.end(); k++) {
//cout<<k<<" "<<*l<<endl;
if (!(i->first[0] & *k || i->first[1] & *k)) {
array<int1024_t, 2>b{ i->first[0], i->first[1] };
b[j] |= *k;
bool e = true;
if (D2) {
for (auto l = f.begin(); l != f.end(); l++) {
if ((*l)[0] & b[0] == (*l)[0] && (*l)[0] & b[1] == (*l)[0]) {
e = false;
break;
}
}
}
if (e) {
s.push_back(make_pair(b, i->second + 1));
}
}
}
}
}
//cout << endl;
}
//cout<<"s size: "<<s.size()<<endl;
if (!D) {
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
r = s;
//cout << x << ": " << "r size: " << r.size() << endl;
}
//map<size_t, int>rs;
//for (auto j = r.begin(); j != r.end(); j++) {
// size_t js = j->first[0].size() + j->first[1].size();
// auto k = rs.find(js);
// if (k == rs.end()) {
// rs.insert(make_pair(js, 1));
// }
// else {
// k->second++;
// }
//}
//for (auto k = rs.begin(); k != rs.end(); k++) {
// cout << k->first << ": " << k->second << endl;
//}
}
if (!D && r.size() <= 40000000) {
continue;
}
//size_t ms = 0;
//for (auto i = r.begin(); i != r.end(); i++) {
// size_t cs = i->first[0].size() + i->first[1].size();
// if (cs < ms || !ms) { ms = cs; }
//}
size_t w = y.size();
cout << x << " -> " << f.size() << " " << w << " " << (f.size() * ((size_t)1 << w)) << endl;
if (D && w <= 25 && (f.size() * ((size_t)1 << w)) < (1 << 30)) {
vector<array<int1024_t, 2>>q(((size_t)1) << w);
//for (auto j = t.begin(); j != t.end(); j++) {
// cout << "t:" << *j << endl;
//}
for (int j = 0; j < (int)(1 << w); j++) {
q[j] = { 1,1 };
auto l = y.begin();
for (int k = 0; k < w; k++, l++) {
q[j][(j & (1 << k)) / (1 << k)] *= *l;
}
q[j][0] *= t;
//cout << j << ": " << q[j][0] << " " << q[j][1] << endl;
}
vector<thread> ts(min(f.size(), (size_t)nt));
vector<promise<int1024_t>> ps(ts.size());
for (size_t i = 0; i < ts.size(); i++) {
ts[i] = thread(&M, &f, &nr, &q, x, i, nt, &ps[i]);
}
int1024_t m = 0;
for (size_t i = 0; i < ts.size(); i++) {
ts[i].join();
int1024_t o = ps[i].get_future().get();
if (!m || o < m) {
m = o;
}
}
double rt = (double)((chrono::duration<double>)(std::chrono::system_clock::now() - start)).count();
tt += rt;
cout << x << " -> " << m << " : " << rt << " secs; total " << tt << " secs" << endl;
}
else if (D) {
double rt = (double)((chrono::duration<double>)(std::chrono::system_clock::now() - start)).count();
tt += rt;
cout << x << " skipping because too many to check : " << rt << " secs; total " << tt << " secs" << endl;
}
else {
double rt = (double)((chrono::duration<double>)(std::chrono::system_clock::now() - start)).count();
tt += rt;
cout << x << " skipping because search got too broad : " << rt << " secs; total " << tt << " secs" << endl;
}
}
}
3180417880379694
... but21653939146794
satisfies the requirements, while being two orders of magnitude smaller. \$\endgroup\$