Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for an algorithm that will partition a positive integer into distinct primes. The number of partitions is given by this OEIS sequence: https://oeis.org/A000586

To be more specific, I am only interested in sets of 5 primes that add up to the original number, and I would like to get all possible such partitions for each number.

Is anyone aware of an algorithm along these lines?

share|improve this question
1  
Can you assume that you have a list of the primes below $n$? If so an algorithm to do what you want is trivial: you write $f(n,k)$ which lists the partitions of $n$ into a sum of $k$ primes, and for each prime $j<n$ you call $f(n-j, k-1)$. Your base case if $f(n,1)=\{n\}$ if $n$ is prime, and $f(n,1)=\{\}$ otherwise. This will probably scale quite horribly (maybe worse than exponentially) although you will be able to improve the performance significantly by memoization. –  Chris Taylor Jun 15 '11 at 10:54
    
I can use a sieve to get the primes if needed. I was interested in seeing if there are any cleverer than trivial-but-slow algorithms out there. –  Alexandros Marinos Jun 15 '11 at 10:56

1 Answer 1

up vote 4 down vote accepted

The first step is to consider whether 2 is included. Since other primes are odd, 2 is included if you are trying to finad partitions of an even number into an odd number of distict primes or an odd number into an even number of distinct primes; 2 is excluded otherwise.

The next step is consider the partition of $n$ into $k$ distinct odd primes less than or equal to $m$ (there is no point looking at $m$ greater than the difference between $n$ and the sum of the first $k-1$ odd primes). If $k=1$ then test whether $n$ is prime. If $k>1$ then the largest part is greater than $\frac{n}{k}$ but less than or equal to $m$. So you can choose a set of primes in this range as potential parts; if one of these is $p$ then you then next need to find partitions of $n-p$ into $k-1$ distinct odd primes less than or equal to $p-2$, which takes you back to the beginning of this step.

There may be stages where the same question is being asked several times, and so it may be more efficient to precalculate solutions

As an illustration, take the partition of 40 into five distinct primes. 40 is even and five is odd so 2 must be a part.

Now we want paritions of 38 into four distinct odd primes. The largest part must be more than $\frac{38}{4}$ and less than or equal to $38-3-5-7$, so must be in $\{ 11,13,17,19,23\}$. Consider these in turn.

  • We want partitions of 27 into three distinct odd primes less than or equal to 9. That is not possible since they must also be greater than $\frac{27}{3}$.

  • We want partitions of 25 into three distinct odd primes less than or equal to 11. The largest part must also be greater than $\frac{25}{3}$ so the only possibility for the largest part is 11, leaving us to look for partitions of 14 into two distinct odd primes less than or equal to 9, which at the next stage will turn out not to be possible since there are no primes greater than 7 and less than or equal to 9.

  • We want partitions of 21 into three distinct odd primes less than or equal to 15, though we can reduce this 15 to $21-3-5=13$. The largest part must also be greater than $\frac{21}{3}$,so must be in $\{ 11,13\}$, leaving us to look for leaving us to look for partitions of 10 into two distinct odd primes less than or equal to 9 (reduce to $10-3=7$) [which at the next step will give us $3+7$], and for partitions of 8 into two distinct odd primes less than or equal to 11 (reduce to $8-3=5$) [which at the next step will give us $3+5$]. So reconstructing back to the start, this gives us the partitions $2+3+7+11+17$ and $2+3+5+13+17$.

  • We want partitions of 19 into three distinct odd primes less than or equal to 17, though we can reduce this 17 to $19-3-5=11$. The largest part must also be greater than $\frac{19}{3}$, so must be in $\{7,11\}$, leaving us to look for partitions of 12 into two distinct odd primes less than or equal to 5 (not possible), and for partitions of 8 into two distinct odd primes less than or equal to 9 (reduce to $8-3=5$) [we have already found $3+5$]. So reconstructing back to the start, this gives us the partition $2+3+5+11+19$.

  • We want partitions of 15 into three distinct odd primes less than or equal to 23, though we can reduce this 23 to $15-3-5=7$. The largest part must also be greater than $\frac{15}{3}$, so must be in $\{7\}$, leaving us to look for partitions of 8 into two distinct odd primes less than or equal to 5 [we have already found $3+5$]. So reconstructing back to the start, this gives us the partition $2+3+5+7+23$.

So this method does indeed the four desired partitions of 40.

share|improve this answer
    
This is excellent, thank you. Will code it up and see how it goes. –  Alexandros Marinos Jun 15 '11 at 11:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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