23
\$\begingroup\$

Consider, for a given positive integer \$k\$, the sequence \$(a, a+1, a+2, ..., a+k)\$, where \$a\$ is some positive integer. Is there ever a pair \$a, k\$ such that for each element \$a+i\$ in the sequence, either \$\gcd(a, a+i)\$ or \$\gcd(a+i, a+k)\$ are greater than 1?

This was investigated by Alan R. Woods as part of his PhD thesis, and it turns out that the answer is not only "yes", but also, that there are an infinite number of such pairs. For example, choose \$k = 16\$ and \$a = 2184\$, to get the sequence

$$2184, 2185, 2186, 2187, 2188, 2189, 2190, 2191, 2192, 2193, 2194, 2195, 2196, 2197, 2198, 2199, 2200$$

For each element \$x\$ in this sequence, calculate \$\gcd(2184, x)\$ and \$\gcd(2200, x)\$ to get the pairs

$$[8, 2184], [5, 1], [2, 2], [1, 3], [4, 4], [11, 1], [10, 6], [1, 7], [8, 8], [1, 3], [2, 2], [5, 1], [4, 12], [1, 13], [2, 14], [1, 3], [2200, 8]$$

None of these are \$[1,1]\$, therefore the pair \$16, 2184\$ accomplishes the proposed question.

However, not every choice of \$k\$ produces a valid \$a\$. For example, no such \$a\$ exists for \$k = 2\$ (i.e. it is impossible to choose a consecutive triple of positive integers such that the middle is not coprime with either the first or last). The values of \$k\$ for which \$a\$ exists are the Erdős–Woods numbers, which begin

$$16, 22, 34, 36, 46, 56, 64, 66, ...$$

A059756 is the list of Erdős–Woods numbers, and A059757 is the list of corresponding \$a\$'s

Given an Erdős–Woods number \$k\$, output a positive integer \$a\$ for which no element of \$(a,a+1,a+2,...,a+k)\$ is coprime to both \$a\$ and \$a+k\$. The output does not have to be the smallest such integer, so long as the output is always correct.

This is , so the shortest code in bytes wins.

Test Cases

 k                       a
16                    2184
22                 3521210
34             47563752566
36             12913165320
46        3180417880379694
56     2212091405535117414
64  3843095117044776029646
66  3615758618744894508744
70 13151117479433859435440

Bounty

I have awarded a +100 bounty (minimum) to Nick Kennedy's C++ answer, which can handle \$k = 538\$ on Try it online! without timing out.

This has completely blown the scale for the other offered bounty (+500 for producing output for \$k = 76\$ or higher), so instead, I've decided to award +500 to xash's J answer, which was the first to find the more efficient method that other quick answers relied on, as well as notice that the values listed on OEIS were wrong.

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Brownie points for beating my (incredibly inefficient) 15 byte Jelly program \$\endgroup\$
    – caird coinheringaahin g ♦
    Jun 25, 2021 at 23:53
  • \$\begingroup\$ To verify: for the codegolf it doesn't matter whether \$a\$ is minimal, but for the bounties it must be the minimal \$a\$? \$\endgroup\$
    – Greg Martin
    Jun 26, 2021 at 18:48
  • 1
    \$\begingroup\$ @GregMartin Yes - for the code golf, any valid \$a\$ is fine. For the bounty, the output should be the lowest such \$a\$ \$\endgroup\$
    – caird coinheringaahin g ♦
    Jun 26, 2021 at 18:49
  • 1
    \$\begingroup\$ As it turns out, the sequence A059757 is wrong. For example, for \$k=46\$, the given value is 3180417880379694... but 21653939146794 satisfies the requirements, while being two orders of magnitude smaller. \$\endgroup\$
    – Glen O
    Jun 29, 2021 at 9:59
  • \$\begingroup\$ @cairdcoinheringaahing for the bounty, is it the maximum k where all from 16 to that number can be produced within 60 seconds, or the maximum k where each from 16 to that number can individually be produced within 60 seconds? \$\endgroup\$
    – Nick Kennedy
    Jun 30, 2021 at 20:05

14 Answers 14

Reset to default
17
+500
\$\begingroup\$

J, 213 bytes

Computes the lowest solution for each \$n \leq 162\$ on TIO. Also found out that the OEIS lowest values is apparently wrong, as you don't need to put every prime in a partition. Big thanks to @Neil for reminding me about modular arithmetic, otherwise I would have sit at \$n=36\$. :-)

3 :'N-~<./(0{[*|.(]-[*<.@%~)N*0}.@{_2{[:(]\:~@,:[-]*<.@%&{.)/^:a:,.&(=i.2))"1*/&x:&>>,&.>/@(<@((|.@[(;~"1&>&{.,;"1&>&{:)[,"1 0&.>(-.&.>|.)~)`(,:@[)@.(1 e.[:,e.&>))"1&>~)/(<,:a:,~<2),~<"1\:~(,.|.)<@~.@q:i.&.<:N=:y'

Try it online!

How it works

Partition the primes \$\leq n\$ into two sets \$p_0, p_1\$ … this approach doesn't necessarily finds the lowest value, as sometimes not all primes are needed.

Find \$p_0, p_1 \subseteq primes_{\leq n}\$ with \$p_0 \cap p_1 = \emptyset\$, so that every number \$i\$ in \$0 \dots n\$ is a multiples of a prime in \$p_0\$ or \$n - i\$ is a multiple of a prime in \$p_1\$ – so the numbers get sieved. I got the idea from Bertram Felgenhauer's implementation to get the Erdös-Woods numbers. For example, for \$n = 16\$ the sets \$2,3,7,13\$ and \$5,11\$ do this. With \$P_0 = \prod p_0\$ and \$P_1 = \prod p_1\$ we need some \$a, b\$ so that \$aP_0 + n = bP_1\$.

With some shifting around this is equal to \$aP_0 \equiv n \bmod P_1\$, which can be solved with \$a = n P_0^{\phi(P_1)} - tP_1\$. Luckely, J has m&|@^ already efficiently implemented, thus we can easily get a solution with \$t=0\$ and then adjust \$t\$ so \$aP_0\$ will be the lowest over 0. At the end we just find the lowest overall \$aP_0\$ of all partitions.

Another method that is slightly faster (but also quite longer) is to solve the equation with the extended Euclidean Algorithm. \$aP_0 + n = bP_1\$ is \$a(-P_0) + bP_1 = n\$, and with the algorithm we get a solution for \$a(-P_0) + bP_1 = 1\$. We multiply \$a, b\$ by \$n\$ to get a solution for the original formula. To get the smallest positive number, we can increase \$a\$ by \$P_1\$ and decrease \$b\$ by \$-P_0\$ (though in the end we don't care only about one of them, so we can ignore \$b\$).

To get the sets we compute for each \$i \in 1\dots n - 1\$ the primes that would sieve \$i\$ on both side. So with \$n = 16, i = 3\$ would get sieved if \$3 \in p_0\$ or \$13 \in p_1\$. We sort this list so lower numbers that occur more often will already be sieved when construction the sets. Folding these results, starting with the pair \$(\{2\}, \{\})\$, either a pair already sieves that number (then we pass it unaltered to the next iteration), or it doesn't – in which case new sets are generated, so that for example \$(\{2, 3\},\{\})\$ and \$(\{2\}, \{13\})\$ occur next step. We need to make sure that no prime occurs in both sets, otherwise \$gcd(P_0, P_1) \neq 1\$.

Ungolfed (old)

f =: 3 : 0
N=:y
NB. needed primes to sieve number
ps=:(,.|.)<@~.@q:i.&.<: N
NB. initial partitioning of 2;''
i=:(<,:(<2),a:),~<"1 ps
NB. fold and expand each partition to all possibilities
NB. to sieve out the next number
ugh=:([:,&.>/<@(([:(#~*/@~:@;"1)({:@[;~"1&>[:{.n),{.@[;"1&>[:{:n=:,"1 0/&.>/@,:)`(,:@[)@.(1 e.[:,e.&>))"1&>~)/ i
NB. helper function for the mod-calculation
t=:4 :'x-@*y(]-[*>.@%~)N*x y&|@^_1+(-~:)&.q:y'
NB. get each partition's solution and pick the lowest of them
<./t/"1 */&x:&>> ugh
)
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I wanted to do this but I couldn't work out how to do the partitioning. Can't you use the Chinese Remainder Theorem to solve for a? \$\endgroup\$
    – Neil
    Jun 26, 2021 at 17:53
  • \$\begingroup\$ @Neil Of course! Thanks a lot, this makes this blazing fast! :-) (Not exactly CRT because of golf, but close enough.) \$\endgroup\$
    – xash
    Jun 26, 2021 at 20:03
  • \$\begingroup\$ Does phi(P1) refer to the totient function of P1, and if so, how did you find that formula? \$\endgroup\$
    – Underslash
    Jun 26, 2021 at 23:37
  • \$\begingroup\$ @Underslash Yes! Found it in the german wiki for linear diophantine equations – surprisingly can't find an english proof for this. But basically Euler's Theorem + some steps. :-) \$\endgroup\$
    – xash
    Jun 28, 2021 at 15:37
12
\$\begingroup\$

Jelly, 12 bytes

,gþr’§Ạð+¥1#

Try it online!

-3 bytes thanks to caird coinheringaahing

yeah this isn't gonna finish for 22 on TIO.

You can find a more in-depth explanation and step-by-step process for solving and golfing a Jelly solution for this challenge in my YouTube video here.

,gþr’§Ạð+¥1#   Main Link; accept `k`
          1#   nfind; find the first 1 element `a` where all of [a, a + 1, ..., a + k] are not coprime with both [a, a + k]
         ¥     last two links as a dyad:
-------ð       - this link accepts `a` on the left and `a + k` on the right
        +      - this link adds `a` and `k`
               therefore, by the 2,2 chaining rule, this applies the left link to `a` and `a + k`
,gþr             - by the special-case 2,2,2 chaining rule, this applies `gþ` to `(a) , (a+k)` on the left and `(a) r (a+k)` on the right
 gþ                - product table: compute the GCD between all pairs between
,                  - pair; [a, a+k]
   r               - inclusive range; [a, a + 1, a + 2, ..., a + k]
    ’            - decrement each GCD
     §           - vectorized sum: sum each pair
      Ạ          - are all truthy?

Essentially, for each number, we compute the GCD between all elements of [a, a + k] and [a, a + 1, a + 2, ..., a + k]. Then, we get a list of pairs (though each in reverse order to what was presented in the challenge). Then, we subtract 1 from each. Since GCD gives a minimum of 1, this gives a minimum of 0. Therefore, when we sum each pair, and [1, 1] GCD pairs become 0 and everything else remains positive. Therefore, we check if all elements are truthy, and find the first a for which it is.

enter image description here

Improve this answer
\$\endgroup\$
9
\$\begingroup\$

Jelly, 168 bytes

ṫ-;Ṛ×+ƭ/⁸;
%@’п/:ƝṖṚçƒØ.ṫ-××%P{
’ÆfQ$€m2Ṛż$©f/ÐḟFḢWḟ"Ṛ¥€FḊ$ÐḟZ;FQɗ"ʋ@ƬƲṪF®ḟ€ƑƇẈ⁼Ø1ƊƇƲF€fƇFQɗⱮ`ÐLQƲ,@$ŒPżṚ$F€€;"€ʋ@/;"Ɱ®f"Ẹ¥ÐḟFQɗḟF}ɗŒPżṚ$Ʋ$€Ẏf"ⱮẸ€ẠɗƇ®P€ḤżUƊ$€ẎNÞ祀⁸FṂ

Try it online!

A full program taking an integer argument and returning an integer. Works on TIO to solve a for all values of n between 16 and 118 inclusive within 60 seconds. Individually it manages every n up to 130 within 60 seconds.

I’ll post a full explanation later, but crudely it works like this:

  1. Partition primes <n such that all \$i\$ or \$n-i\$ for \$i\$ from \$1\$ to \$n-1\$ have gcd > 1 for one of the two partitions. This is done initially y working out which primes must go together and then trying all combinations of the rest.
  2. Solve the Diophantine equation of the form \$Ax - By = c\$ to work out the final end points.
  3. Find the minimal such solution.

Here’s a minimally golfed Python 3.8 version of this solution that gets from 16 to 144 within 60 seconds.

Thanks to @ovs for pointing out a bug that meant the minimum \$a(n)\$ was not always obtained.

Following @xash’s insightful observation, now doesn’t assume that the prime partition will always include every prime. For example, the value for \$a(46)\$ in the question and the linked OEIS sequence is wrong.

I’ve now got a faster, slightly shorter version which doesn’t guarantee a minimum value of \$a(n)\$ but generates values of \$a(n)\$ for all \$n\$ between 16 and 430 in about 50 seconds on TIO. This represents all of the values of \$n\$ listed in A059756 at the time of writing.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ @ovs fixed at a cost of 1 byte and only reaching 112 in 60 seconds. \$\endgroup\$
    – Nick Kennedy
    Jun 28, 2021 at 10:22
  • 1
    \$\begingroup\$ Apparently to get the lowest value some primes aren't needed in the partition, e.g. for n=46 prime 31 isn't needed in any set. Maybe you can insert [A...],[B...] when both [A...],[B...,x] and [A...,x],[B] occur? \$\endgroup\$
    – xash
    Jun 28, 2021 at 13:10
  • \$\begingroup\$ @xash quite right. I’ve now fixed this so should give the lowest value. Interestingly this means that the OEIS entry is incorrect. \$\endgroup\$
    – Nick Kennedy
    Jun 28, 2021 at 20:33
6
+100
\$\begingroup\$

C++ (gcc), 4344 bytes

#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;
        }
    }
}
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ @cairdcoinheringaahing I’m planning to submit these to OEIS as a b list for A059757. I need to do some work first to confirm that the shortest lists of primes always give the lowest a(k) as they do for the lower values of k. The lowest one I haven’t checked yet is 330, but it should be doable with my C++ code. \$\endgroup\$
    – Nick Kennedy
    Jul 4, 2021 at 18:17
  • \$\begingroup\$ 2598 bytes \$\endgroup\$
    – ceilingcat
    Jul 12, 2021 at 15:21
5
\$\begingroup\$

Python 3.8, 263 407 544 536 bytes

A port of xash's J answer, if this ends up getting the most terms, the bounty should definitely go to them. Uses functionality added to pow in 3.8 to compute modular inverses. Using the bits of integers to store sets of primes resulted in a quite large improvement, this gets to 204 on TIO.

n=int(input())
Q=[]
P=k=r=1
while k<n:Q+=P%k*[k];P*=k*k;k+=1
D=[int(''.join(str(+(a%p<1))for p in Q)[::-1],2)for a in range(n)]
R=[(0,0,-1)]
for i in sorted(range(1,n),key=lambda x:-((P:=D[x]|D[n-x])&-P)):
 N=[];F=D[i];O=D[n-i]
 for p in R:
  A,B,c=p
  if F&A or O&B:N+=p,;continue
  d=F&c;w=1
  while d:
   if d%2:N+=(A^w,B,c^w),
   d>>=1;w*=2
  d=O&c;w=1
  while d:
   if d%2:N+=(A,B^w,c^w),
   d>>=1;w<<=1
 R=N
for v,w,_ in R:
 x=y=1
 for p in Q:
  if v%2:x*=p
  if w%2:y*=p
  v>>=1;w>>=1
 r=min([n*pow(x,-1,y)%y*x-n,r][:r])
print(r)

Try it online!

A bit more readable:

def f(n):
    primes = []
    P = k = 1
    while k<n:
        if P%k: primes.append(k)
        P *= k*k
        k += 1
    divs = [
        int(''.join(str(+(a%p==0))for p in primes)[::-1], 2)
        for a in range(n)
    ]
    np = len(primes)
    partitions = [(0, 0, 2**np-1)]
    for i in sorted(
        range(1,n),
        key=lambda x:bin(divs[x]|divs[n-x])[::-1].index('1'),
        reverse=True
    ):
        new_partitions = []
        factors = divs[i]
        other_factors = divs[n-i]
        for p in partitions:
            set_a, set_b, r_primes = p
            if factors & set_a or other_factors & set_b:
                new_partitions += p,
                continue
            for i, v in enumerate(bin(factors & r_primes)[2:][::-1]):
                if v=='1':
                    w = 1 << i
                    new_partitions += (set_a^w, set_b, r_primes^w),
            for i, v in enumerate(bin(other_factors & r_primes)[2:][::-1]):
                if v=='1':
                    w = 1 << i
                    new_partitions += (set_a, set_b^w, r_primes^w),
        partitions = new_partitions
    result = float('inf')
    for px, py, _ in partitions:
        x = y = 1
        for p in primes:
            if px % 2:
                x *= p
            if py % 2:
                y *= p
            px //= 2
            py //= 2
        result = min(result, n*pow(x,-1,y)%y*x-n)
    return result

Try it online!

After letting this run a bit longer than 60 seconds locally, here are some more results:

 16 -> 2184
 22 -> 3521210
 34 -> 47563752566
 36 -> 12913165320
 46 -> 21653939146794
 56 -> 172481165966593120
 64 -> 808852298577787631376
 66 -> 91307018384081053554
 70 -> 1172783000213391981960
 76 -> 26214699169906862478864
 78 -> 27070317575988954996883440
 86 -> 92274830076590427944007586984
 88 -> 3061406404565905778785058155412
 92 -> 549490357654372954691289040
 94 -> 38646299993451631575358983576
 96 -> 50130345826827726114787486830
100 -> 35631233179526020414978681410
106 -> 200414275126007376521127533663324
112 -> 1022681262163316216977769066573892020
116 -> 199354011780827861571272685278371171794
118 -> 5084808394825008411597027854612265320
120 -> 33088145229978950006171841905081799893430
124 -> 9132534211053896168120244510786592061314796
130 -> 1010223786859974709684811231603116447862010
134 -> 918536092326116746940802093225005168208856
142 -> 326415290503067481481262636553276300760538971418633970
144 -> 12519236270374172120152530393181563366703899726
146 -> 30102196727419035397352263664971701624550
154 -> 250086121511153463601017992836053431027953173230156
160 -> 16823726350582448550419008635093980344211195490
162 -> 971838598937769539765770921839883750903640741790
186 -> 1794082996332254346315702546582790195234663527026144577149550
190 -> 100043328863825836942691086460363243931180087197722910850
196 -> 17018920629980040075969105511895180448985253900154238700
204 -> 481578279081960788203960306279407682980396228758026204933056959715840
210 -> 29225782603870300544827882241040291898185518589118372486421537923611871170
216 -> 440200183843647241078327939248364204862519711650712622914040841410
218 -> 67518017451793349875086631136663331002689144202850547609381398525979202451060
220 -> 1459104994350090197385240721881419804872579186868731078959002070
222 -> 398425392772309365488991662748906112633693445300311983234641390568
232 -> 907378346149256277304071914319955007121813704909147483268086111540
238 -> 45894107313965996638570818463974089099761314947922544200331971462236682
246 -> 127209574731840814488699664382213489925455290327133090193663688070010069772464
248 -> 87349027419299768189875606566564845285333219860920999198422625577318053831430260
250 -> 1274769952223858733770020211602403840979999894289407226855668118167657960120
256 -> 211337714604794757725712768305031523837613606852887423808080138155983960657486438548840080
260 -> 611379532364397862318258986724238889055579879595343134082300581949384481717350
262 -> 457385261010485284248495193082983704923527433029112880026848488309914263938871758209640697245248
268 -> 3837924875435446453632171348188362753950788432477364059540845274930576542794383781497646020913032
276 -> 690516469573823892560050501225021813072395907134207867385994632898243111919015752071367994
280 -> 47182555594339904819679927877406287035566782878354969819901299764693418800067961552340
286 -> 120610684017694120228701154065517023464640987099534560151170016560718941441263176114
288 -> 138971473108541248222606578801479253148138919955516661540809691054255010511185699956086224052870
292 -> 185675662432708092090998266897578702332183677920758773231493308055529123987258619622978284717475820
296 -> 528072426832989018489058277937146939019285808979376200830352699489792774867918795228285244
298 -> 7925959560314994619176238662647274773767908511981401648794904625493728870549039264807892534696970055800
300 -> 3830358397632282878932144419312617888493673029003334276706856317887318564286779642788172700903966820
302 -> 40657328466375053173917761727511056770288784946750010931930738501228836738754637506437259099070010911712995558

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Apparently to get the lowest value some primes aren't needed in the partition, e.g. for n=46 prime 31 isn't needed in any set. Maybe you can insert [A...],[B...] when both [A...],[B...,x] and [A...,x],[B] occur? \$\endgroup\$
    – xash
    Jun 28, 2021 at 13:10
  • \$\begingroup\$ @xash I'll have to think about how to implement this a bit, since I currently don't store any partitions anywhere. Did your solution get faster through this change or did you find some other optimizations? \$\endgroup\$
    – ovs
    Jun 28, 2021 at 15:00
  • 1
    \$\begingroup\$ Instead of brute-forcing&filtering all partitions which made is quite slow for large n, I construct all valid partitions (if 2;3 is a partition so far, and the next number would be eliminated by 7;13, then (2 7;3) and (2;3 13) would be generated – repeating for every number.) This is quite the speedup, as most n only have few such partitions, but a bit annoying to implement. \$\endgroup\$
    – xash
    Jun 28, 2021 at 15:07
  • 1
    \$\begingroup\$ @xash I got this working properly now and after using bits of integers instead of proper sets to encode the subsets and prime factors it actually gets to 190 on TIO. I was quite surprised how big of an improvement the sorting was. \$\endgroup\$
    – ovs
    Jun 29, 2021 at 14:47
4
\$\begingroup\$

Python 3, 97 bytes

f=lambda k,a=1:all(gcd(a,x)+gcd(a+k,x)>2for x in range(a,a+k))and a or f(k,a+1)
from math import*

Try it online!

Might reach the recursion limit, so adjust it with sys.setrecursionlimit. In TIO link it is set to 10000 in Header section.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Ruby, 60 bytes

->k{1.step.find{|x|(x..x+k).all?{|y|y.gcd(k+x)+y.gcd(x)>2}}}

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ cant you change 1.step with (1..) to save 1 character \$\endgroup\$
    – user100752
    Jun 26, 2021 at 12:06
  • \$\begingroup\$ It would not work on TIO, I always use 1.step for that reason. \$\endgroup\$
    – G B
    Jun 26, 2021 at 12:24
4
\$\begingroup\$

Vyxal, 17 bytes

λ?+₌ṡ"Ẋvġ2ẇ‹v∑Π;ṅ

Try it Online!

-3 bytes thanks to lyxal

Using the same approach as my Jelly answer.

You can find a more in-depth walk-through and explanation of my solution on my YouTube channel here. However, the explanation there is outdated.

λ?+₌ṡ"Ẋvġ2ẇ‹v∑Π;ṅ       Full Program; start with `k` on the stack and as the input
λ?+₌ṡ"Ẋvġ2ẇ‹v∑Π;ṅ       Function: given `a`:
 ?                      Push the input, `k`
  +                     Sum with `a`: `a + k`
   ₌ṡ"                  In parallel, apply inclusive range and pair
                        The TOS is now [a, a + k]
                        The second element is [a, a + 1, a + 2, ..., a + k]
      Ẋ                 Cartesian Product
       vġ               GCD of each pair
         2ẇ             Slice into blocks of length 2
           ‹            Decrement
            v∑          Sum of each pair
              Π         Product

                  ṅ     Find the first integer satisfying this
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ ⁰W¦:⁽ṡR$ -> ?+₌ṡ" \$\endgroup\$
    – lyxal
    Jun 27, 2021 at 2:05
4
\$\begingroup\$

R, 106 102 100 93 bytes

function(k,`^`=function(x,y)ifelse(r<-x%%y,y^r,y)){while({b=0:k+T;sd(T^b*(T+k)^b<2)})T=T+1;T}

Try it online!

This won't win any fastest-code bounties, but at least runs happily on TIO for the first test-case.

A lot of the code is used-up writing a gcd function (here assigned to the ^ operator for golfing motives), since 'greatest common divisor' isn't a built-in function in base R.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Julia 1.0, 60 59 51 bytes

k->(a=1;while any(gcd.((a+k)a,a:a+k).<2) a+=1end;a)

Try it online!

Thanks to MarcMush for a saved byte and to Glen O for further -8.

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ you can drop the * for -1 byte \$\endgroup\$
    – MarcMush
    Jun 27, 2021 at 9:47
  • \$\begingroup\$ Totally forgot that implicit multiplication is supported here, thanks for the tip! \$\endgroup\$
    – Kirill L.
    Jun 27, 2021 at 9:58
  • 1
    \$\begingroup\$ Note that you only care if there's a common factor between i and a*(a+k), since a*(a+k) contains all factors of a and a+k, and no new factors are introduced by multiplying them. \$\endgroup\$
    – Glen O
    Jun 28, 2021 at 0:23
  • 1
    \$\begingroup\$ Indeed, you can compress it quite nicely with any(gcd.((a+k)a,a:a+k).<2) rather than any(i->gcd(a,i)gcd(i,a+k)<2,a:a+k) to save 8 bytes. \$\endgroup\$
    – Glen O
    Jun 28, 2021 at 2:19
3
\$\begingroup\$

JavaScript (Node.js), 101 95 90 bytes

f=(k,a=0)=>[...Array(k+1)].some((_,i)=>(g=(x,y=a+i)=>y?g(y,x%y):x)(a)*g(a+k)<2)?f(k,++a):a

Try it online!

-5 thanks to Arnauld

Explanation

f = (                       // Define a function f
  k,                        // Taking a parameter k
  a = 0                     // And initialise a to 0
) => 
  [ ...Array(k + 1) ].some( // If any value i in the range 0 to k satisfies the following: 
    (_ , i) =>              // Taking a useless variable _ and the iteration i
      (g = (                // Define a helper gcd function g
          x,                // Taking a parameter x
          y = a + i         // And initialising y to a + i
        ) => 
          y ?               // If y is nonzero
            g(y,x%y)        // Take the gcd of y and x modulo y
          : x               // Otherwise yield x
      )(a)                  // And call that on a
      *                     // Multiplied by
      g(a + k)              // That called on a+k
    < 2                     // Is less than 2?
  ) 
  ? f(k,++a)                // If so (at least one is invalid), then increment a and try again
  : a                       // Otherwise (all are valid) yield a.
Improve this answer
\$\endgroup\$
1
3
\$\begingroup\$

Vyxal, 23 bytes

λD→a?+:£ṡƛ¥ġn←aġ+2>;A;ṅ

Try it Online!

-1 byte thanks to @cairdcoinheringaahing

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Looks like you can remove the space? \$\endgroup\$
    – caird coinheringaahin g ♦
    Jun 26, 2021 at 4:00
  • \$\begingroup\$ @cairdcoinheringaahing yes! I thought that space was necessary after variable definition \$\endgroup\$
    – Wasif
    Jun 26, 2021 at 4:01
3
\$\begingroup\$

Julia 1.6, 941 bytes

As it turns out, the numbers provided in the question aren't the "optimal" ones. The code provided below makes no attempt to be golfed (although I may make a pass at golfing it down soon), but rather seeks to find the smallest possible \$a\$ for any given \$k\$, as efficiently as possible.

The code here begins with the approach noted by Xash (obviously, converted to Julia), but makes some tweaks to improve the optimisation.

using Primes
function g(k)
  p=primes(k)
  Q=p[gcd.(p,k).>1]
  q=big(prod(Q))
  p=setdiff(p,Q)
  p2=big.(p)
  l=falses(k-1)
  L=copy(l)
  for i=Q
    l[i:i:end].=true
  end
  r=p.>0
  ~p=prod(p)
  n=(q*~p2)^2
  while any(r)
    L.=l
    for i=1:length(p)
      if r[i]
        L[p[i]:p[i]:end].=true
      else
        L[k%p[i]:p[i]:end].=true
      end
    end
    if all(L)
      L1=copy(l)
      for i=1:length(p)
        if r[i]
          L1[p[i]:p[i]:end].=true
        end
      end
      L2=copy(L1)
      pn=p[.!r];
      r2=pn.>0
      while any(r2)
        L2.=L1
        for i=1:length(pn)
          if r2[i]
            L2[k%pn[i]:pn[i]:end].=true
          end
        end
        if all(L2)
          P0=q*~p2[r]
          P1=~big.(pn[r2])
          m=(k*invmod(-P0,P1)%P1)*P0
          if m<n
            n=m
          end
        end
        r2.chunks.-=1
      end
    end
    r.chunks.-=1
  end
  n==(q*~p2)^2 ? Inf : n
end

Try it online! - note that, because the Primes package cannot be loaded on TIO, I have hardcoded the primes up to 200; this does not provide any substantive speed boost, as most of the time is spent in the loops.

Here are the smallest \$a\$ values for given \$k\$ values...

16 -> 2184
22 -> 3521210
34 -> 47563752566
36 -> 12913165320
46 -> 21653939146794
56 -> 172481165966593120
64 -> 808852298577787631376
66 -> 91307018384081053554
70 -> 1172783000213391981960
76 -> 26214699169906862478864
78 -> 27070317575988954996883440
86 -> 92274830076590427944007586984
88 -> 3061406404565905778785058155412
92 -> 549490357654372954691289040
94 -> 38646299993451631575358983576
96 -> 50130345826827726114787486830
100 -> 35631233179526020414978681410

TIO was able to complete this set in 57 seconds - The time required grows rapidly (indeed, exponentially) with \$k\$, though, so the next Erdos-Woods number, 106, takes more than 60 seconds on TIO on its own.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Husk, 17 bytes

ḟSμΛo←§Y⌋¹⌋³…)+⁰N

Try it online!

ḟ                   # find the first x
                N   # in the infinite list of integers
                    # that satisfies:
 Sμ          )+⁰    # hook: apply lambda function with args x and x+input
   Λ                # are all results truthy
            …       # in range arg1 to arg2 (so from x to x+input):
    o←              #   one less than
      §Y            #   maximum of
        ⌋¹          #   GCD of each element and arg1
          ⌋³        #   and GCD of each element and arg2
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.