predict 42 different parenthesisations

predict 21 different products

42 parenthesisations:
(1x(2x(3x(4x(5x6)))))
(1x(2x(3x((4x5)x6))))
(1x(2x((3x4)x(5x6))))
(1x(2x((3x(4x5))x6)))
(1x(2x(((3x4)x5)x6)))
(1x((2x3)x(4x(5x6))))
(1x((2x3)x((4x5)x6)))
(1x((2x(3x4))x(5x6)))
(1x(((2x3)x4)x(5x6)))
(1x((2x(3x(4x5)))x6))
(1x((2x((3x4)x5))x6))
(1x(((2x3)x(4x5))x6))
(1x(((2x(3x4))x5)x6))
(1x((((2x3)x4)x5)x6))
((1x2)x(3x(4x(5x6))))
((1x2)x(3x((4x5)x6)))
((1x2)x((3x4)x(5x6)))
((1x2)x((3x(4x5))x6))
((1x2)x(((3x4)x5)x6))
((1x(2x3))x(4x(5x6)))
((1x(2x3))x((4x5)x6))
(((1x2)x3)x(4x(5x6)))
(((1x2)x3)x((4x5)x6))
((1x(2x(3x4)))x(5x6))
((1x((2x3)x4))x(5x6))
(((1x2)x(3x4))x(5x6))
(((1x(2x3))x4)x(5x6))
((((1x2)x3)x4)x(5x6))
((1x(2x(3x(4x5))))x6)
((1x(2x((3x4)x5)))x6)
((1x((2x3)x(4x5)))x6)
((1x((2x(3x4))x5))x6)
((1x(((2x3)x4)x5))x6)
(((1x2)x(3x(4x5)))x6)
(((1x2)x((3x4)x5))x6)
(((1x(2x3))x(4x5))x6)
((((1x2)x3)x(4x5))x6)
(((1x(2x(3x4)))x5)x6)
(((1x((2x3)x4))x5)x6)
((((1x2)x(3x4))x5)x6)
((((1x(2x3))x4)x5)x6)
(((((1x2)x3)x4)x5)x6)

21 unique products:
1
2
3
4
5
6
1x2
2x3
3x4
4x5
5x6
1x2x3
2x3x4
3x4x5
4x5x6
1x2x3x4
2x3x4x5
3x4x5x6
1x2x3x4x5
2x3x4x5x6
1x2x3x4x5x6



#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <set>

using namespace std;

int num_of_ways(int m, int n)
{ if (n == m || n == m + 1)
    return 1;
  int total = 0;
  for (int i = m; i < n; i += 1)
    total += num_of_ways(m, i) * num_of_ways(i + 1, n);
  return total; }

int num_of_prods(int m, int n)
{ return (n - m + 1) * (n - m + 2) / 2; }

// ....

int main(int argc, char * argv[]) 
{ int n = 20;
  if (argc > 1)
    n = atol(argv[1]);
  for (int i = 0; i < n; i += 1) 
    cout << num_of_ways(1, i) << ", ";
  cout << "\n"; }

$ a.out 20
0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700,

>>> vs = [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700]
>>> r = s.solve(vs)

       115589*N^19/11058645491712000 - 10984003*N^18/6402373705728000 + 140093699*N^17/1067062284288000
     - 389977213*N^16/62768369664000 + 12767154809*N^15/62768369664000 - 306555496463*N^14/62768369664000
     + 523629807731*N^13/5884534656000 - 12917494117*N^12/10287648000 + 26813911472903*N^11/1931334451200
     - 106162766239463*N^10/877879296000 + 364211109664967*N^9/438939648000 - 21542768235958723*N^8/4828336128000 
     + 437862803760000461*N^7/23538138624000 - 86933101767489221*N^6/1471133664000 + 182056770323227871*N^5/1307674368000
     - 305155252451576209*N^4/1307674368000 + 80292695067201889*N^3/308756448000 - 477634326410417*N^2/2806876800
     + 11285976812633*N/232792560

>>> for i in range(2, len(vs)):
        print(vs[i] / vs[i-1])
    
    1
    2
    5/2
    14/5
    3
    22/7
    13/4
    10/3
    17/5
    38/11
    7/2
    46/13
    25/7
    18/5
    29/8
    62/17
    11/3
    70/19

>>> vs = [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700]

>>> for i in range(2, len(vs)):
        print(vs[i] / vs[i-1])

    1.0
    2.0
    2.5
    2.8
    3.0
    3.142857142857143
    3.25
    3.3333333333333335
    3.4
    3.4545454545454546
    3.5
    3.5384615384615383
    3.5714285714285716
    3.6
    3.625
    3.6470588235294117
    3.6666666666666665
    3.6842105263157894


#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>

using namespace std;

long double * * memory = NULL;

void prepare(int n)
{ memory = new long double * [n + 1];
  for (int i = 0; i <= n; i += 1)
  { memory[i] = new long double[n + 1];
    for (int j = 0; j <= n; j += 1)
      memory[i][j] = -1.0; } }

void unprepare(int n)
{ for (int i = 0; i <= n; i += 1)
    delete [] memory[i];
  delete [] memory;
  memory = NULL; }

long double num_of_ways(int m, int n)
{ if (n == m || n == m + 1)
    return 1.0;
  if (memory[m][n] >= 0.0)
    return memory[m][n];
  long double total = 0.0;
  for (int i = m; i < n; i += 1)
    total += num_of_ways(m, i) * num_of_ways(i + 1, n);
  memory[m][n] = total;
  return total; }

int main(int argc, char * argv[])
{ int n = 100;
  if (argc > 1)
    n = atol(argv[1]);
  long double answers[n + 1];
  prepare(n + 1);
  answers[0] = 0.0;
  for (int i = 1; i <= n; i += 1)
  { answers[i] = num_of_ways(1, i);
    if (i % 100 == 0)
      cout << ".\n";  
    if (i < 20 || i > n - 20 || i % 100 == 0)
      cout << answers[i] << "   " << setprecision(10) << answers[i] / answers[i - 1] << "\n"; }
  unprepare(n + 1);
  cout << "\n"; }




$ a.out 5000
1   inf
1   1
2   2
5   2.5
14   2.8
42   3
132   3.142857143
429   3.25
1430   3.333333333
4862   3.4
16796   3.454545455
58786   3.5
208012   3.538461538
742900   3.571428571
2674440   3.6
9694845   3.625
35357670   3.647058824
129644790   3.666666667
477638700   3.684210526
.
2.275088308e+56   3.94
.
1.290131581e+116   3.97
.
1.127779149e+176   3.98
.
1.176736182e+236   3.985
.
1.352793999e+296   3.988
.
1.653501444e+356   3.99
.
2.10835972e+416   3.991428571
.
2.772852796e+476   3.9925
.
3.73400183e+536   3.993333333
.
5.122940538e+596   3.994
.
7.1353389e+656   3.994545455
.
1.006279329e+717   3.995
.
1.434049293e+777   3.995384615
.
2.061945749e+837   3.995714286
.
2.987609099e+897   3.996
.
4.357857572e+957   3.99625
.
6.394001986e+1017   3.996470588
.
9.430423573e+1077   3.996666667
.
1.3973459e+1138   3.996842105
.
2.079142129e+1198   3.997
.
3.105242231e+1258   3.997142857
.
4.653567431e+1318   3.997272727
.
6.995587479e+1378   3.997391304
.
1.054618207e+1439   3.9975
.
1.594037493e+1499   3.9976
.
2.415155787e+1559   3.997692308
^C
$ 



// One last try

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>

using namespace std;

long double * * memory = NULL;

void prepare(int n)
{ memory = new long double * [n + 1];
  for (int i = 0; i <= n; i += 1)
  { memory[i] = new long double[n + 1];
    for (int j = 0; j <= n; j += 1)
      memory[i][j] = -1.0; }
  for (int i = 0; i <= n; i += 1)
    memory[i][i] = 1.0;
  long double prev = 1.0;
  for (int diff = 1; diff < n; diff += 1)
    for (int i = 1; i + diff < n; i += 1)
    { long double tot = 0.0;
      for (int j = i; j < i + diff; j += 1)
        tot += memory[i][j] * memory[j + 1][i + diff];
      if (i == 1 && (diff < 100 || diff % 100 == 0))
        cout << i << ", " << i + diff << ": " << tot << "      " << tot / prev << "\n";
      memory[i][i + diff] = tot;
      prev = tot; } }

void unprepare(int n)
{ for (int i = 0; i <= n; i += 1)
    delete [] memory[i];
  delete [] memory;
  memory = NULL; }

int main(int argc, char * argv[])
{ int n = 100;
  if (argc > 1)
    n = atol(argv[1]);
  long double answers[n + 1];
  prepare(n + 1);
  unprepare(n + 1);
  cout << "\n"; }

$ a.out 5000
1, 2: 1      1
1, 3: 2      2
1, 4: 5      2.5
1, 5: 14      2.8
1, 6: 42      3
1, 7: 132      3.14286
1, 8: 429      3.25
1, 9: 1430      3.33333
1, 10: 4862      3.4
1, 11: 16796      3.45455
1, 12: 58786      3.5
1, 13: 208012      3.53846
1, 14: 742900      3.57143
1, 15: 2.67444e+06      3.6
1, 16: 9.69484e+06      3.625
1, 17: 3.53577e+07      3.64706
1, 18: 1.29645e+08      3.66667
1, 19: 4.77639e+08      3.68421
1, 20: 1.76726e+09      3.7
1, 21: 6.56412e+09      3.71429
1, 22: 2.44663e+10      3.72727
1, 23: 9.14826e+10      3.73913
1, 24: 3.4306e+11      3.75
1, 25: 1.2899e+12      3.76
1, 26: 4.86195e+12      3.76923
1, 27: 1.83674e+13      3.77778
1, 28: 6.95336e+13      3.78571
1, 29: 2.63748e+14      3.7931
1, 30: 1.00224e+15      3.8
1, 31: 3.81499e+15      3.80645
1, 32: 1.45446e+16      3.8125
1, 33: 5.55341e+16      3.81818
1, 34: 2.12336e+17      3.82353
1, 35: 8.12944e+17      3.82857
1, 36: 3.11629e+18      3.83333
1, 37: 1.19598e+19      3.83784
1, 38: 4.59508e+19      3.84211
1, 39: 1.76734e+20      3.84615
1, 40: 6.80425e+20      3.85
1, 41: 2.62213e+21      3.85366
1, 42: 1.01139e+22      3.85714
1, 43: 3.90444e+22      3.86047
1, 44: 1.50853e+23      3.86364
1, 45: 5.833e+23      3.86667
1, 46: 2.25712e+24      3.86957
1, 47: 8.74033e+24      3.87234
1, 48: 3.38688e+25      3.875
1, 49: 1.31328e+26      3.87755
1, 50: 5.09552e+26      3.88
1, 51: 1.97826e+27      3.88235
1, 52: 7.68479e+27      3.88462
1, 53: 2.98692e+28      3.88679
1, 54: 1.16158e+29      3.88889
1, 55: 4.5196e+29      3.89091
1, 56: 1.75941e+30      3.89286
1, 57: 6.85246e+30      3.89474
1, 58: 2.6701e+31      3.89655
1, 59: 1.04088e+32      3.89831
1, 60: 4.05945e+32      3.9
1, 61: 1.58385e+33      3.90164
1, 62: 6.18213e+33      3.90323
1, 63: 2.41397e+34      3.90476
1, 64: 9.42959e+34      3.90625
1, 65: 3.68479e+35      3.90769
1, 66: 1.44042e+36      3.90909
1, 67: 5.63268e+36      3.91045
1, 68: 2.20337e+37      3.91176
1, 69: 8.62189e+37      3.91304
1, 70: 3.37486e+38      3.91429
1, 71: 1.32142e+39      3.91549
1, 72: 5.17557e+39      3.91667
1, 73: 2.02769e+40      3.91781
1, 74: 7.94635e+40      3.91892
1, 75: 3.11497e+41      3.92
1, 76: 1.2214e+42      3.92105
1, 77: 4.79041e+42      3.92208
1, 78: 1.87931e+43      3.92308
1, 79: 7.37452e+43      3.92405
1, 80: 2.8945e+44      3.925
1, 81: 1.13636e+45      3.92593
1, 82: 4.46229e+45      3.92683
1, 83: 1.75266e+46      3.92771
1, 84: 6.88544e+46      3.92857
1, 85: 2.70557e+47      3.92941
1, 86: 1.06335e+48      3.93023
1, 87: 4.18008e+48      3.93103
1, 88: 1.64353e+49      3.93182
1, 89: 6.46333e+49      3.93258
1, 90: 2.54224e+50      3.93333
1, 91: 1.00013e+51      3.93407
1, 92: 3.93531e+51      3.93478
1, 93: 1.54874e+52      3.93548
1, 94: 6.09609e+52      3.93617
1, 95: 2.39993e+53      3.93684
1, 96: 9.44974e+53      3.9375
1, 97: 3.72144e+54      3.93814
1, 98: 1.46579e+55      3.93878
1, 99: 5.77434e+55      3.93939
1, 100: 2.27509e+56      3.94
1, 101: 8.9652e+56      3.94059
1, 201: 5.12201e+116      3.97015
1, 301: 4.48864e+176      3.98007
1, 401: 4.68934e+236      3.98504
1, 501: 5.39497e+296      3.98802
1, 601: 6.5975e+356      3.99002
1, 701: 8.41539e+416      3.99144
1, 801: 1.10706e+477      3.99251
1, 901: 1.49111e+537      3.99334
1, 1001: 2.04611e+597      3.99401
1, 1101: 2.85025e+657      3.99455
1, 1201: 4.02009e+717      3.995
1, 1301: 5.72958e+777      3.99539
1, 1401: 8.23895e+837      3.99572
1, 1501: 1.19385e+898      3.996
1, 1601: 1.74151e+958      3.99625
1, 1701: 2.55535e+1018      3.99647
1, 1801: 3.76903e+1078      3.99667
1, 1901: 5.58497e+1138      3.99684
1, 2001: 8.31033e+1198      3.997
1, 2101: 1.24121e+1259      3.99714
1, 2201: 1.86016e+1319      3.99727
1, 2301: 2.79641e+1379      3.99739
1, 2401: 4.21584e+1439      3.9975
1, 2501: 6.37233e+1499      3.9976
1, 2601: 9.65505e+1559      3.99769
1, 2701: 1.46614e+1620      3.99778
1, 2801: 2.23095e+1680      3.99786
1, 2901: 3.40122e+1740      3.99793
1, 3001: 5.19463e+1800      3.998
1, 3101: 7.94691e+1860      3.99807
1, 3201: 1.21764e+1921      3.99813
1, 3301: 1.86843e+1981      3.99818
1, 3401: 2.871e+2041      3.99824
1, 3501: 4.41726e+2101      3.99829
1, 3601: 6.80463e+2161      3.99833
1, 3701: 1.04944e+2222      3.99838
1, 3801: 1.62027e+2282      3.99842
1, 3901: 2.5042e+2342      3.99846
1, 4001: 3.87417e+2402      3.9985
1, 4101: 5.99922e+2462      3.99854
1, 4201: 9.29819e+2522      3.99857
1, 4301: 1.44235e+2583      3.9986
1, 4401: 2.23922e+2643      3.99864
1, 4501: 3.47903e+2703      3.99867
1, 4601: 5.40931e+2763      3.9987
1, 4701: 8.41654e+2823      3.99872
1, 4801: 1.31045e+2884      3.99875
1, 4901: 2.04169e+2944      3.99878
$
// the biggest long double is 1.18e+4932 so there was a way still to go,
// but not enough memory.



// the rest of the original program


struct str_less
{ bool operator()(const string & a, const string & b) const
  { if (a.length() != b.length())
      return a.length() < b.length();
    return a < b; } };

string enstring(int n)
{ string s;
  if (n >= 10)
    s = enstring(n / 10);
  return s + (char)(n % 10 + '0'); }

void solve(int a, int b, vector <string> & v, set <string, str_less> & all)
{ if (a == b)
  { string s = enstring(a);
    all.insert(s);
    v.push_back(s);
    return; }
  vector <string> vr, vs;
  for (int p = a; p < b; p += 1)
  { vr.clear();
    vs.clear();
    solve(a, p, vr, all);
    solve(p + 1, b, vs, all);
    for (string x: vr)
      for (string y : vs)
        v.push_back(string("(") + x + "x" + y + ")"); }
  string s = enstring(a);
  for (int i = a + 1; i <= b; i += 1)
    s = s + "x" + enstring(i);
  all.insert(s); }

int main(int argc, char * argv[])
{ int n = 5;
  if (argc > 1)
    n = atol(argv[1]);
  vector <string> v;
  set <string, str_less> all;
  solve(1, n, v, all);
  cout << v.size() << " parenthesisations:\n";
  for (string s: v)
    cout << s << "\n";
  cout << all.size() << " unique products:\n";
  for (string s: all)
    cout << s << "\n"; }