Leonhard Euler 1707-1783
Srinivasa Ramanujan 1887-1920
Godfrey Harold Hardy 1877-1947
Edward Maitland Wright 1906-2005
John Edensor Littlewood 1885-1977
Percy Alexander MacMahon 1854-1929
Srinivasa Ramanujan 1887-1920
Godfrey Harold Hardy 1877-1947
Edward Maitland Wright 1906-2005
John Edensor Littlewood 1885-1977
Percy Alexander MacMahon 1854-1929
Maybe you have seen the movie about Ramanujan\b’s life the man who knew infinity. Ramanujan find’s an asymptotic formula to compute the partitions. MacMahon on the other side relies on the explicit formula found by Euler to compute p(200).
This is from 1938 Hardy/Wright An Introduction to the Theory of Numbers:
Here are the 15 unrestricted partitions of 7, i.e. :
p(7)=15
Out[]=
So lets implement Euler’s formula used by MacMahon to compute p(n):
In[]:=
p[n_Integer?Negative]:=0;macmahon[n_Integer?Positive]:=Module[{k=1,sum=0,index=n-1},While[index>=0,sum+=(p[index]+p[index-k]);k++;index-=(3k-2)];Style[Row[{p[n],":=",sum,"=",PartitionsP[n]}],10]]
k+1
(-1)
Example:
In[]:=
macmahon[12]
Out[]=
p[12]:=p[0]-p[5]-p[7]+p[10]+p[11]=77
Here are the first 42 entries:
In[]:=
Column[Map[macmahon,Range[42]]]
Out[]=
lets check the value for p(42):
In[]:=
macmahon[42]
Out[]=
p[42]:=p[2]+p[7]-p[16]-p[20]+p[27]+p[30]-p[35]-p[37]+p[40]+p[41]=53174
The sum is reversed here:
In[]:=
44583+37338-21637-14883+5604+3010-627-231+15+2
Out[]=
53174
And all you have to do is to calculate all entries up to 200:)
In[]:=
macmahon[200]
Out[]=
p[200]:=p[13]+p[24]-p[45]-p[55]+p[74]+p[83]-p[100]-p[108]+p[123]+p[130]-p[143]-p[149]+p[160]+p[165]-p[174]-p[178]+p[185]+p[188]-p[193]-p[195]+p[198]+p[199]=3972999029388
This can also be done with this recursive definition:
In[]:=
P[n_Integer?Negative]:=0P[0]:=P[0]=1P[n_Integer?Positive]:=P[n]=Module[{k=1,sum=0,index=n-1},While[index>=0,sum-=(P[index]+P[index-k++]);index-=3k-2];sum]
k
(-1)
In[]:=
P[42]
Out[]=
53174
In[]:=
P[200]
Out[]=
3972999029388
Appendix: Approximation of Ramanujan/Hardy 1918
Appendix: Approximation of Ramanujan/Hardy 1918
This is a special Dedekind sum:
In[]:=
sD[h_,k_]:=SumMod,1-,{r,1,k-1}
r
k
hr
k
1
2
In[]:=
Grid[Table[sD[h,k],{h,0,5},{k,1,9}],Frame->All]
Out[]=
0 | - 1 4 | - 1 2 | - 3 4 | -1 | - 5 4 | - 3 2 | - 7 4 | -2 |
0 | 0 | 1 18 | 1 8 | 1 5 | 5 18 | 5 14 | 7 16 | 14 27 |
0 | - 1 4 | - 1 18 | - 1 4 | 0 | - 7 36 | 1 14 | - 1 8 | 4 27 |
0 | 0 | - 1 2 | - 1 8 | 0 | - 1 2 | - 1 14 | 1 16 | - 4 9 |
0 | - 1 4 | 1 18 | - 3 4 | - 1 5 | - 11 36 | 1 14 | - 3 4 | - 4 27 |
0 | 0 | - 1 18 | 1 8 | -1 | - 5 18 | - 1 14 | - 1 16 | 4 27 |
In[]:=
A[n_,k_]:=Sum,{h,Select[Range[0,k-1],CoprimeQ[#,k]True&]}
sD[h,k]-2n
h
k
(-1)
In[]:=
Grid[Table[A[h,k],{h,1,5},{k,1,5}],Frame->All]
Out[]=
1 | -1 | - 7/18 (-1) 11/18 (-1) | 3/8 (-1) 5/8 (-1) | 0 |
1 | 1 | - 5/18 (-1) 13/18 (-1) | - 1/8 (-1) 7/8 (-1) | 0 |
1 | -1 | 1/18 (-1) 17/18 (-1) | - 3/8 (-1) 5/8 (-1) | -2+ 2/5 (-1) 3/5 (-1) |
1 | 1 | - 7/18 (-1) 11/18 (-1) | 1/8 (-1) 7/8 (-1) | - 1/5 (-1) 2/5 (-1) 3/5 (-1) 4/5 (-1) |
1 | -1 | - 5/18 (-1) 13/18 (-1) | 3/8 (-1) 5/8 (-1) | 2+ 1/5 (-1) 4/5 (-1) |
In[]:=
RamanujanHardyPTerms[n_,m_]:=Withexpr=D,x/.x->n,TableA[n,k]
Expx-
π
k
2
3
1
24
x-
1
24
1
2π
2
k
expr,{k,1,m}This example is given by Ramanujan/Hardy for p(100) on page 84:
And this is computed with the above code:
Out[]=
Compared to the exact value:
In[]:=
PartitionsP[100]
Out[]=
190569292
And here is computed (you can see, that the sign of the second term is negative now):
p(101)
Out[]=
Compared to the exact value:
In[]:=
PartitionsP[101]
And this is computed with the above code (so they made a small mistake at the third term:):
Compared to the exact value:
Compared to the exact value:
The first term alone is:
The asymptotic of this term is:
And this is the value Mathematica returns:
The asymptotics of the first two terms are:
And here you can see how the approximations perform:
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Ramanujan-Hardy approximation and how MacMahon computed P(200)
by Oliver Seipel
Wolfram Community, STAFF PICKS, October 8, 2023
https://community.wolfram.com/groups/-/m/t/3030135
by Oliver Seipel
Wolfram Community, STAFF PICKS, October 8, 2023
https://community.wolfram.com/groups/-/m/t/3030135