Number of distinct prime partitions

Question

Possible Duplicate:
A number as it’s prime number parts

I have this homework assignment of mine, hard as hell, where I have to get all the distinct prime partitions of a given number. For example, number 7 has five different prime partitions (or five different ways of representing the 2 prime partitions it has):

5 + 2
2 + 5
3 + 2 + 2
2 + 3 + 2
2 + 2 + 3

As you can see, the number itself is excluded in the case it's a prime. I don't have to print all the distinct partitions, only the number of them.

So I'm a bit lost with this. I've been completely unable to produce any code, but I think I should approach this from a dynamic programming kind of view. I'm only asking for some hints. Has anyone got an idea? Thanks in advance.

The highest inputted number is 100. Also, the running time of the program cannot exceed 1 second, and the memory limit is 128 MB.

If I get you correctly, you have to find all the sums of primes leading to your input, am I right? — Gui13, Jan 18 '13 at 12:15
@stefan "a bit lost" was supposed to be sarcastic. Sorry about that. And of course I did. I was happily coding the array of all the primes below 100 and getting on with it, until I suddenly stopped and started staring at my computer screen in awe, and staying like that for 30 minutes, my only hope being the brainstorming monkey-orchestra inside my head trying to think of something useful. I think I managed to write the beginning of a for-loop, but I'm not sure. — Olavi Mustanoja, Jan 18 '13 at 12:29
primes to a 100 is easy, like e.g. [here](http://stackoverflow.com/a/12543821/849891). Next, dynamic programming (memoization). — Will Ness, Jan 19 '13 at 09:28
Duplicate: http://stackoverflow.com/questions/14218882/a-number-as-its-prime-number-parts/14219154 and http://stackoverflow.com/questions/7941680/how-can-i-find-the-number-of-ways-a-number-can-be-expressed-as-a-sum-of-primes - and one of those is also by you, Olavi! — Eamon Nerbonne, Jan 19 '13 at 13:32

score 2 · Answer 1 · answered Jan 18 '13 at 15:23

To solve this one you are going to need to combine three ideas:

Say the given number is n:

find all primes less than n, as shown here.
dynamically calculate the subset sum from your prime array and n. A few hints are here and here
then, calculate the number of distinct permutations of each answer you get from step two, as here.

Now of course, this is just a hint. But it should help you a great deal to cook up your final code.

Ivaylo Strandjev · Answer 2 · 2013-01-18T12:21:40.120

1

You can not improve the brute force here too much unfortunately. One thing you should definitely do is to use an sieve of Eratosthenes to precalculate all the prime numbers up to a given number. After that given a number N recursively print all its partitions where the smallest prime number is each prime from the list of prime numbers consecutively(remember to have it being the smallest one so that you don't repeat partitions).

EDIT: after knowing you only need to know the count of partitions: best solution would be to use dynamic programming. Again you will need to memoize in an array with two dimensions mem[MAX_SIZE][MAX_SIZE] first index being the number you are computing the solution for and the second index being the index of the minimum prime number you should use for the partition.

edited Jan 18 '13 at 12:21

answered Jan 18 '13 at 12:01

Ivaylo Strandjev

69,226
18
123
176

Ah! I forgot to mention: The highest possible input is 100, so I could simply make an array of all the primes below 100. EDIT: oh, and the answer for 80 is known to be 10343662267187, so I think the recursive method is a no-no. I'll edit the description a bit. – Olavi Mustanoja Jan 18 '13 at 12:05
@OlaviMustanoja: In that case, [*memoization*](http://en.wikipedia.org/wiki/Memoization) may help... – Oliver Charlesworth Jan 18 '13 at 12:14
@Olavi you only care about the **count**? This changes the problem completely. – Ivaylo Strandjev Jan 18 '13 at 12:18
@Ivaylo Yes. It reads right there: "I don't have to print all the distinct partitions, only the number of them." – Olavi Mustanoja Jan 18 '13 at 12:22
@OlaviMustanoja I should have missed that sorry :) – Ivaylo Strandjev Jan 18 '13 at 12:22
printing would be great fun to watch for several months :D – stefan Jan 18 '13 at 12:23
@OlaviMustanoja: Hmm, I get 1381018419 for an input of 80... – Oliver Charlesworth Jan 18 '13 at 12:47
@Oli maybe you do not count `5+2` and `2+5` as different? – Ivaylo Strandjev Jan 18 '13 at 12:49
@IvayloStrandjev: I do count them as different. – Oliver Charlesworth Jan 18 '13 at 12:50
@IvayloStrandjev: Ah, no false alarm. I had overflow with an `int`! – Oliver Charlesworth Jan 18 '13 at 12:56
This is something completely new for me... What is this and how do I do it? – Olavi Mustanoja Jan 18 '13 at 13:23
@OlaviMustanoja better have a look [here](http://en.wikipedia.org/wiki/Dynamic_programming) – Ivaylo Strandjev Jan 18 '13 at 13:24

score 1 · Answer 3 · answered Jan 18 '13 at 12:18

So, in the form of hints as opposed to an answer:

As has been said elsewhere, you can precompute the primes.
Can you reuse results from a smaller number? So, assuming you know the actual permutations for 5, does this help you find any of the actual permutations for 7?
Is there any structure to the results, and if so, can you use that structure to avoid repeating calculations? For example, you list 5 permutations for number 7, but these exhibit some similarity to each other - is that a general trend, and what is it?
Assuming you find internal structure and can use smaller results to help find larger ones, can you do both - can you entirely avoid storing the complete intermediate results?
Finally, do you need to list each ordered combination or just return the number of ordered combinations? You may be able to save computation here.

score 1 · Answer 4 · edited Jul 23 '17 at 17:59

You may want to look at the mathematics of partitions at Wikipedia in particular the sections on the Generating Function and on Restricted Partition Generating Functions about half-way down the page. It mentions a generating function for partitions consisting of particular summands (specified by a set T of natural numbers).

Let the number of non-order-dependent prime-partitions of the number n be R(n). You can derive R(n) from the generating function by taking the n-th partial derivative w.r.t x and setting then x = 0. This may not be easy.

One caveat: these partitions are not order dependent (i.e. 1 + 2 and 2 + 1 are counted only as one partition).

That caveat matters, unfortunately: when order-dependant, the *identity* of the primes it consists of matters since duplicates result in fewer distinct orderings. It's likely to be hard or impossible to find a closed form solution for this reason. — Eamon Nerbonne, Jan 18 '13 at 13:30

Number of distinct prime partitions

4 Answers4

Linked