3

Possible Duplicate:
Generating the partitions of a number

Prime number sum

The number 7 can be expressed in 5 ways as a sum of primes:

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

Make a program that calculates, in how many ways number n can be expressed as a sum of primes. You can assume that n is a number between 0-100. Your program should print the answer in less than a second

Example 1:
Give number: 7 Result: 5

Example 2:
Give number: 20 Result: 732

Example 3:
Give number: 80 Result: 10343662267187

I've been at this problem for hours. I can't figure out how to get n from (n-1). Here are the sums from the first 30 numbers by a tree search

0 0 0 1 2 2 5 6 10 16 19 35 45 72 105 152 231 332 500 732 1081 1604 2351 3493 5136 7595 11212 16534 24441

I thought I had something with finding the biggest chain 7 = 5+2 and somehow using the knowledge that five can be written as 5, 3+2, 2+3, but somehow I need to account for the duplicate 2+3+2 replacement.

Community
  • 1
  • 1
ahathoor
  • 101
  • 2
  • 6

3 Answers3

4

Look up dynamic programming, specifically Wikipedia's page and the examples there for the fibonacci sequence, and think about how you might be able to adapt that to your problem here.

Kevin
  • 53,822
  • 15
  • 101
  • 132
  • I'm looking at it. But did you look at the number sequence I posted? – ahathoor Oct 29 '11 at 21:36
  • I'm writing it to double check, but I believe dynamic programming should accout for duplicates. – Kevin Oct 29 '11 at 21:44
  • Upon further work/reflection, this may not be the right way to go. If you get all the unique sets of sums (which shouldn't be that hard, I'm thinking n^2 worst case?), you can mathematically calculate the number of permutations of each set. – Kevin Oct 30 '11 at 00:26
2

Okay so this is a complicated problem. you are asking how to write code for the Partition Function; I suggest that you read up on the partition function itself first. Next you should look at algorithms to calculate partitions. It is a complex subject here is a starting point ... Partition problem is [NP complete] --- This question has already been asked and answered here and that may also help you start with algorithms.

Community
  • 1
  • 1
Ahmed Masud
  • 21,655
  • 3
  • 33
  • 58
-1

There're several options. Since you know the number is between 0-100, there is the obvious: cheat, simply make an array and fill in the numbers.

The other way would be a loop. You'd need all the primes under 100, because a number which is smaller than 100 can't be expressed using the sum of a prime which is larger than 100. Eg. 99 can't be expressed as the sum of 2 and any prime larger than 100.

What you also know is: the maximum length of the sum for even numbers is the number divided by 2. Since 2 is the smallest prime. For odd numbers the maximum length is (number - 1) / 2.

Eg. 8 = 2 + 2 + 2 + 2, thus length of the sum is 4
9 = 2 + 2 + 2 + 3, thus length of the sum is 4

If you want performance you could cheat in another way by using GPGPU, which would significantly increase performance.

Then they're is the shuffling method. If you know 7 = 2 + 2 + 3, you know 7 = 2 + 3 + 2. To do this you'd need a method of calculating the different possibilities of shuffling. You could store the combinations of possibilities or keep them in mind while writing your loop.

Here is a relative brute force method (in Java):

int[] primes = new int[]{/* fill with primes < 100 */};
int number = 7; //Normally determined by user
int maxLength = (number % 2 == 0) ? number / 2 : (number - 1) / 2; //If even number maxLength = number / 2, if odd, maxLength = (number - 1) / 2
int possibilities = 0;    

for (int i = 1; i <= maxLength; i++){   
    int[][] numbers = new int[i][Math.pow(primes.length, i)]; //Create an array which will hold all combinations for this length
    for (int j = 0; j < Math.pow(primes.length, i); j++){ //Loop through all the possibilities
        int value = 0; //Value for calculating the numbers making up the sum
        for (int k = 0; k < i; k++){
            numbers[k][j] = primes[(j - value) % (Math.pow(primes.length, k))]; //Setting the numbers making up the sum
            value += numbers[k][j]; //Increasing the value
        }
    }
    for (int x = 0; x < primes.length; x++){
        int sum = 0;
        for (int y = 0; y < i; y++){
            sum += numbers[y];
            if (sum > number) break; //The sum is greater than what we're trying to reach, break we've gone too far
        }
        if (sum == number) possibilities++;
    }
}

I understand this is complicated. I will try to use an analogy. Think of it as a combination lock. You know the maximum number of wheels, which you have to try, hence the "i" loop. Next you go through each possibility ("j" loop) then you set the individual numbers ("k" loop). The code in the "k" loop is used to go from the current possibility (value of j) to the actual numbers. After you entered all combinations for this amount of wheels, you calculate if any were correct and if so, you increase the number of possibilities.

I apologize in advance if I made any errors in the code.

Boude
  • 677
  • 6
  • 13