title: Find the Erdős–Woods origin

text:
# Question
Title: Find the Erdős–Woods origin
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.

# Answer
# , 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
)

```
> 17 votes

# Answer
# 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.

---
> 12 votes

# Answer
# 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.
> 9 votes

# Answer
# 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;
        }
    }
}

```
> 6 votes

# Answer
# Python 3.8, <sup>~~263~~ ~~407~~ ~~544~~</sup> 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
```
> 5 votes

# Answer
# 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.
> 4 votes

# Answer
# 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

```
> 4 votes

# Answer
# Ruby, 60 bytes

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

```

Try it online!
> 4 votes

# Answer
# 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.
> 4 votes

# Answer
# , ~~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 .
> 4 votes

# Answer
# 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.

```
> 3 votes

# Answer
# Vyxal, 23 bytes

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

```

Try it Online!

-1 byte thanks to @cairdcoinheringaahing
> 3 votes

# Answer
# 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.
> 3 votes

# Answer
# 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

```
> 2 votes

---
Tags: code-golf, math, number-theory
---


# Question
Title: Tips on golfing this Python program to generate a palindrome from a string
I wrote this function in 48 bytes and I wonder, is there any way to write this code 2 characters shorter?

```
p=lambda n,c:(n*c)[:n//2]+(n*c)[:n//2+n%2][::-1]

```

The point of the function is to create a palindrome of length `n` by using all the characters from the string `c`. Example: `n = 3`, `c = 'ab'`. Result is `'aba'`.

Is there something I am missing that can be shortened or is there no other way to make it shorter? Thanks!

# Answer
> 6 votes
In general, slicing twice usually results in extraneous code.

Here, you use `[:n//2+n%2][::-1]`. The first part means "get from `0` to `n//2+n%2`", left-inclusive right-exclusive. The second part reverses it. Thus, what you are *actually* trying to do is get from `n//2+n%2-1` to `-1`, stepping by `-1`, left-inclusive right-exclusive. Thus, you can do `[n//2-n%2-1:-1:-1]`. The stop argument is excessive there.

```
p=lambda n,c:(n*c)[:n//2]+(n*c)[n//2+n%2-1::-1]

```

Then, since `n%2-1` gives `0` for odd numbers and `-1` for even numbers, we can also get `0` for odd numbers and `1` for even numbers via `~n%2`, and then subtract that:

```
p=lambda n,c:(n*c)[:n//2]+(n*c)[n//2-~n%2::-1]

```

(The following is found by dingledooper)

Finally, we can optimize that part even further, as what we are asking for is `n//2-1` for even numbers and `n//2` for odd numbers. Notice that if we subtract one, then `(n-1)//2` solves this. For integers, `n-1` is equivalent to `~-n` (remember that `~` is complement, and `~n == -1 - n` so `~-n == -1 + n == n - 1`). Therefore, we can shorten that part down to `[~-n//2::-1]`.

Remember the `~-` trick for decrementing (as well as `-~` for incrementing) as it saves 2 bytes for `(n+1)` and `(n-1)` where brackets would otherwise be needed, since unary operators have very high precedence.

# Python 3, 43 bytes

```
p=lambda n,c:(n*c)[:n//2]+(n*c)[~-n//2::-1]

```

Try it online!

(Thanks to Jo King for spotting this one)

If you can use Python 3.8, inline assignment with the walrus operator saves a byte:

# Python 3.8 (pre-release), 42 bytes

```
p=lambda n,c:(r:=n*c)[:n//2]+r[~-n//2::-1]

```

Try it online!

---
Tags: code-golf, tips, python, palindrome
---


title: Tips for golfing in J

text:
# Question
Title: Tips for golfing in J
GolfScript gets its own way far too often and I feel that a repository of handy hints for golfing in J might help in the fight against the evil empire. What tips do you have for making this already terse language shorter?

For those wanting to learn J, the obvious place to begin is the jsoftware site and particularly the vocabulary, the Learning J guide and the J for C programmers guide.

# Answer
> 15 votes
There are a number of subtleties to squeezing out the last few characters in J. For the following, assume that each capital letters is a primitive verb (i.e. I am removing the spaces that would otherwise be required to delimit names).

* When you have a train going, and you need to apply a function atop another partway through, `([:FLGR)` and `(LF@:GR)` have the same number of characters, but `(LF@GR)` saves one. If the frame of G is greater than or equal to the monad rank of F, this is a valid transformation. Notably, all trains have infinite rank, as do `, ,. ,: ~. /: \: [ ]` and most uses of `#` and `|.`.
* If you have to pick strings out of a list, and these strings have no spaces, use `>i{ab`cd`ef`. It's dirty, but it saves characters for each new string you have to deal with, unless you're just pulling single characters, and even then the charlist has to be length 4 to be shorter. What's happening is that undefined names are treated as references to verbs, and when you take the gerunds of those verbs you get a boxed string of the name. Any names that are already defined as having type noun, adverb, or conjunction cannot be used in this fashion, because those names get resolved before ``` can have at them.
* If you're lucky enough to have an expression to work with and not just a tacit verb, it's almost always worth it to assign any bits you reuse to variables, be they nouns, verbs, or adverbs. The parens will sometimes pay themselves back by fitting right into where you had spaces before, and most such definitions are worth it if they're reused even once more.
* Conjunctions like `(FGH)^:(u`v`w)` can be rewritten `u`v`w(FGH^:)`. This works for any length of train, even 1, though you only save anything if this trick removes parens from the right argument. This trick only works when you preload the left operand. (Have no idea what just happened? Look up 'tacit adverbs', and study the Parsing and Execution section of the J Dictionary.)
* Don't use `a.&i.`, use `u:`! `{&a.` and `3&u:` are equivalent on length, though, and the former might be more useful in a conjunction (depending on the conjunction).
* Things like `(2%~F)` and `(F%2:)` are equivalent in length. This is useful because sometimes, depending on what the rest of your train looks like, you can restructure it with `@` tricks as written in the first point, to save some desperate characters. (And of course, if `F` is `]` and the train is a monad, using `%&2` saves a char, duh.)
* Hook-like trains with `]` or `[` as the leftmost verb, e.g. `(]FGH)`.

+ `]` lets you break up a dyadic application and use the right argument only. (Swap to left with `(]FGH)~`, at a penalty of at least 1 character, maybe more.) Saves a char over `(FGH)@]`, and is very handy in gerunds!
    + `[` in a hook applied monadically allows you to do something for the side effects on the right side, then return the argument again. Most common usage is with `1!:2`, possibly with formatting junk.
* I/O sucks. Speed up the process by making loops out of everything you can. `1!:1` has rank `0`, and both of `1!:2 3` have rank `_ 0`, for example, so utilise this by making arrays of 1s and run `1!:1` directly over them. Note that `".` also has rank 1, so you can usually just put that directly after `1!:1`, too, and not have to attach it via `@` or rank shenanigans.
* It's not easy to find places to put this, but `::` can be useful.

+ `::]^:_` is a particularly powerful combination, for example, that lets you do something dangerous until you can't do it anymore. (Subject to the usual `^:_`-as-a-loop caveats.)
    + This also lets you use `{` on lists that don't have the desired index, because it throws a domain error when that happens. Useful to e.g. take the head of a list only if it exists (try using `::]` to return the empty list, or `::_1:` to return an error code, and so on).
* `]`($:@u)@.v` can usually be made shorter than `u^:v^:_`, especially on definitions of `u` and `v` that can be played around with. A similar case holds for the conditional-like `u^:(1-v)` vs. `]`u@.v`. Consider your options, especially when you have lots of named verbs floating about. It's also a little more flexible, but remember, if using `$:`, there is a recursion depth that it's easy to bump up against. (Usually something like 1800 iterations?)

# Answer
> 11 votes
**Be wary of using loops.**

While J has looping structures (`for. do. end.`, `while. do. end.` and variations), if you find yourself using them there's a possibility that your algorithm is not playing to J's golfing strengths and that there are character savings to be made.

`^:` the power conjunction is your friend. To execute a verb `x` times:

```
verb^:x

```

If you need the result of each iteration in a list:

```
verb^:(i.x)

```

You can also use `^:` to execute a verb conditionally:

```
  +:^:(3<])"0[ 1 2 3 4 5 6
1 2 3 8 10 12

```

Double `+:` if `^:` the item is greater than 3 `3<]` (the `"0` changes the rank of the verb so it works an item at a time).

# Answer
> 11 votes
The most important thing when golfing in J is to not only understand the problem, but to reduce the problem to a series of array transformations. You need to understand this way of thinking to have any success with J code.

For example, a recent challenge asked to solve the *largest subarray problem.* The stock algorithm to solve this problem is Kadane's algorithm has the following informal description:

> Go through the array and at each position and find the sum of the largest subarray ending here, which is the maximum of 0 or the value at the current index plus the sum of the largest subarray ending at the previous position. Compute the maximum of these subarrays as you go to find the largest subarray in the entire array.

A translation into imperative code is straightforward:

1. let A be the input array.
2. *h**m**i* ← 0.
3. **if** *i* ≥ len(A) **return** *m*.
4. *h* ← max(0, *h* \+ A\[*i*\]).
5. *m* ← max(*m*, *h*).
6. *i**i* \+ 1.
7. **goto** 3.

This algorithms seems complicated for J at a glance as there is an explicit loop that doesn't look like a reduction at first. If you realize what the algorithm is doing you can untangle the individual steps and see that it actually performs two simple array operations:

1. *Scan* through the array to compute the lengths of the largest subarrays ending at each index.
2. *Reduce* these lengths with the max function to find the maximum.

Now these two steps are very easy to implement in J. Here is a translation:

1. `(0 >. +)/\. y , 0` – This step operates from the other end of the array to better fit J's paradigm. `0 >. +` is tacit for `0 >. x + y`.
2. `>./ y`

Put together, we get a very terse implementation of the algorithm:

```
>./ (0 >. +)/\. y , 0

```

If you learn this way of approaching the implementation of algorithms, your solutions will be as terse as this code.

Here are some tricks I accumulated over time. This list will be expanded as I get more knowledge in J golfing.

* Learn the dictionary. It contains a lot of really obscure verbs that don't make any sense until you see how useful they are. For instance, monadic `=` is strange at first but is very useful in ASCII art challenges.
* Use dyadic `&` in tacit contexts when you want a power conjunction. The vocabulary suggests `u@[&0` as a tacit replacement to `4 : 'u^:x y` and so do I.
* In many cases you can avoid a `[:` or `@:` in a sequence like `u@v` by choosing a variant of `u` that has a left argument. For instance, to drop the first item of the result of `v`, use `1}.v` instead of `[:}.v` if `}.@v` isn't possible for some reason.
* `] v` is often shorter than `v@]` if you want to use monadic `v` in a dyadic context. This comes in useful especially when `v` is a long train of verbs.
* Sometimes you can write `m (n v w) y` instead of `(n v m&w) y`. This may make it possible to avoid spaces and parentheses.
* `#\` instead of `>:@i.@#`.
* `u &. v` is useful when `v` has an obverse. When not, you might want to use `[: vinv u & v` or `u & (v :. vinv)` instead.
* Understand rank and how to use it. Try to fiddle around with the rank conjunction until you get something that fits. It helps understanding how rank influences your code.
* `^:_` is extremely useful for algorithms where you want to reach convergence, like a flood-fill or simulations.
* Know your standard library. It contains very useful functions that save you tons of characters.
* The copulæ `=.` and `=:` can be embedded anywhere in a phrase. Use this to make one-liners where tacit notation isn't enough.
* Use monadic `,` instead of multiple reductions when reducing multi-dimensional arrays.
* Understand what phrases are supported by special code when the challenge imposes runtime boundaries. Some useful things operate in O(*n*) instead of O(*n*<sup>2</sup>) counter-intuitively.
* Boxes are useful for trees.

# Answer
> 10 votes
**Input**

`1!:1[1` will take one line of input terminated by pressing the enter key.

`1!:1[3` will take a number of lines of input (terminated by Ctrl-D on my Mac, Ctrl-C on Windows).

If you're trying to input numbers, using `".` will evaluate the string and return a list of numbers ready to be manipulated. If you're taking in one number but need to operate on the digits individually, `".,.` (thanks to Jan Dvorak's comment for this) or `"."0` will split the string into separate digits:

```
   "."0[1!:1[1
12345
1 2 3 4 5

   ".,.1!:1[1
12345
1 2 3 4 5

```

If you're reading in strings, the shortest way to get a boxed list of separate strings is to use `;:`. This works best for space separated strings:

```
   ;:1!:1[1
hello world
┌─────┬─────┐
│hello│world│
└─────┴─────┘

```

# Answer
> 6 votes
Consider using explicit definition instead of writing a tacit verb; sure the `3 :'` and `'` cost 5 bytes, but you can save a lot of `@`, `@:` and `[:` that way.

# Answer
> 6 votes
## Using iteration to compute sequences

Typically, solving an OEIS sequence challenge will require using one of the formulas given on its page. Some of these adapt well for J, and others not so much. Recursive formulas are straight-forward, however, iteration might not be simple. A pattern I've begun to use is

```
(s(]f)^:[~]) n
          ]  Gets n
 s           The first value in the sequence
         ~   Commute the argument order, n is LHS and s is RHS
        [    Gets n
      ^:     Nest n times with an initial argument s
  (]f)         Compute f s
             Returns (f^n) s

```

where `s` is the first value in the sequence, `f` is a verb that will compute the next term given the previous term, and `n` is the zero-based index of the term you want to compute. This method relies on the fact that when computing the power of a dyad, the LHS is bound to the dyad to form a new monad, and that monad is nested on the initial value. The dyad given to the power adverb is a hook where `(]f)` is given the index `n` on the LHS and the value of a term in the sequence `s`. The hook will apply `f` on `s` as a monad, and then ignore `n` to return the result of `f s`.

## Standard library

Sometimes, you might find that J will have support for a verb in its standard library. For example, most of the bitwise integer operations are bound to names which are shorter than using the primitive call.

```
AND =: (17 b.) NB. it is actually '$:/ :(17 b.)'

```

Date and time builtins are also available.

## Ranges

If you have a set of values `[a, b, c]` and you want to form a range based on their product like `[0, 1, 2, ..., a*b*c-1]`, the typical approach would be to find their product and then form a range which might be `[:i.*/` which costs 6 bytes. A shorter way is `,@i.` for 4 bytes since `i.` can form multidimensional arrays while still counting up, and flattening it will produce an equivalent range.

# Printing continuously

A tacit way to print a value and continue to use it without an explicit loop is `([echo)` for a monadic case. `echo` is a verb in the standard library that prints its contents to `stdout` in the same format used in the interpreter. The hook then passes the same input value out using the left `[` verb.

# Base 10 digits of an integer

The standard way of acquiring the base 10 digits of an integer is `10#.inv]` which costs 8 bytes, too much! An alternative is to convert it to a string and parse it at rank 0 `"."0@":` which saves a byte, but an even better way is `,.&.":` which saves another byte making the final cost 6 bytes instead of 8.

# Answer
> 6 votes
# Shorter ways to mess with ranks

Sometimes, you'll have code like `<"0 i.3 3`, where you want to apply a verb `v` at rank `r`. However, if you use a noun (like `0`), you'll often have to include a space. To avoid this, you can use another verb `u` of equivalent rank and use `u"v` instead. For example, since `+` has rank `0 0 0`, we can use `<"+` instead of `<"0`.

Here is a table of all verbs and their ranks (obtainable by using `v b. 0`):

```
0 0 0     > + * - % ^ | ! ? <. <: >. >: +. +: *. *: %: ^. j. o. q: r.
0 _ _     -. -: E. i: p:
1 0 1     p..
1 0 _     { A.
1 1 0     p.
1 1 1     #.
1 1 _     C.
1 _ _     ;: ". i. I.
2 _ 2     %.
_ 0 0     = < ~. ~: {: }: ?. L.
_ 1 0     #:
_ 1 _     $ # |. |: {. }. ": {::
_ _ _     , ; [ ] _: $. $: ,. ,: /: \: [: e. s: u: x: 0:

```

To use this table, find the desired rank `r` on the left hand side, then choose an appropriate verb `v` from the right hand side. E.g., if I need to vectorize a verb `v` at depth `2 _ 2`, then I find that rank on the left and choose `%.` from the right. Then I use `v"%.` instead of `v"2 _ 2`.

# Answer
> 5 votes
# Some (fairly) common tricks I've seen

I'm sharing a few things that have come in handy for me. Basically all of these are tips I've received myself, but I don't have credits for most.

### Sum of a rank one array

Instead of using `+/@:(FGH)` use `(1#.FGH)`. This means debase to base 1, which effectively means summing an array. Although it's longer than `+/`, it doesn't require a cap or composition, which often makes it much shorter than using `+/`.

### Counting trailing truths

If you have a boolean list and you want to count the number of trailing truths, use `#.~`. See here. The APL answer provides a good explanation for how this works. Granted, this has only been helpful to me twice but I figured I'd share it anyways.

### Under (&.)

Not a specific trick, but just a general suggestion: the adverb `&.`-under often leads to elegant and (more importantly) short solutions. Keep it in mind when you're golfing.

Often times it's useful for and other base conversion challenges, e.g. this code which removes the most significant bit from a number: `}.&.#:` (convert to list of binary digits, remove the first digit, then undo the conversion to a list of binary digits and convert back to decimal). The straightforward solution is two more bytes: `#.@}.@#:`.

Under is also helpful for challenges where you need to work with decimal digits, since you can use `u&.":`. For example, the short way miles gives to split to decimal digits uses under: `,.&.":`.

A final example is finding the magnitude of a vector: `+/&.:*:`, note that you need to collect all of the results from `*:`-square with `&.:`-under since `*:`-square is rank zero.

# Answer
> 5 votes
# Tacit programming

## Basics

### Dyadic verb

```
x (F G H) y == (x F y) G (x H y)
x (F G) y == x F (G y)
x ([: G H) y == G (x H y)  NB. G is called monadically

NB. Verbs are grouped from the right by units of 3.
NB. For the following, think like G, I, K are replaced by the results of (x G y) etc.
NB. and then the sentence is run as usual.
x (F G H I J K) y == x (F (G H (I J K))) y
                  == x F ((x G y) H ((x I y) J (x K y)))

NB. Using conjunctions for dyadic verb
x F@G y == F (x G y)  NB. Atop; Same as x ([: F G) y; Consider as golfing alternatives
x F&G y == (G x) F (G y)  NB. Compose; G is applied monadically to both arguments

```

### Monadic verb

```
(F G H) y == (F y) G (H y)
(G H) y == y G (H y)  NB. Note that this is different from APL
([: G H) y == G (H y)
(F G H I J K) y == (F (G H (I J K))) y
                == y F ((G y) H ((I y) J (K y)))
F@G y == F (G y)

```

### Misc

```
x&F y == x F y
F&y x == x F y
y F~ x == x F y
F~ y == y F y

```

## Tricks

### `(F x) G (H y)`

Tacit solution: `(G~F)~H`; depending on the actual verbs, consider rearranging the left and right arguments to remove `~`.

```
x ((G~F)~H) y
x (G~F)~ (H y)
(H y) (G~F) x
(H y) G~ (F x)
(F x) G (H y)

```

### Monadic-Dyadic replacements

```
>:y == 1+y
<:y == 1-~y or _1+y
+:y == 2*y
-.y == 1-y
-:y == 2%~y
*:y == 2^~y
#.y == 2#.y
#.inv y == 2#.inv y  NB. #: doesn't work this way
{.y == 0{y
{:y == _1{y
}.y == 1}.y
+/y == 1#.y  NB. Vectors only
+/"1 y == 1#.y  NB. Higher-dimension arrays

```

# Answer
> 3 votes
# `strings` library: golfing tips

The strings library is vastly helpful for doing anything with string manipulation. Sure, it takes `include'strings'` (which is very costly, considering J), but you may at times reap the benefits.

## `stringreplace`

Find yourself using string replace? Observe that `A stringreplace B` is the same as `B rplc A`.

In fact, this is how `rplc` is implemented:

```
   rplc
 stringreplace~

```

## `cuts`

The verb `cuts` provides thus:

> ```
> cut y at x (conjunction)
> string (verb cuts n) text
>   n=_1  up to but not including string
>   n= 1  up to and including string
>   n=_2  after but not including string
>   n= 2  after and including string
> ```

So it's really slicing a string.

# Answer
> 3 votes
### Getting numbers from 0 to 4

If there’s a restriction on using numbers in your code:

**0** `%_`: one divided by infinity.
**1** `#_`: how many infinities?
**2** `#_ _`: two infinities.
**3** `verb`: there’s a built-in.
**4** `dyad`: another built-in.

### Getting numbers from 10 to 35

Base-inifinity literals: **11**:`_bb`, **26**:`_bq` etc.

# Answer
> 3 votes
# Miscellaneous ideas

Cross-post of my own APL tip, because APL and J are so closely related that the two can share many ideas.

## If you're facing `[:-~/`, use `_1#.` instead

A common reason to use `-~/` is to reverse-subtract over a length-2 axis, e.g. given a 2-element array `x y`, compute `y-x`.

If this is the case, `_1#.` is an equivalent expression; just like `2#.x y` computes `2x+y`, `_1#.x y` computes `-x+y`. While `-~/` most likely requires the use of `[:` (capped fork) or `@` (atop), `_1#.` is likely to fit just well in trains as-is.

Note that, if you apply it to longer axis, `_1#.` gives you more similar result to `-/` (alternating sum), with negated result when the length is even.

## Construct a boolean square matrix where the border is ones/zeros and the interior is the opposite

This is mainly for large fixed-size matrices, say 6 by 6.

The matrix

```
1 1 1 1 1 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

```

can be generated by `+./~` -ing the boolean vector `1 0 0 0 0 1`. The shortest known way to generate that vector is `#:33`, so we can get the matrix above in just **8 bytes**:

```
+./~#:33

```

If we're to put this in a train, a constant function `+./~@#:@33` and parenthesized noun left arg `(+./~#:33)` have equal length of **10 bytes**. The two forms have their own pros and cons: the former can be placed at the right end of a train, while the latter may serve better by not messing up with something that comes on its right (e.g. `33e.` is a syntax error).

We can also get negation of it at no extra cost, by swapping `+.` with `+:`! (Remember that J, like APL, has NOR `+:` and NAND `*:`; they are rarely needed, but definitely are a byte saver when we do need them.)

# Answer
> 2 votes
# `&` is your friend, use it wisely

`v` is a verb, `n` is a noun, `x` and `y` are left and right arguments, respectively.

### Monad `&`: Introduce `~` inside adverb/conjunction chain

An adverb/conjunction chain evaluates from the left. So something like `_2&+/\&.>` won't work because it parses like `(_2&+)/\&.>` while we want `_2&(+/\)&.>`. In this case, swapping the left/right of `+/\` can save a byte, as in `+/\~&_2&.>` because this one parses as `((+/\)~)&_2&.>`. To see why this works:

```
+/\~&_2 y
is equivalent to
y +/\~ _2
is equivalent to
_2 +/\ y
is equivalent to
_2&(+/\) y

```

### Dyad `&`: Repeat `x` times

Did you know that if you give a left argument `x` to `&`, the function applies it `x` times to `y`? Quite a few challenges ask you to do certain operation `x` times. It is mainly achievable in two ways:

* Use the power operator `^:` without right operand

If the operation is `v`, then `v^:` becomes an adverb train that, when given a left operand, becomes a monadic verb. So `v` is applied to `y`, `x` times.

```
x(v^:)y
is equivalent to
(v^:x)y

```
* Use the dyadic `&` as the outermost conjunction

To use this, you need to identify a constant `n` and a dyadic verb `u`, so that either `n u y` or `y u n` is equivalent to `v`. Then you can write `n&u` or `u&n` to solve the entire task. This form is most effective when the choice of the constant is obvious, e.g. 3 in `3 u:` (convert chars to ASCII values).

Also, `u&n` is slightly preferred over `n&u` when the outermost structure of `u` is a conjunction or adverb (in which case `n&u` should be `n&(u)`; you can do `u~&n` instead).

Note that you can place the dyadic `&` anywhere in a train to achieve repeating arbitrary function to arbitrary argument, in the similar sense to dynamic `^:`.

# Answer
> 2 votes
# `x$y` does something different than you think

Dyadic `$` is called *reshape*. If you're coming from APL, you'd know  under the same name which lists down all elements of `y` before creating the `x`-shaped array.

J handles it differently: it does not flatten `y`; instead it uses `y`'s items, or major cells, to fill in each cell of the `x`-shaped array. So the resulting shape becomes `x,}.$y`. It doesn't look very useful by this description.

There is one use case where this becomes useful in code golf: when `x` is a positive singleton. Then `x$y` acts like a **take** or **repeated overtake**.

* When `x <: #y` (`x` is smaller than or equal to length of `y`), the result of `x $ y` is exactly same as `x {. y`, directly shaving one byte no matter what. The verb ranks are identical (`1 _`), so the replacement is safe even in a rank-sensitive context (e.g. `@`/`&`).
* When `x > #y`, the result becomes `y` cyclically extended to length `x`. This is different from `x {. y` (which would fill the missing places with zeros/blanks), but it could have its own uses.

Note that, in both cases, the result *is* equivalent to using the individual elements to fill in `x,}.$y`-shaped array.

# Answer
> 2 votes
# Know (and abuse) J's truthy/falsy ()

When truthy/falsy is not defined by the language spec, it is defined as the one that is accepted by an `if` statement. Truthy ones are those that make the `if` clause run, and falsy ones are the opposite.

Unlike APL (where only 1/0 are truthy/falsy respectively), J is quite liberal. J's `if.` clause accepts any array, and evaluates to falsy if and only if the array is nonempty and its first atom is a numeric zero. Any other arrays (including empty arrays, character or boxed arrays) are truthy.

Demonstration:

```
f =: 3 : 0
if. 0         do. echo 'yes 0' end.
if. 1         do. echo 'yes 1' end.
if. 2         do. echo 'yes 2' end.
if. 0 1 2 3 4 do. echo 'yes 3' end.
if. 2 0 0 1 3 do. echo 'yes 4' end.
if. 0$0       do. echo 'yes 5' end.
if. 'abcd'    do. echo 'yes 6' end.
if. '';'def'  do. echo 'yes 7' end.
)
f ''

```

Output:

```
yes 1
yes 2
yes 4
yes 5
yes 6
yes 7

```

`yes 0` and `yes 3` were not printed because the array is nonempty and the first element is zero. Having zeros at any other positions does not affect the truthy/falsy interpretation. Try it online!

---
Tags: code-golf, tips
---


# Question
Title: How many bead arrangements on the abacus?
Your toy in this challenge is a special abacus of 4 rows and 8 positions per row. There's one bead on the first row, 2 beads on the 2nd row, 3 beads on the 3rd row and 4 beads on the 4th row. Beads on a same row are glued together, which means that they can only be moved as a block.

Below is a valid configuration of the abacus:

```
---O----
------OO
-OOO----
---OOOO-

```

Of course, a block cannot be moved beyond the edges of the abacus. So there are 8 possible positions for the block on the first row and only 5 for the block on the last row.

## Task

You'll be given a list of 8 non-negative integers representing the total number of beads in each column of the abacus. Your task is to output the number of configurations that lead to this result.

## Examples

If the input is \\$\[4,3,2,1,0,0,0,0\]\\$, the only possible way is to put all blocks at the leftmost position:

```
O-------
OO------
OOO-----
OOOO----
________
43210000

```

If the input is \\$\[1,0,0,1,2,3,2,1\]\\$, there are **2** possible configurations:

```
O-------    O-------
----OO--    -----OO-
-----OOO    ---OOO--
---OOOO-    ----OOOO
________    ________
10012321    10012321

```

If the input is \\$\[1,1,1,2,2,2,1,0\]\\$, there are **13** possible configurations. Below are just 4 of them:

```
O-------    ---O----    ---O----    ------O-
-OO-----    ----OO--    ----OO--    OO------
---OOO--    OOO-----    ----OOO-    ---OOO--
---OOOO-    ---OOOO-    OOOO----    --OOOO--
________    ________    ________    ________
11122210    11122210    11122210    11122210

```

## Rules

* You can assume that the input is valid: all values are in \\$\[0\dots4\]\\$, their sum is \\$10\\$ and at least one configuration can be found.
* You can take the input list in any reasonable format (array, string of digits, etc.).
* Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[4,3,2,1,0,0,0,0] -> 1
[1,1,1,2,0,2,2,1] -> 1
[1,0,0,1,2,3,2,1] -> 2
[1,1,2,2,2,1,0,1] -> 3
[0,2,2,2,2,2,0,0] -> 4
[0,0,0,1,2,2,3,2] -> 5
[1,1,1,1,1,1,2,2] -> 6
[0,2,2,2,2,1,1,0] -> 8
[1,1,1,2,2,1,1,1] -> 10
[1,1,2,2,2,1,1,0] -> 12
[1,1,1,2,2,2,1,0] -> 13

```

# Answer
> 5 votes
# Jelly, 15 bytes

```
żJØ.xⱮS
8Ḷṗ4Ç€ċ

```

Try it online!

Takes input without trailing zeros.

## Explanation

```
żJØ.xⱮS Auxiliary monadic link, taking a list of 4 integers
ż       Zip with
 J        indices: [1,2,3,4]
    x   Repeat
  Ø.      [0,1]
          [a,b] times respectively
     Ɱ    for each [a,b] in the list
      S Sum

8Ḷṗ4Ç€ċ Main monadic link, taking a list of integers
8       8
 Ḷ      Lowered range: [0,1,2,3,4,5,6,7]
  ṗ4    Cartesian 4th power
    Ç   Apply the auxiliary link
     €    to each
      ċ Count the occurences of the input

```

# Answer
> 4 votes
# MATL, ~~33~~ ~~32~~ ~~31~~ 25 bytes

```
8:KZ^!"8:@<1M-K:!<<sGX=vs

```

Try it online! (but it takes around 50 seconds, and it sometimes times out).

### Explanation

The code `8:` generates the vector `[1 2 ··· 8]`. `K` pushes `4`, `Z^` computes the Cartesian power, and `!` transposes. So this gives the following matrix, of size `4`×`4096`:

```
[1 1 ··· 8 8;
 1 1 ··· 8 8;
 1 1 ··· 8 8;
 1 2 ··· 7 8]

```

Each column represents a possible abacus configuration, defined by the position of the leftmost bead in each row. Some configurations are impossible (for example, values above `5` in the last row are not allowed), but this isn't a problem because the result computed from these configurations will never coincide with the input.

The loop `"` takes each column of this matrix. `8:` pushes `[1 2 ··· 8]` onto the stack, and `@` pushes the current column, say `[1; 1; 1; 1]` in the first iteration. `<` compares these two vectors, of sizes 1×8 and 4×1, element-wise with singleton expansion. This gives a 4×8 matrix with all the comparisons, in this case (\*)

```
[0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0]

```

Then, `1M` pushes the two vectors again and `-` subtracts them element-wise with singleton expansion. This gives, in this case

```
[0 1 2 3 4 5 6 7;
 0 1 2 3 4 5 6 7;
 0 1 2 3 4 5 6 7;
 0 1 2 3 4 5 6 7]

```

`K:!` pushes the column vector `[1; 2; 3; 4]`, and `<` compares the previous matrix with this vector, again element-wise with singleton expansion. The result is (\**)

```
[1 0 0 0 0 0 0 0;
 1 1 0 0 0 0 0 0;
 1 1 1 0 0 0 0 0;
 1 1 1 1 0 0 0 0]

```

Now `<` compares matrices (\*) and (\**) element-wise. The result will give `1` at entries where the first matrix has a `0` and the second has a `1`. The result represents the beads in the abacus for the current configuration:

```
[1 0 0 0 0 0 0 0;
 1 1 0 0 0 0 0 0;
 1 1 1 0 0 0 0 0;
 1 1 1 1 0 0 0 0]

```

`s` computes the sum of each column: `[4 3 2 1 0 0 0 0]`. Then `GX=` compares this with the input vector. (Note that non-valid abacus configurations such as `[8; 8; 8; 8]` will produce less then `10` entries equal to `1` in the matrix above, and so will never give a result matching the input.) The result is `1` if both vectors are equal or `0` otherwise. `vs` adds this to the accumulated sum of previous iterations.

The final sum is implicitly printed at the end.

# Answer
> 4 votes
# , 42 41 40 bytes

*-1 thanks to Jonah!*

```
1#.(1680+/@((#:~8&-)I.@,.1+])"{&i.4)e.,:

```

Try it online!

* `1680 f"{&i. 4` for each `i` in `0…1679` and `0 1 2 3` run …
* `(#:~8&-)` `i` mixed-base-converted with bases `8 - 0 1 2 3 = 8 7 6 5` so we get every possible configuration, f.e. `2 1 0 1`.
* `,.1+]` append item-wise `1 + 0 1 2 3 = 1 2 3 4`: `2 1, 2 2, 0 3, 1 4`.
* `I.@` for each pair, take that many 0s and 1s (`_` filled with 0s):

```
2 1: 0 0 1 _ _
2 2: 0 0 1 1 _
0 3: 1 1 1 _ _
1 4: 0 1 1 1 1

```
* `+/@` sum `1 2 4 2 1` – because we get every possible configuration, J automatically pads the arrays to length of 8.
* `1#. … e.,:` count the occurrences of the input.

# Answer
> 4 votes
# Python 3, 72 bytes

```
f=lambda a,n=4:n==a or sum(f(a-int(n*"1"+i*"0"),n-1)for i in range(n*8))

```

Try it online!

---

# Python 2, 75 bytes

```
[sum(int(-~j*"1"+n/8**j%8*"0")for j in range(4))for n in range(8**4)].count

```

Try it online!

This is an expression evaluated to an unnamed function. You can assign it to `f` by prepend `f=`, and then use it as `f(43210000)`. It takes input as a single integer. For example, `[4,3,2,1,0,0,0,0]` becomes `43210000` while `[0,0,0,1,2,2,3,2]` becomes `12232`.

It is interesting that you don't need `lambda` nor `def` to define a function in Python.

# Answer
> 3 votes
# Haskell, 88 bytes

```
0#t=[1|all(==0)t]
m#t=do k<-[0..7];(m-1)#[r-sum[1|j>k,j<=k+m]|(j,r)<-zip[1..]t]
sum.(4#)

```

Try it online!

# Answer
> 3 votes
# Charcoal, ~~32~~ 26 bytes

```
Ｉ№Ｅ×³φΣＥ⁴×Ｘχ﹪÷ιＸ⁸λ⁸÷Ｘχ⊕λ⁹Ｎ

```

Try it online! Link is to verbose version of code. Takes input as a string of 8 digits. Explanation: Simply generates the column sums of all configurations and counts the number that match.

```
  Ｅ×³φ                      Consider 3,000 configurations
       Ｅ⁴                   Consider 4 rows
                   ÷Ｘχ⊕λ⁹   Row mask
         ×                  Multiplied by
          Ｘχ                Shift given by
            ﹪÷ιＸ⁸λ⁸         Current base 8 digit
      Σ                     Take the (column) sum
 №                          Count matches of
                         Ｎ  Input cast to integer
Ｉ                           Cast to string
                            Implicitly print

```

There are only 1680 true configurations but without mixed base conversion they won't be consecutive; in base 8 the last configuration is 2423 but obviously 3000 is golfier (any value up to 4096 would work). The row mask is simply a string of `1`s representing the `O`s, with a shift that represents the number of trailing `0`s representing the `-`s (the leading `-`s are implied). Since the column sums won't be higher than 4 the masks can simply be added as decimal integers (golfier than base 5 of course). False configurations will result in a value greater than 43,210,000 so they which will never match a legal input value.

# Answer
> 2 votes
# Jelly, 13 bytes

Started looking for ways to golf xigoi's great Jelly answer but it took a fair bit of effort so thought I'd post instead.

```
8ṗ4+"JḶ$ṬSƲ€ċ

```

A monadic Link that accepts the list (using the no-trailing zeros option) and yields the count.

**Try it online!**

### How?

```
8ṗ4+"JḶ$ṬSƲ€ċ - Link: list of non-negative integers, Totals
8             - eight
  4           - four
 ṗ            - ([1..8]) Cartesian power (4) -> all length 4 lists using [1..8]
           €  - for each (list of four "start indices", I, in that):
          Ʋ   -   last four links as a monad - f(I):
       $      -     last two links as a monad - g(I):
     J        -       range of length -> [1,2,3,4]
      Ḷ       -       lowered range -> [[0],[0,1],[0,1,2],[0,1,2,3]]
    "         -     (I) zip (that) with:
   +          -       addition -> [[0+i1],[0+i2,1+i2],[0+i3,1+i3,2+i3],[0+i4,1+i4,2+i4,3+i4]]
        Ṭ     -     un-truth -> [[0...0,1],[0...0,1,1],[0...0,1,1,1],[0...0,1,1,1,1]]
                                (number of zeros being i1-1, i2-1, i3-1, and i4-1 respectively)
         S    -     sum (column-wise)
            ċ - count occurrences (of the input list, Totals)

```

# Answer
> 2 votes
# Haskell, 58 bytes

```
(1111%)
0%0=1
0%_=0
k%n=sum[div k 10%(n-k*10^i)|i<-[0..7]]

```

Try it online!

`(1111%)` is the main function. It takes input as an integer, e.g. `(1111%) 11122210 == 13`.

This essentially counts solutions to $$1111a+111b+11c+d=n$$ where \\$a,b,c,d\\$ range over \\$10^0, 10^1 \dots 10^7\\$.

# Answer
> 1 votes
# Python 3, 136 bytes

Takes input as an integer (i.e. no leading zeroes). Generates all possible configurations of the abacus, filters down to only those matching the input, returns the count. Loses 23 byes on the itertools import.

```
lambda n:sum([x==n for x in map(sum,product(*([int('1'*i+'0'*(8-j-i))for j in range(9-i)]for i in range(1,5))))])
from itertools import*

```

Try it online!

# Answer
> 1 votes
# Vyxal `R`, 23 bytes

```
8:Ẋ:Ẋvfƛ‹↵\1dd¦vI*∑⁰=;∑

```

Try it Online!

A messy attempted port of Lynn's answer.

---
Tags: code-golf, array
---