Minimum number of different primes that sum to x

Question

How can we develop a dynamic programming algorithm that calculates the minimum number of different primes that sum to x?

Assume the dynamic programming calculates the minimum number of different primes amongst which the largest is p for each couple of x and p. Can someone help?

Answer 1

First of all, you need a list of primes up to x. Let's call this array of integers primes.

Now we want to populate the array answer[x][p], where x is the sum of primes and p is maximum for each prime in the set (possibly including, but not necessarily including p).

There are 3 possibilities for answer[x][p] after all calculations:

1) if p=x and p is prime => answer[x][p] contains 1

2) if it's not possible to solve problem for given x, p => answer[x][p] contains -1

3) if it's possible to solve problem for given x, p => answer[x][p] contains number of primes

There is one more possible value for answer[x][p] during calculations:

4) we did not yet solve the problem for given x, p => answer[x][p] contains 0

It's quite obvious that 0 is not the answer for anything but x=0, so we are safe initializing array with 0 (and making special treatment for x=0).

To calculate answer[x][p] we can iterate (let q is prime value we are iterating on) through all primes up to (including) p and find minimum over 1+answer[x-q][q-1] (do not consider all answer[x-q][q-1]=-1 cases though). Here 1 comes for q and answer[x-q][q-1] should be calculated in recursive call or before this calculation.

Now there's small optimization: iterate primes from higher to lower and if x/q is bigger than current answer, we can stop, because to make sum x we will need at least x/q primes anyway. For example, we will not even consider q=2 for x=10, as we'd already have answer=3 (actually, it includes 2 as one of 3 primes - 2+3+5, but we've already got it through recursive call answer(10-5, 4)), since 10/2=5, that is we'd get 5 as answer at best (in fact it does not exist for q=2).

package ru.tieto.test;

import java.util.ArrayList;

public class Primers {

    static final int MAX_P = 10;
    static final int MAX_X = 10;
    public ArrayList<Integer> primes= new ArrayList<>();
    public int answer[][] = new int[MAX_X+1][MAX_P+1];

    public int answer(int x, int p) {
        if (x < 0)
            return -1;
        if (x == 0)
            return 0;
        if (answer[x][p] != 0)
            return answer[x][p];

        int max_prime_idx = -1;
        for (int i = 0; 
             i < primes.size() && primes.get(i) <= p && primes.get(i) <= x; 
             i++)
            max_prime_idx = i;

        if (max_prime_idx < 0) {
            answer[x][p] = -1;
            return -1;
        }

        int cur_answer = x+1;
        for (int i = max_prime_idx; i >= 0; i--) {
            int q = primes.get(i);
            if (x / q >= cur_answer)
                break;
            if (x == q) {
                cur_answer = 1;
                break;
            }
            int candidate = answer(x-q, q-1);
            if (candidate == -1)
                continue;
            if (candidate+1 < cur_answer)
                cur_answer = candidate+1;
        }

        if (cur_answer > x)
            answer[x][p] = -1;
        else
            answer[x][p] = cur_answer;

        return answer[x][p];
    }


    private void make_primes() {
        primes.add(2);

        for (int p = 3; p <= MAX_P; p=p+2) {
            boolean isPrime = true;
            for (Integer q : primes) {
                if (q*q > p)
                    break;
                if (p % q == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
                primes.add(p);
        }
//      for (Integer q : primes)
//          System.out.print(q+",");
//      System.out.println("<<");       
    }

    private void init() {
        make_primes();
        for (int p = 0; p <= MAX_P; p++) {
            answer[0][p] = 0;
            answer[1][p] = -1;
        }
        for (int x = 2; x <= MAX_X; x++) {
            for (int p = 0; p <= MAX_P; p++)
                answer[x][p] = 0;
        }

        for (Integer p: primes)
            answer[p][p] = 1;
    }

    void run() {
        init();
        for (int x = 0; x <= MAX_X; x++)
            for (int p = 0; p <= MAX_P; p++)
                answer(x, p);
    }

    public static void main(String[] args) {
        Primers me = new Primers();
        me.run();

//      for (int x = 0; x <= MAX_X; x++) {
//          System.out.print("x="+x+": {");
//          for (int p = 0; p <= MAX_P; p++) {
//              System.out.print(String.format("%2d=%-3d,",p, me.answer[x][p]));
//          }
//          System.out.println("}");
//      }
    }

}

Answer 2

Assuming you're not using goldbach conjecture, otherwise see Peter de Rivaz excellent answer, :

dynamic programming generally takes advantage of overlapping subproblems. Usually you go top down, but in this case bottom up may be simpler

I suggest you sum various combinations of primes.

lookup = {}
for r in range(1, 3):
   for primes in combinations_with_replacement(all_primes, r):
        s = sum(primes)
        lookup[s] = lookup.get(s, r) //r is increasing, so only set it if it's not already there

this will start getting slow very quickly if you have a large number of primes, in that case, change max r to something like 1 or 2, whatever the max that is fast enough for you, and then you will be left with some numbers that aren't found, to solve for a number that doesnt have a solution in lookup, try break that number into sums of numbers that are found in lookup (you may need to store the prime combos in lookup and dedupe those combinations).

Answer 3

Start with a list of all primes lower than x. Take the largest. Now we need to solve the problem for (x - pmax). At this stage, that will be easy, x - pmax will be low. Mark all the primes as "used" and store solution 1. Now take the largest prime still in the list and repeat until all the primes are either used or rejected. If (x - pmax) is high, the problem gets more complex.

That's your first pass, brute force algorithm. Get that working first before considering how to speed things up.

Answer 4

If we assume the Goldbach conjecture is true, then every even integer > 2 is the sum of two primes.

So we know the answer if x is even (1 if x==2, or 2 otherwise).

If x is odd, then there are 3 cases:

1. x is prime (answer is 1)
2. x-2 is prime (answer is 2)
3. otherwise x-3 is an even number bigger than 2 (answer is 3)