How can I find the number of ways to express a number as a sum of primes?

Question

Possible duplicate:
Creating Number Partitions

Amount of the main number

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

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

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

Example 1:
Give number: 7 Result: 5

Example 2:
Give number: 20 Result: 732

Example 3:
Give the number: 80 Result: 10343662267187

I have been dealing with 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 searching the tree

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 largest chain 7 = 5 + 2 and somehow, using the knowledge that five could be written as 5, 3 + 2, 2 + 3, but for some reason then I need to consider duplicate 2+ 3 + 2.

Answer 1

Take a look at dynamic programming, namely the Wikipedia page and examples for the Fibonacci sequence, and think about how you could adapt this to your problem here.

Answer 2

Good, so this is a difficult problem. you ask how to write code for a split function; I suggest you first read about the section function itself . Then you should look at the algorithms for calculating partitions. This is a difficult question here is the starting point ... Section problem - [NP complete] --- This question has already been asked and answered here , and it can also help you get started with algorithms.

Answer 3

There are several options. Since you know that the number is between 0-100, there is the obvious: cheat, just create an array and fill in the numbers.

Another way would be a loop. You will need all primes up to 100, because a number that is less than 100 cannot be expressed using the sum of a prime number that is more than 100. For example. 99 cannot be expressed as the sum of 2 and any prime is greater than 100.

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

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

If you want to increase productivity, you can cheat in another way using GPGPU, which will significantly increase productivity.

Then this is a shuffle method. If you know 7 = 2 + 2 + 3, you know 7 = 2 + 3 + 2. To do this, you will need a method for calculating the various shuffling options. You can store combinations of features or consider them when writing a loop.

Here is the 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 that it is difficult. I will try to use an analogy. Think of it as a combination lock. You know the maximum number of wheels that you should try, therefore, the "i" cycle. Then you look at each opportunity (cycle "j"), then you set individual numbers (cycle "k"). The code in the loop "k" is used to move from the current opportunity (value j) to the actual numbers. After you have entered all the combinations for this number of wheels, you will calculate whether they were correct, and if so, then you will increase the number of possibilities.

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