# Ramanujan's conjecture

If $p(n)$ is the number of ways in which the number $n$ can be expressed as a sum of positive integers then find $p(200)$.

[I know that] $p(1) = 1$, $p(2) = 2$, $p(3) = 3$, $p(4) = 5$, $p(5) = 7$, $p(6) = 11$.

This question is the toughest question I have ever faced in my school exam. I had tried to use the partition method of combinatorics but failed as the number 200 is too big. Help me to get the answer.

• Hint: $n=1+1+1+\cdots+1$ ($n$ times)
– CIJ
Commented Mar 24, 2015 at 18:28
• Search for number of partitions in your favorite search-engine (or read this). Commented Mar 24, 2015 at 18:28
• Just shy of 4 trillion (or rather $4 \cdot 10^{12}$ for those who use -illiards). I see no not-painful way of doing this by hand. Commented Mar 24, 2015 at 18:31
• Any sort of formulae or general expression for this type of question. Commented Mar 24, 2015 at 18:47
• Is it possible the problem does not mean the usual partition function? I.e., when you say you know the first six values of $p(n)$, is that because the problem itself gives them, or because you've worked them out for yourself, based on an interpretation of the problem's defintion of $p(n)$? In particular, if the problem actually means ordered sums, so that, for example, $2+1$ and $1+2$ are different sums for $3$, then the answer is simply $2^{199}$. Commented Mar 24, 2015 at 23:20

When I know the answer for a few small values but I don't know the general formula, I usually turn to Sloane's OEIS. I looked for 1,2,3,5,7,11 and the very first result was Sloane's A000041. These numbers are called the partition numbers. One of the formulas given is $$p(n) = \frac{1}{n} \sum_{k = 0}^{n - 1} \sigma(n - k) p(k).$$ Problem with this of course is that you'd have to compute $p(k)$ for $0 \leq k < 200$. But you can't just say $p(200) = 3972999029388$; I got that answer just by looking in the B-file (see the David Wilson link in Sloane's A000041). Skimming Sloane's entry (it's long), I see no simple formula to get the answer, but I'm not taking an exam.
If you only need a decent approximation, you can use $$p(n) \sim \frac{1}{4n \sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$$ to obtain $p(200) \sim 4100251432187$, which overshoots by little more than 1% (I got this formula from MathWorld but it also appears in Sloane's entry).
There's no general expression for $p(n)$ and, in fact, there's no easy way to calculate something of this magnitude, especially not by hand.
Inputting "partitions of 200" into our friend WolframAlpha gives us $3,972,999,029,388$ partitions.
There's a lot of information about partitions which you an find here. Nothing makes the herculean task of calculating $p(200)$ any easier.