In 1914, the great mathematician Srinivasa Ramanujan came from India to England and worked with Thomas Hardy at Cambridge. One of the projects they completed was a formula to approximate the number of partitions for any number \(n\), to which an algebraic solution had seemed intractable. Partitions of a number, denoted \(p(n)\), are simply the number of ways positive integers can be combined to sum to any number \(n\), in which the order does not matter. In other words, if \(n=5\) then the possible combinations are
\[ \begin{matrix} 1& 1& 1 &1& 1\; \\ 2 &1& 1& 1\; \\ 2& 2 &1\; \\ 3 &1 &1\; \\ 3 &2\; \\ 4 &1\; \\ 5&\; \\ \end{matrix} \]
Giving us a total of 7 partitions for \(n=5\), or \(p(5)=7\). Changing the order does not give us more partitions. 2,1,1,1 and 1,2,1,1 would be considered the same partition, as changing order of elements still sums to \(n\).
Partitions of a number increase very quickly. There are 42 partitions of \(n=10,\) 627 partitions of \(n=20,\) 37,338 partitions of \(n=40,\) and when \(n=100\) then \(p(n)=\) 190,569,292.
\[p(n) \sim\ \frac{1}{4n\sqrt{3}}e^{\pi \sqrt{\frac{2n}{3}}} \]
The asymptotic partition formula that Hardy and Ramanujan created has beauty and elegance, in that it consists only of the integers 1, 2, 3 and 4, and the constants \(\pi\) and \(e\), and is simple in structure. It is striking that an equation of such simplicity can approximate the values of \(p(n)\), with an error rate that decreases as the value of \(n\) increases. Let's take a look at the approximate number of partitions that this formula returns for a variety of values of \(n,\) and the corresponding error values and percentages.
\[ \begin{array} {l} \it n & \it p(n) & \it HR\phantom{0}formula & \it error & \it error \%\; \\ 10 &42&48.1 &6.1 & 14.524\%\ \; \\ 20 & 627&692.38 & 65.4 & 10.43\%\ \; \\ 30 &5604&6080.4 & 476.4 & 8.5\%\ \; \\ 40 &37338&40080 & 2742 & 7.34\%\ \; \\ 71 & 4697205 &4953642 &256437 & 5.46\%\ \; \\ 100 &190569292 &199280893 & 8711601 & 4.57\%\ \; \\200 & 3.972999E+12 & 4.1002514E+12\phantom{000} &127252402799& 3.2\%\ \; \\ 373 &1.2380578E+18 &1.2669247E+18 &2.88669E+18 & 2.33\%\ \; \\ 500&2.300165E+21&2.3463866E+21 &4.6221593E+21 & 2.01\%\ \; \\ 1000 &2.4061468E+31 &2.4401996E+31 & 3.4052845E+29 & 1.42\%\ \; \\ 3001 &5.0760764+56 &5.1173779E+56 &4.130139+54 & 0.814\%\ \; \\ 5000 &1.6982017E+74 & 1.708893E+74 &1.06914E+72 & 0.63\%\ \; \\ 10,000\phantom{000} & 3.616725E+106\phantom{000} &3.6328058+106 & 1.6080668E+104\phantom{000} & 0.445\%\ \; \\ 20,000 &2.521E+152 & 2.5291E+152 &8.1E+149 & 0.32\%\ \; \\ \end{array} \]
As a quick way to calculate an approximation of \(p(n)\), the Hardy-Ramanujan formula works well, with its accuracy approaching the correct value of \(p(n)\) asymptotically as the value of \(n\) increases.
Experimenting with various manipulations of the formula to see if accuracy could be increased, I found that differentiating the formula and employing the second derivative in the following way significantly reduced the error rate. The results are noticeably more accurate than the original formula for smaller values of \(n\), and the asymptotic approach to the curve represented by \(p(n)\) also occurs at a faster rate than with the original formula.
\[p(n) \sim\ \frac{1}{4n\sqrt{3}}e^{\pi \sqrt{\frac{2n}{3}}} \phantom{0}-\phantom{0} \frac{d^2 }{dn^2} \biggr(\frac{1}{4n\sqrt{3}}e^{\pi \sqrt{\frac{2n}{3}}}\biggr)ln\frac{n}{4} \]
Now let's take a look at the values for \(p(n)\) returned by this modified formula, and the corresponding error values and percentages.
As we can see, the error reduction is considerable. Below is a table for side by side comparison of the error rates for the original and modified formulas, for the selected values of \(n\):
\[ \begin{array} {l} \it n & \bf p(n) & \it HR\phantom{0}error \%\ \ & \it modified\phantom{0}HR\phantom{0}error \%\; \\ 10 & 42 & 14.524\%\ \phantom{000000000} & 5.81\%\; \\ 20 & 627 & 10.43\%\ & 1.276\%\; \\ 30 & 5604 & 8.5\%\ & 0.294\% \; \\ 40 & 37338 & 7.34\%\ & 0.0033\%\; \\ 71 & 4697205 & 5.46\%\ & -0.063\% \; \\ 100 &190569292 & 4.57\%\ & 0.0464\% \; \\200 & 3.972999E+12 & 3.2\%\ & 0.32\%\; \\ 373 &1.2380578E+18 & 2.33\%\ & 0.485\%\; \\ 500 & 2.300165E+21 & 2.01\%\ & 0.526\% \; \\ 1000 & 2.4061468E+31 & 1.42\%\ & 0.55\%\; \\ 3001 & 5.0760764+56 & 0.814\%\ & 0.46\%\; \\ 5000 & 1.6982017E+74\phantom{00000} & 0.63\%\ & 0.4\%\; \\ 10,000\phantom{000} & 3.616725E+106\phantom{000} & 0.445\%\ & 0.32\%\; \\ 20,000 &2.521E+152 & 0.32\%\ & 0.25\%\; \\ \end{array} \]
If we work out the differentiation of the Hardy-Ramanujan formula to the second derivative, we get:
\[ \frac{d^2 }{dn^2} \biggr(\frac{1}{4n\sqrt{3}}e^{\pi \sqrt{\frac{2n}{3}}}\biggr) = \]
\[ \frac{ (\pi(9*2^\frac{15}{2}\pi n^\frac{13}{2} - 640*3^\frac{5}{2}n^6) + 27*2^\frac{19}{2}n^\frac{11}{2})e^{\pi \sqrt{\frac{2n}{3}} } }{2^\frac{21}{2}3^\frac{7}{2}n^\frac{17}{2}} \]
Putting the differentiated result into the modified equation, the algebraic expression is less elegant to behold than the original Hardy-Ramanujan formula, but we have gained a much closer approximation of the partition values for any number \(n\).
\[p(n) \sim\ \frac{1}{4n\sqrt{3}}e^{\pi \sqrt{\frac{2n}{3}}} \phantom{0}-\phantom{0} \frac{ (\pi(9*2^\frac{15}{2}\pi n^\frac{13}{2} - 640*3^\frac{5}{2}n^6) + 27*2^\frac{19}{2}n^\frac{11}{2})e^{\pi \sqrt{\frac{2n}{3}}} }{2^\frac{21}{2}3^\frac{7}{2}n^\frac{17}{2}} ln\frac{n}{4}\]