how to find the minimum number of primatics that sum to a given number

Question

Given a number N (<=10000), find the minimum number of primatic numbers which sum up to N.

A primatic number refers to a number which is either a prime number or can be expressed as power of prime number to itself i.e. prime^prime e.g. 4, 27, etc.

I tried to find all the primatic numbers using seive and then stored them in a vector (code below) but now I am can't see how to find the minimum of primatic numbers that sum to a given number.

Here's my sieve:

#include<algorithm>
#include<vector>

#define MAX 10000

typedef long long int ll;

ll modpow(ll a, ll n, ll temp) {
    ll res=1, y=a;
    while (n>0) {
        if (n&1)
            res=(res*y)%temp;
        y=(y*y)%temp;
        n/=2;
    }
    return res%temp;
}


int isprimeat[MAX+20];

std::vector<int> primeat;

//Finding all prime numbers till 10000
void seive()
{
    ll i,j;
    isprimeat[0]=1;
    isprimeat[1]=1;
    for (i=2;  i<=MAX;  i++) {
        if (isprimeat[i]==0) {
            for (j=i*i;  j<=MAX;  j+=i) {
                isprimeat[j]=1;
            }
        }
    }
    for (i=2;  i<=MAX;  i++) {
        if (isprimeat[i]==0) {
            primeat.push_back(i);
        }
    }

    isprimeat[4]=isprimeat[27]=isprimeat[3125]=0;
    primeat.push_back(4);
    primeat.push_back(27);
    primeat.push_back(3125);
}

int main()
{
    seive();
    std::sort(primeat.begin(), primeat.end());
    return 0;
}

Answer 1

One method could be to store all primatics less than or equal to N in a sorted list - call this list L - and recursively search for the shortest sequence. The easiest approach is "greedy": pick the largest spans / numbers as early as possible.

for N = 14 you'd have L = {2,3,4,5,7,8,9,11,13}, so you'd want to make an algorithm / process that tries these sequences:

1. 13 is too small
2. 13 + 13 -> 13 + 2 will be too large
3. 11 is too small
4. 11 + 11 -> 11 + 4 will be too large
5. 11 + 3 is a match.

You can continue the process by making the search function recurse each time it needs another primatic in the sum, which you would aim to have occur a minimum number of times. To do so you can pick the largest -> smallest primatic in each position (the 1st, 2nd etc primatic in the sum), and include another number in the sum only if the primatics in the sum so far are small enough that an additional primatic won't go over N.

I'd have to make a working example to find a small enough N that doesn't result in just 2 numbers in the sum. Note that because you can express any natural number as the sum of at most 4 squares of natural numbers, and you have a more dense set L than the set of squares, so I'd think it rare you'd have a result of 3 or more for any N you'd want to compute by hand.

Dynamic Programming approach

I have to clarify that 'greedy' is not the same as 'dynamic programming', it can give sub-optimal results. This does have a DP solution though. Again, i won't write the final process in code but explain it as a point of reference to make a working DP solution from.

To do this we need to build up solutions from the bottom up. What you need is a structure that can store known solutions for all numbers up to some N, this list can be incrementally added to for larger N in an optimal way.

Consider that for any N, if it's primatic then the number of terms for N is just 1. This applies for N=2-5,7-9,11,13,16,17,19. The number of terms for all other N must be at least two, which means either it's a sum of two primatics or a sum of a primatic and some other N.

The first few examples that aren't trivial:

6 - can be either 2+4 or 3+3, all the terms here are themselves primatic so the minimum number of terms for 6 is 2.

10 - can be either 2+8, 3+7, 4+6 or 5+5. However 6 is not primatic, and taking that solution out leaves a minimum of 2 terms.

12 - can be either 2+10, 3+9, 4+8, 5+7 or 6+6. Of these 6+6 and 2+10 contain non-primatics while the others do not, so again 2 terms is the minimum.

14 - ditto, there exist two-primatic solutions: 3+11, 5+9, 7+7.

The structure for storing all of these solutions needs to be able to iterate across solutions of equal rank / number of terms. You already have a list of primatics, this is also the list of solutions that need only one term.

Sol[term_length] = list(numbers). You will also need a function / cache to look up some N's shortest-term-length, eg S(N) = term_length iif N in Sol[term_length]

Sol[1] = {2,3,4,5 ...} and Sol[2] = {6,10,12,14 ...} and so on for Sol[3] and onwards.

Any solution can be found using one term from Sol[1] that is primatic. Any solution requiring two primatics will be found in Sol[2]. Any solution requiring 3 will be in Sol[3] etc.

What you need to recognize here is that a number S(N) = 3 can be expressed Sol[1][a] + Sol[1][b] + Sol[1][c] for some a,b,c primatics, but it can also be expressed as Sol[1][a] + Sol[2][d], since all Sol[2] must be expressible as Sol[1][x] + Sol[1][y].

This algorithm will in effect search Sol[1] for a given N, then look in Sol[1] + Sol[K] with increasing K, but to do this you will need S and Sol structures roughly in the form shown here (or able to be accessed / queried in a similar manner).

Working Example

Using the above as a guideline I've put this together quickly, it even shows which multi-term sum it uses.

https://ideone.com/7mYXde

I can explain the code in-depth if you want but the real DP section is around lines 40-64. The recursion depth (also number of additional terms in the sum) is k, a simple dual-iterator while loop checks if a sum is possible using the kth known solutions and primatics, if it is then we're done and if not then check k+1 solutions, if any. Sol and S work as described.

The only confusing part might be the use of reverse iterators, it's just to make != end() checking consistent for the while condition (end is not a valid iterator position but begin is, so != begin would be written differently).

Edit - FYI, the first number that takes at least 3 terms is 959 - had to run my algorithm to 1000 numbers to find it. It's summed from 6 + 953 (primatic), no matter how you split 6 it's still 3 terms.