Computing Partitions

Euler gave us the following recursion formula for \(p(n)\) via his Pentagonal Number Theorem :

\(p(n) = p(n-1) + p(n-2)-p(n-5)-p(n-7) + p(n-12) + p(n-15)-…\)

Note the generalised pentagonal numbers in the above.

Define  \(p(n) = 0\) if \(n \lt 0\) and let \(p(0) = 1\).

 

\( \begin{align}
p(1) & = p(0) & = 1 & = 1\\
p(2) & = p(1) + p(0) & = 1 + 1 & = 2\\
p(3) & = p(2) + p(1) & = 2 + 1 & = 3\\
p(4) & = p(3) + p(2) & = 3 + 2 & = 5\\
p(5) & = p(4) + p(3)-p(0) & = 5 + 3-1 & = 7\\
p(6) & = p(5) + p(4)-p(1) & = 7 + 5-1 & = 11\\
p(7) & = p(6) + p(5)-p(2)-p(0) & = 11 + 7-2-1 & = 15\\
p(8) & = p(7) + p(6)-p(3)-p(1) & = 15 + 11-3-1 & = 22\\
p(9) & = p(8) + p(7)-p(4)-p(2) & = 22 + 15-5-2 & = 30\\
\end{align}\)

 

This is the formula that MacMahon used to compute \(p(n)\) up to \(n = 200\) by hand.

\(p(200) = 3,972,999,029,388\)

 

Ramanujan conjectured that \(p(14,031)\equiv 0\pmod {11^4}\).

This has been verified by Lehmer.  The number has \(127\) digits.

He used the asymptotic formula of Ramanujan-Rademacher :

\( \displaystyle
p(n) \sim
\frac {e^{\pi \sqrt {2n/3}}}{4n \sqrt 3} \)

 

© OldTrout \(2019\)
 

No Audio file – Does not translate well