# 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?

-
@J.M. Any chance of you writing that recursive algorithm as an answer? That may be the most helpful thing for the OP? – Jyrki Lahtonen Dec 7 '11 at 19:41
@Jyrki: What, the one in the comments to joriki's? I suppose... – J. M. Dec 7 '11 at 21:50

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

-
I agree with other posters. This is not a practical way of calculating the prime partition function. Generating functions related to partitions are mostly a theoretical tool. Though sometimes the theory leads to efficient algorithms (google "pentagonal numbers" for an example). – Jyrki Lahtonen Dec 7 '11 at 15:26

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.

-
Got it. Thanks. – user448810 Dec 9 '11 at 16:52

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

-
Yep, this is essentially the Frobenius problem. Generate the first $n$ primes, and count how many ways to represent $n$ in terms of those primes. – J. M. Dec 7 '11 at 15:47
I'm looking at your recursion. B(12,2) is 1: {2 2 2 2 2 2}. B(12,3) and B(12,4) are 3: the partition from B(12,2) plus {2 2 2 3 3} and {3 3 3 3}. B(12,5) and B(12,6) are 5: the partitions from B(12,3) plus {2 2 3 5} and {2 5 5}. B(12,7) through B(12,10) are 7: the partitions from B(12,5) plus {2 3 7} and {5 7}. B(12,11) and B(12,12) are also 7, as there are no partitions involving 11. – user448810 Dec 7 '11 at 16:31
I must be slow today. There are some obvious recursive bases. If $n<2$, then $b(n,p)=0$. If $n<p$, then $b(n,p)=b(n,q)$, where $q$ is the largest prime not greater than $p$. If $p$ is not prime, then $b(n,p)=b(n,q)$ where q is the largest prime not greater than $p$. If $p=2$, then $b(n,p)=0$ if $n$ is odd and $b(n,p)=1$ if $n$ is even. But what happens in the general case? – user448810 Dec 7 '11 at 17:49
In the general case, $b(n,p) = \sum_{q\le p}\sum_{i\ge 1}b(n-qi,q-1)$, where $q$ is restricted to primes. In other words, sum over the possibilities for the size and multiplicity of the largest prime in the partition. – mjqxxxx Dec 8 '11 at 7:21
I still don't get it. Consider b(12,5). The correct answer is 5, the sets {2 2 2 2 2 2}, {2 2 2 3 3}, {3 3 3 3}, {2 2 3 5} and {2 5 5}. In your formula the q are 2, 3 and 5, the corresponding maximum i that keep the first parameter of the inner b positive are 5, 3 and 2, and the non-zero b(n-qi,q-1) are b(6,2)=1, b(7,4)=1, and b(2,4)=1, for a sum of 3. What have I done wrong? I thought of changing the lower bound on i from 1 to 0, but that doesn't work either. – user448810 Dec 9 '11 at 16:51

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.

-
Can you please explain how to use the Euler transform to calculate the number of prime partitions? In detail? – user448810 Dec 7 '11 at 15:34
@user448810: Formulae 5-10 here are what you need. – J. M. Dec 7 '11 at 15:45
Here are the first few terms of the sequence $a$ and the sequences $c$ and $b$ computed using formulas 7 and 8, respectively: $a: 0,1,1,0,1,0,1,\dotsc$, $c: 0,2,3,2,5,5,7,\dotsc$, $b:0,1,1,1,2,2,3,\dotsc$. – joriki Dec 7 '11 at 16:01