I'm interested in finding out whether there exists a prime partition of a given positive integer $N>1$ such that the partition has specific number of parts.

For instance, as given in another question, $N=12$ has seven partitions: $\{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\}$. So there exist partitions of length 2, 3, 4, 5, 6 and no partition of length 1 (obviously).

So given an integer $N$ and a partition length ($\leq N/2$), is there an effective way of constructing or verifying the existence of a prime partition of the given length (particularly for large values of $N$, so simply computing primes up to $N$ and searching is not an option)?

I've seen the formulae on computing the total number of prime partitions (e.g. Prime Partition and http://programmingpraxis.com/2012/10/19/prime-partitions/), but I see no clear way of relating this to specific partition sizes.



In general this seems like a very difficult problem. Indeed, when partition length$=2$ and $N>2$ is even, this question is an instance of the longstanding Goldbach's Conjecture.

  • $\begingroup$ Absolutely, and I believe I read somewhere that this strong version of Goldbach's conjecture has been verified up to ~$10^{18}$, so that's certainly useful. But it's not immediately clear how it would help for arbitrary partition length. $\endgroup$ – user3638633 May 21 '14 at 22:01

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.