<s>[INST] Prime Partition A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there are seven prime partitions of $12$: {2 2 2 2 2 2}, {2 2 2 3 3}, {3 3 3 3}, {2 2 3 5}, {2 5 5}, {2 3 7}, and {5 7}. The number of prime partitions of a number is given by A000607.
I want to calculate the number of prime partitions of a number. From reading the text of A000607 it seems to me that the formula $\prod\limits_{p \in \pi(n)} \frac1{1 - n^p}$ should work. But it doesn't. Consider the case of $n=12$. The primes less than $12$ are $2, 3, 5, 7$, and $11$. Thus the formula computes $\frac1{1-12^2} \times \frac1{1-12^3} \times \frac1{1-12^5} \times \frac1{1-12^7} \times \frac1{1-12^{11}}$ = $\frac1{-143} \times \frac1{-1727} \times \frac1{-248831} \times \frac1{-35831807} \times \frac1{-743008370687}$ = $\frac{-1}{1636045119596820253743372240719}$ which is obviously incorrect.
How can I compute the number of prime partitions of a number?
 [/INST] You need to learn a bit about generating functions. The text associated with A000607 means the following. For each prime $p$ expand the function $1/(1-x^p)$ as a power series:
$$
\frac1{1-x^p}=1+x^p+x^{2p}+x^{3p}\cdots=\sum_{k=0}^\infty x^{kp}.
$$
Call that series $f_p(x)$.
Then you multiply these power series together, and identify the coefficient of $x^n$. That coefficient is then  the desired value of the prime partition function. Let's do this for $n=12$. To that end we can throw away all the terms of degree $>12$. I denote those with three dots. So start with
$$
f_2(x)=1+x^2+x^4+x^6+x^8+x^{10}+x^{12}+\cdots
$$
Multiplying this with $f_3(x)=1+x^3+x^6+x^9+x^{12}+\cdots$ gives
$$
\begin{aligned}
f_2(x)f_3(x)=&f_2(x)+x^3f_2(x)+x^6f_2(x)+x^9f_2(x)+x^{12}f_2(x)+\cdots\\
=&1+x^2+x^3+x^4+x^5+2x^6+x^7+2x^8+2x^9+2x^{10}+2x^{11}+3x^{12}+\cdots
\end{aligned}
$$
At this point you should check that the coefficient of $x^k$ counts the number of ways of
writing $k$ as a sum of twos and threes.
Next we add $p=5$ to the mix, and multiply the above with $f_5(x)=1+x^5+x^{10}+\cdots$ and get
$$
\begin{aligned}
&f_2(x)f_3(x)f_5(x)\\
=&1+x^2+x^3+x^4+2x^5+2x^6+2x^7+3x^8+3x^9+4x^{10}+4x^{11}+5x^{12}+\cdots
\end{aligned}
$$
Next we multiply this with $f_7(x)=1+x^7+\cdots$ and get
$$
\begin{aligned}
&f_2(x)f_3(x)f_5(x)f_7(x)\\
=&1+x^2+x^3+x^4+x^5+2x^6+3x^7+3x^8+4x^9+5x^{10}+5x^{11}+7x^{12}+\cdots\\
\end{aligned}
$$
As a laste step we multiply this with $f_{11}(x)=1+x^{11}+\cdots$ to end with
$$
\begin{aligned}
&f_2(x)f_3(x)f_5(x)f_7(x)f_{11}(x)\\
=&1+x^2+x^3+x^4+x^5+2x^6+3x^7+3x^8+4x^9+5x^{10}+6x^{11}+7x^{12}+\cdots\\
\end{aligned}
$$
Here the term $7x^{12}$ appears. Primes $p>12$ won't affect the term of degree $12$, so at long last that tells us that there are seven prime partitions of $n=12$.
</s>