15
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Jyrki Lahtonen Dec 7 '11 at 15:26
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Got it. Thanks. $\endgroup$ – user448810 Dec 9 '11 at 16:52
5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – J. M. is a poor mathematician Dec 7 '11 at 15:47
  • $\begingroup$ 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. $\endgroup$ – user448810 Dec 7 '11 at 16:31
  • $\begingroup$ 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? $\endgroup$ – user448810 Dec 7 '11 at 17:49
  • $\begingroup$ 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. $\endgroup$ – mjqxxxx Dec 8 '11 at 7:21
  • $\begingroup$ 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. $\endgroup$ – user448810 Dec 9 '11 at 16:51
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you please explain how to use the Euler transform to calculate the number of prime partitions? In detail? $\endgroup$ – user448810 Dec 7 '11 at 15:34
  • 1
    $\begingroup$ @user448810: Formulae 5-10 here are what you need. $\endgroup$ – J. M. is a poor mathematician Dec 7 '11 at 15:45
  • 1
    $\begingroup$ 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$. $\endgroup$ – joriki Dec 7 '11 at 16:01
1
$\begingroup$

https://www.dropbox.com/s/6diyuy3dijqkjvd/image1.jpeg?dl=0

See above link for image of a table for calculating recursively a(n)=A000607(n), the number of partitions of n into primes. It is easy to use and involves no complicated formulae. The first column is n, the second a(n), and subsequent columns record the contributions to a(n) associated with different primes, denoted in the top row by p'. Thus a(n) is the sum of the numbers recorded in the boxes (n,p') in the nth row, p denoting primes between 2 and n. As worked example here is how to calculate a(31). Note that the box at (31,31) is already filled in with number 1 (denoting that 31 is a prime partition of itself). To find the value for (31,p), count up to the box p squares above and add together the value in that box with those in all boxes in the same row to the right. Thus in box (31,2) the value is 67+14+4+1+1=87. Likewise in box (31,3) the value is 12+3+1+1=17. Similarly (31,5)=4, (31,7)=2, (31,31)=1 and the rest are zeroes. The sum of these numbers is a(n)= 87+17+4+2+1=111. Bingo! Enter these numbers in the table and they contribute to calculations for higher values of a(n).

If the count up from any box runs up through the top row then that value is 0. The 1 in the top row is "floating", that is to say can move to any box on the first row to attribute its value in any count ending on that square.

I don't know if this method is generally known, contact me if you are interested in how it works David.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.