Prime Partition

Question

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?

Answer 1

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$.

Answer 2

You are misunderstanding the text of OEIS's sequence A000607, I think. The function $$ g(x) = {\prod}_{p}\frac{1}{1-x^{p}} = \frac{1}{1-x^2}\times\frac{1}{1-x^3}\times\frac{1}{1-x^5}\times{...} $$ is the generating function for the sequence. The number of prime partitions of $n$ is given by the coefficient of $x^n$ in the Taylor series expansion of $g(x)$ around $x=0$: that is, $$ a_n = \frac{1}{n!}\frac{\partial^n}{\partial{x}^n}g(x)\Big\vert_{x=0}. $$ This doesn't give a practical way to actually calculate the coefficients, though. For that, a dynamic programming approach can easily be formulated (e.g., by recursively evaluating $b_{n,p}$, the number of prime partitions of $n$ using primes no greater than $p$, and setting $a_n=b_{n,n}$).

Answer 3

This is a misunderstanding. The formula you quote is the generating function for the numbers you're looking for. It would more usually be written as

$$\prod_p\frac1{1-x^p}\;,$$

where the product runs over all primes $p$, and then the number of partitions of $n$ into prime parts is the coefficient of $x^n$ in the power series for this function. However, this is not meant as a practical way to compute these numbers, more like an efficient way to organize the information about these numbers.

The MathWorld article on prime partitions describes how to compute the numbers of prime partitions using an Euler transform.

Answer 4

I've decided to turn one of my comments into a full answer, in the interest of keeping this thread self-contained. The formulae needed are from here (formulae 5-10).

First, we define the sum of prime factors function, $\mathrm{sopf}(n)$ (sequence A008472 in the OEIS):

$$\mathrm{sopf}(n)=\sum_{p\in\mathbb P,\;p\mid n}p$$

In Mathematica: PrimeDivisorSum[n_Integer] := DivisorSum[n, Identity, PrimeQ]. (On some other language and assuming you have a pre-cached array of primes, just check for the primes $\leq n$ that are divisors, and add them all up.)

The prime partition counting function, which I'll denote in this answer by $\kappa(n)$, then satisfies the following recursion:

$$\kappa(n)=\frac1{n}\left(\mathrm{sopf}(n)+\sum_{j=1}^{n-1} \mathrm{sopf}(j)\kappa(n-j)\right)$$

with the initial condition $\kappa(1)=0$. In effect, we are saying that $\kappa(n)$ is the Euler transform of the function $[n\in\mathbb P]$, where $[p]$ is an Iverson bracket.

In Mathematica:

PrimePartitionCount[1] = 0; 
PrimePartitionCount[n_Integer] := PrimePartitionCount[n] =
   (PrimeDivisorSum[n] +
    Sum[PrimeDivisorSum[k] PrimePartitionCount[n - k], {k, n - 1}])/n

---

If you want to see the actual partitions themselves, however, you will need to solve the Frobenius coin problem.