Return to Answer

For $n=\{{6,7,8}\}$, it take about $\{{1.43,\;19.69,\;860.85}\}$ seconds.
When $n=9$, it doesn't finished for $4$ hours, I terminate it.

Still very slow, I tried to convert all the patterns to C code, it's not difficult, the generated C code is more than 5,700 lines, the efficiency improvement is very obvious.

n=9; gps=Block[{i=1,j=1},Groupings[Table[x,n],f->2]/. {f:>(F[#,Symbol["i"<>ToString@Mod[i++,n-1,1]],#2]&),x:>Symbol["n"<>ToString[Mod[j++,n,1]]]}]; gen=StringTemplate["if(check1(``)){ sprintf(buffer, \"``\\n\", ``); if(check2(buffer)) printf(\"%s\", buffer); }"][ToString@CForm@#, StringReplace[ToString@#,{"F"|", "->"","["->"(","]"->")", "n"~~DigitCharacter:>"%d","i"~~DigitCharacter:>"%c"}], StringReplace[StringRiffle[#//.F[x___]:>{x}//Flatten,","],"i"->"o"] ]&/@gps//StringRiffle[#,"\n"]&; src="#include <stdio.h> #include <math.h> #include <string.h> #include <time.h> #define NUM 100 #define N 6 #define EPS 1e-8 char ops[N] = {'+', '-', '*', '/', '#', '@'}; char buffer[128]; double F(double x, int op, double y) { double arr[] = {x + y, x - y, x * y, x / y, 10 * x + y, -x + y}; return arr[op]; } int check1(double x) { return fabs(x - NUM) < EPS || fabs(x + NUM) < EPS; } int check2(char buffer[]) { return (!strstr(buffer, \"#(\") && !strstr(buffer, \")#\")); } void calc(int a[]) { int len = 0; int n1 = a[0], n2 = a[1], n3 = a[2], n4 = a[3], n5 = a[4], n6 = a[5], n7 = a[6], n8 = a[7], n9 = a[8]; #pragma omp parallel for schedule(dynamic) reduction(+:buffer) for (int i1 = 0; i1 < N; i1++) { for (int i2 = 0; i2 < N; i2++) for (int i3 = 0; i3 < N; i3++) for (int i4 = 0; i4 < N; i4++) for (int i5 = 0; i5 < N; i5++) for (int i6 = 0; i6 < N; i6++) for (int i7 = 0; i7 < N; i7++) for (int i8 = 0; i8 < N; i8++) { char o1 = ops[i1], o2 = ops[i2], o3 = ops[i3], o4 = ops[i4], o5 = ops[i5], o6 = ops[i6], o7 = ops[i7], o8 = ops[i8]; `` } } } int main() { clock_t t0 = clock(); freopen(\"output.txt\", \"w\", stdout); int a[] = {1,2,3,4,5,6,7,8,9}; calc(a); printf(\"Elapsed time: %g sec\\n\", (clock() - t0) / (double) CLOCKS_PER_SEC); return 0; } "; Export["main.c",TemplateApply@StringTemplate[src,gen],"Text"] Run["gcc -Og main.c -fopenmp"] Run["a.exe"] // AbsoluteTiming list=ReadList["output.txt","String"] list // Most // Length LeftTeeArrow[x_,y_]:=-x+y; ans=ToExpression[StringReplace[Most@list,{"#"->"","@"->"~LeftTeeArrow~"}],InputForm,HoldForm] ReleaseHold[ans]//Union 

For $n=\{{6,7,8}\}$, it take about $\{{1.43,\;19.69,\;860.85}\}$ seconds.
When $n=9$, it doesn't finished for $4$ hours, still very slow, I terminate it.

I tried to convert all the patterns to C code, it's not difficult, the generated C code is more than 5,700 lines, the efficiency improvement is very obvious.

n=9; gps=Block[{i=1,j=1},Groupings[Table[x,n],f->2]/. {f:>(F[#,Symbol["i"<>ToString@Mod[i++,n-1,1]],#2]&),x:>Symbol["n"<>ToString[Mod[j++,n,1]]]}]; gen=StringTemplate["if(check1(``)){ sprintf(buffer, \"``\\n\", ``); if(check2(buffer)) printf(\"%s\", buffer); }"][ToString@CForm@#, StringReplace[ToString@#,{"F"|", "->"","["->"(","]"->")", "n"~~DigitCharacter:>"%d","i"~~DigitCharacter:>"%c"}], StringReplace[StringRiffle[#//.F[x___]:>{x}//Flatten,","],"i"->"o"] ]&/@gps//StringRiffle[#,"\n"]&; src="#include <stdio.h> #include <math.h> #include <string.h> #include <time.h> #define NUM 100 #define N 6 #define EPS 1e-8 char ops[N] = {'+', '-', '*', '/', '#', '@'}; char buffer[128]; double F(double x, int op, double y) { double arr[] = {x + y, x - y, x * y, x / y, 10 * x + y, -x + y}; return arr[op]; } int check1(double x) { return fabs(x - NUM) < EPS || fabs(x + NUM) < EPS; } int check2(char buffer[]) { return (!strstr(buffer, \"#(\") && !strstr(buffer, \")#\")); } void calc(int a[]) { int len = 0; int n1 = a[0], n2 = a[1], n3 = a[2], n4 = a[3], n5 = a[4], n6 = a[5], n7 = a[6], n8 = a[7], n9 = a[8]; #pragma omp parallel for reduction(+:buffer) for (int i1 = 0; i1 < N; i1++) { for (int i2 = 0; i2 < N; i2++) for (int i3 = 0; i3 < N; i3++) for (int i4 = 0; i4 < N; i4++) for (int i5 = 0; i5 < N; i5++) for (int i6 = 0; i6 < N; i6++) for (int i7 = 0; i7 < N; i7++) for (int i8 = 0; i8 < N; i8++) { char o1 = ops[i1], o2 = ops[i2], o3 = ops[i3], o4 = ops[i4], o5 = ops[i5], o6 = ops[i6], o7 = ops[i7], o8 = ops[i8]; `` } } } int main() { clock_t t0 = clock(); freopen(\"output.txt\", \"w\", stdout); int a[] = {1,2,3,4,5,6,7,8,9}; calc(a); printf(\"Elapsed time: %g sec\\n\", (clock() - t0) / (double) CLOCKS_PER_SEC); return 0; } "; Export["main.c",TemplateApply@StringTemplate[src,gen],"Text"] Run["gcc -Og main.c -fopenmp"] Run["a.exe"] // AbsoluteTiming list=ReadList["output.txt","String"] list // Most // Length LeftTeeArrow[x_,y_]:=-x+y; ans=ToExpression[StringReplace[Most@list,{"#"->"","@"->"~LeftTeeArrow~"}],InputForm,HoldForm] ReleaseHold[ans]//Union 

Finally, the program takes about $10$ seconds to finds $422716$ distinct solutions, same result as whuber.

n=9; gps=Block[{i=1,j=1},Groupings[Table[x,n],f->2]/. {f:>(F[#,Symbol["i"<>ToString@Mod[i++,n-1,1]],#2]&),x:>Symbol["n"<>ToString[Mod[j++,n,1]]]}] gen=StringTemplate["if(check1(``)){ sprintf(buffer, \"``\\n\", ``); if(check2(buffer)) printf(\"%s\", buffer); }"][ToString@CForm@#, StringReplace[ToString@#,{"F"|", "->"","["->"(","]"->")", "n"~~DigitCharacter:>"%d","i"~~DigitCharacter:>"%c"}], StringReplace[StringRiffle[#//.F[x___]:>{x}//Flatten,","],"i"->"o"] ]&/@gps//StringRiffle[#,"\n"]&; src="#include <stdio.h> #include <math.h> #include <string.h> #include <time.h> #define NUM 100 #define N 6 #define EPS 1e-8 char ops[N] = {'+', '-', '*', '/', '#', '@'}; char buffer[128]; double F(double x, int op, double y) { double arr[] = {x + y, x - y, x * y, x / y, 10 * x + y, -x + y}; return arr[op]; } int check1(double x) { return fabs(x - NUM) < EPS || fabs(x + NUM) < EPS; } int check2(char buffer[]) { return (!strstr(buffer, \"#(\") && !strstr(buffer, \")#\")); } void calc(int a[]) { int len = 0; int n1 = a[0], n2 = a[1], n3 = a[2], n4 = a[3], n5 = a[4], n6 = a[5], n7 = a[6], n8 = a[7], n9 = a[8]; #pragma omp parallel for schedule(dynamic) reduction(+:buffer) for (int i1 = 0; i1 < N; i1++) { for (int i2 = 0; i2 < N; i2++) for (int i3 = 0; i3 < N; i3++) for (int i4 = 0; i4 < N; i4++) for (int i5 = 0; i5 < N; i5++) for (int i6 = 0; i6 < N; i6++) for (int i7 = 0; i7 < N; i7++) for (int i8 = 0; i8 < N; i8++) { char o1 = ops[i1], o2 = ops[i2], o3 = ops[i3], o4 = ops[i4], o5 = ops[i5], o6 = ops[i6], o7 = ops[i7], o8 = ops[i8]; `` } } } int main() { clock_t t0 = clock(); freopen(\"output.txt\", \"w\", stdout); int a[] = {1,2,3,4,5,6,7,8,9}; calc(a); printf(\"Elapsed time: %g sec\\n\", (clock() - t0) / (double) CLOCKS_PER_SEC); return 0; } "; Export["main.c",TemplateApply@StringTemplate[src,gen],"Text"] Run["gcc -O2 main.c -fopenmp"] Run["a.exe"] // AbsoluteTiming list=ReadList["output.txt","String"] list // Most // Length LeftTeeArrow[x_,y_]:=-x+y; ans=ToExpression[StringReplace[Most@list,{"#"->"","@"->"~LeftTeeArrow~"}],InputForm,HoldForm] ReleaseHold[ans]//Union 

Finally, the program takes about $8$ seconds to finds $422716$ distinct solutions, same result as whuber.

n=9; gps=Block[{i=1,j=1},Groupings[Table[x,n],f->2]/. {f:>(F[#,Symbol["i"<>ToString@Mod[i++,n-1,1]],#2]&),x:>Symbol["n"<>ToString[Mod[j++,n,1]]]}]; gen=StringTemplate["if(check1(``)){ sprintf(buffer, \"``\\n\", ``); if(check2(buffer)) printf(\"%s\", buffer); }"][ToString@CForm@#, StringReplace[ToString@#,{"F"|", "->"","["->"(","]"->")", "n"~~DigitCharacter:>"%d","i"~~DigitCharacter:>"%c"}], StringReplace[StringRiffle[#//.F[x___]:>{x}//Flatten,","],"i"->"o"] ]&/@gps//StringRiffle[#,"\n"]&; src="#include <stdio.h> #include <math.h> #include <string.h> #include <time.h> #define NUM 100 #define N 6 #define EPS 1e-8 char ops[N] = {'+', '-', '*', '/', '#', '@'}; char buffer[128]; double F(double x, int op, double y) { double arr[] = {x + y, x - y, x * y, x / y, 10 * x + y, -x + y}; return arr[op]; } int check1(double x) { return fabs(x - NUM) < EPS || fabs(x + NUM) < EPS; } int check2(char buffer[]) { return (!strstr(buffer, \"#(\") && !strstr(buffer, \")#\")); } void calc(int a[]) { int len = 0; int n1 = a[0], n2 = a[1], n3 = a[2], n4 = a[3], n5 = a[4], n6 = a[5], n7 = a[6], n8 = a[7], n9 = a[8]; #pragma omp parallel for schedule(dynamic) reduction(+:buffer) for (int i1 = 0; i1 < N; i1++) { for (int i2 = 0; i2 < N; i2++) for (int i3 = 0; i3 < N; i3++) for (int i4 = 0; i4 < N; i4++) for (int i5 = 0; i5 < N; i5++) for (int i6 = 0; i6 < N; i6++) for (int i7 = 0; i7 < N; i7++) for (int i8 = 0; i8 < N; i8++) { char o1 = ops[i1], o2 = ops[i2], o3 = ops[i3], o4 = ops[i4], o5 = ops[i5], o6 = ops[i6], o7 = ops[i7], o8 = ops[i8]; `` } } } int main() { clock_t t0 = clock(); freopen(\"output.txt\", \"w\", stdout); int a[] = {1,2,3,4,5,6,7,8,9}; calc(a); printf(\"Elapsed time: %g sec\\n\", (clock() - t0) / (double) CLOCKS_PER_SEC); return 0; } "; Export["main.c",TemplateApply@StringTemplate[src,gen],"Text"] Run["gcc -Og main.c -fopenmp"] Run["a.exe"] // AbsoluteTiming list=ReadList["output.txt","String"] list // Most // Length LeftTeeArrow[x_,y_]:=-x+y; ans=ToExpression[StringReplace[Most@list,{"#"->"","@"->"~LeftTeeArrow~"}],InputForm,HoldForm] ReleaseHold[ans]//Union 

Similar to whuber's answer, we can use Groupings to simplify the generation patterns, it's introduced from Mathematica 11, and use parallel computing, which is a little faster.

Similar to whuber's answer, we can use Groupings(introduced in version 11) to simplify the generation patterns, the number of patterns is related to the CatalanNumber, and use parallel computing, which is a little faster.