Prime Partition

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

Solution 2:

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.

Solution 3:

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