# Number of distinct prime partitions

Page 1 of 1

## 3 Replies - 1164 Views - Last Post: 18 January 2013 - 05:34 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=307850&amp;s=27f4a04226eaa2f1ff124fc7c54ea31e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 statistician

Reputation: 0
• Posts: 4
• Joined: 18-January 13

# Number of distinct prime partitions

Posted 18 January 2013 - 04:25 AM

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

Is This A Good Question/Topic? 0

## Replies To: Number of distinct prime partitions

### #2 Aphex19

• Born again Pastafarian.

Reputation: 619
• Posts: 1,873
• Joined: 02-August 09

## Re: Number of distinct prime partitions

Posted 18 January 2013 - 04:54 AM

I think the first step would be to generate all the prime numbers up to the number you're finding the partitions for and store them in an array. As for calculating the amount of partitions, I don't think I could offer much useful advice, but I found an interesting paper on the topic, here. This is also worth a look.

edit: The mathematics behind the paper I linked is summarized here.

This post has been edited by Aphex19: 18 January 2013 - 04:57 AM

### #3 statistician

Reputation: 0
• Posts: 4
• Joined: 18-January 13

## Re: Number of distinct prime partitions

Posted 18 January 2013 - 05:02 AM

Aphex19, on 18 January 2013 - 04:54 AM, said:

I think the first step would be to generate all the prime numbers up to the number you're finding the partitions for and store them in an array. As for calculating the amount of partitions, I don't think I could offer much useful advice, but I found an interesting paper on the topic, here. This is also worth a look.

edit: The mathematics behind the paper I linked is summarized here.

I was thinking of making an array of all the usable primes too, but that's as far as I go. I've tried studying various topics almost identical to those you listed, but they are of little help in my case. They get all the partitions only once and with all numbers, not only primes (this would be, I think, easily tweakable tho).

### #4 Aphex19

• Born again Pastafarian.

Reputation: 619
• Posts: 1,873
• Joined: 02-August 09

## Re: Number of distinct prime partitions

Posted 18 January 2013 - 05:34 AM

If you were to ignore efficiency and primes (for now), I think that a brute force algorithm is feasible. It seems possible to iterate through all values up to the number being partitioned, assessing all possible permutations of the values.

e.g, for the number 3.
1: 1, 2, 3
2: 1+1, 1+2, 1+3, 2+2, 3+3
3: 1+1+1, 1+1+2, 1+1+3, 2+1+1, 2+1+2, 2+1+3, 2+2+2, 2+3+3, 3+1+1, 3+1+2, 3+2+2, 2+3+2, 1+3+3... (etc)

Sorry if some potential partitions are missing (or are redundant) there, that's just an example.

This post has been edited by Aphex19: 18 January 2013 - 05:43 AM