Exact results (given below) are out on Thu Dec 9 10:46:59 IST 2010. In the table below, $p_3(N)$ denotes the solid partitions of $N$ while $q_3(N)$ and $r_3(N)$ denote two approximations (as described below) to it. The complete results are given at the end of this page
$N$ | 55 | 56 | 57 | 58 | |
---|---|---|---|---|---|
$p_3(N)$ | 886033384475166 | 1464009339299229 | 2413804282801444 | 3971409682633930 | Exact |
$q_3(N)$ | used to fix const. | 1464095834419295 | 2414026269758682 | 3971801006366828 | Pred. 1 |
$r_3(N)$ | 886033238816908 | 1464000246148514 | 2413758496872281 | 3971251709996636 | Pred. 2 |
$N$ | 59 | 60 | 61 | 62 | |
---|---|---|---|---|---|
$p_3(N)$ | 6520649543912193 | 10684614225715559 | 17472947006257293 | 28518691093388854 | Exact |
$q_3(N)$ | 6521164672460061 | 10684975704975763 | 17472313806874724 | 28514975666146341 | Pred. 1 |
$r_3(N)$ | 6520195930064767 | 10683450471539752 | 17470184645592214 | 28512500279825068 | Pred. 2 |
Estimating the numbers of solid partitions
We came up with two sets of predictions for these numbers before the arrival of the exact data.
- The first prediction was made on Sat Nov 13 17:17:26 IST 2010. and made use of the following asymptotic formula.
where we fixed the multiplicative constant to give the exact answer for 55. We anticipated that the numbers will be of the correct order with the first three digits being correct.
- A second prediction was made on Sun Dec 5 15:32:52 IST 2010. This is based on an extension of the above formula and we call the expression $r_3(N)$ — this has three unknown constants ($d,e,f$) and we fit them using data for $N=50-55$. The formula is
where $a,b,c$ are as before and the constants were chosen to be $d= -1.0990048006607374$, $e= -2.4707724558397453$ and $f=3.4257194464498872$.
With the arrival of the exact results, we present the two predictions as well the exact numbers in the table above. We believe that this constitutes significant evidence that there exists an asymptotic formula for solid partitions. However, the precise form as well as error estimates remain unknown. The surprise is that it seems to work even for small numbers such as 50, 60.
A plot of how the two approximations work in the range 40-55 (added the 56-62 data when they became available) — we are plotting the ratio of the approximate formula to the exact one. Black dots are for $q_3(x) /p_{3}(x)$ while red dots are for $r_3(x) /p_{3}(x)$. Notice the scale on the y-axis.
The next plot contains three grapsh: the red dots are a plot of $N^{-3/4} \log(p_3(N))$ vs $N$. The second curve in green is a fit of $N^{-3/4}\log(p_3(N))$ for the data ($N=25-62$) to a function of the form $\big(a + b N^{-1/4} + c N^{-1/2}\big)$. The third curve is the horizontal line at $1.78982$ — the value of the coefficient of $N^{3/4}$ as given by the wrong MacMahon formula. The last two curves have been drawn up to $N=100$ to show how the extrapolation of the fit looks.
$\mathbf{\textbf{log}(p_3(N)) \sim N^{3/4}\big(1.78465 + 0.567345\ N^{-1/4}-2.14183\ N^{-1/2}+\mathcal{O}(N^{-3/2})\big)}$
If you are wondering what solid partitions are, read here.
Results
Here are the results obtained on Thu Dec 9 10:46:59 IST 2010 by running a parallelized and modified version of Knuth's algorithm for about a month (30000 CPU hours). Below, c[N] denotes the number of solid partitions of N. We add twelve numbers, c[51] to c[62] to the numbers computed by Knuth and Mustonen-Rajesh. The number of solid partitions for the first fifty numbers are also listed in the On-Line Encyclopedia of Integer Sequences. Our list is given below:
c[1] = 1
c[2] = 4
c[3] = 10
c[4] = 26
c[5] = 59
c[6] = 140
c[7] = 307
c[8] = 684
c[9] = 1464
c[10] = 3122
c[11] = 6500
c[12] = 13426
c[13] = 27248
c[14] = 54804
c[15] = 108802
c[16] = 214071
c[17] = 416849
c[18] = 805124
c[19] = 1541637
c[20] = 2930329
c[21] = 5528733
c[22] = 10362312
c[23] = 19295226
c[24] = 35713454
c[25] = 65715094
c[26] = 120256653
c[27] = 218893580
c[28] = 396418699
c[29] = 714399381
c[30] = 1281403841
c[31] = 2287986987
c[32] = 4067428375
c[33] = 7200210523
c[34] = 12693890803
c[35] = 22290727268
c[36] = 38993410516
c[37] = 67959010130
c[38] = 118016656268
c[39] = 204233654229
c[40] = 352245710866
c[41] = 605538866862
c[42] = 1037668522922
c[43] = 1772700955975
c[44] = 3019333854177
c[45] = 5127694484375
c[46] = 8683676638832
c[47] = 14665233966068
c[48] = 24700752691832
c[49] = 41495176877972
c[50] = 69531305679518c[51] = 116221415325837
c[52] = 193794476658112
c[53] = 322382365507746
c[54] = 535056771014674
c[55] = 886033384475166
c[56] = 1464009339299229
c[57] = 2413804282801444
c[58] = 3971409682633930
c[59] = 6520649543912193
c[60] = 10684614225715559
c[61] = 17472947006257293
c[62] = 28518691093388854
Credits: B. Srivatsan (a sophomore at IIT Madras) for writing all the code which was parallelized by Suresh Govindarajan(SG). All runs were carried out by SG on machines at the High Performance Computing Environment at IIT Madras.
Disclaimer: While a lot of effort has gone into ensuring the correctness of our results, this has not been independently verified. Our results do agree with known results up to N=50 and could be considered as an independent verfication of the 2003 Mustonen-Rajesh result. as well as a validation of the numbers for N=51,52 that were generated using different code (v2.0) and N=53-55 that were generated using v3.0 of the code.
Support the solid partitions project
How? Either run code or work on improving the code or help with setting up/running the portal. Contact solidpartitions at gmail.com
© 2010 Suresh Govindarajan