algorithm to determine if a number is made of sum of multiply of two other number

Question

let say it's given 2k+2+3p=n as the test, how to find out the test is true for a number is valid for a number when k>=0, p>=0, n>=0:

example1 : n=24 should result true since k=5 & p=4 => 2(5)+2+3(4)=24

example2 : n=11 should result true since k=0 & p=3 => 2(0)+2+3(3)=11

example3 : n=15 should result true since k=5 & p=1 => 2(5)+2+3(1)=15

i wonder if there is a mathematic solution to this. i solved it like bellow:

//let say 2k+2+3p=n
var accepted = false;
var betterNumber= n-2;
//assume p=0
var kReminder= (betterNumber)%2==0;
//assume k=0
var pReminder= (betterNumber)%3==0;

if (kReminder || pReminder){
    accepted=true;
}else{
    
    var biggerChunk= Math.Max(2,3); //max of 2k or 3p, here i try to find the bigger chunk of the 
    var smallerChunk= Math.Min(2,3);

    if ((betterNumber%bigger)%smallerChunk==0){
        accepted=true;
    }else
    {
        accepted=false;
    }    
}

still there are edge cases that i didn't see. so i wonder if it has a better solution or not.

Update

the test above is just an example. the solution should be efficient enough for big numbers or any combination of number like 1000000k+37383993+37326328393p=747437446239902

Answer 1

Dave already gave a constructive and efficient answer but I'd like to share some math behind it.

For some time I'll ignore the + 2 part as it is of less significance and concentrate on a generic form of this question: given two positive integers a and b check whether number X can be represented as k*a + m*b where k and m are non-negative integers. The Extended Euclidean algorithm essentially guarantees that:

1. If number X is not divisible by GCD(a,b), it can't be represented as k*a + m*b with integer k and m

2. If number X is divisible by GCD(a,b) and is greater or equal than a*b, it can be represented as k*a + m*b with non-negative integer k and m. This follows from the fact that d = GCD(a,b) can be represented in such a form (let's call it d = k0*a + m0*b). If X = Y*d then X = (Y*k0)*a + (Y*m0)*b. If one of those two coefficients is negative you can trade one for the other adding and subtracting a*b as many times as required as in X = (Y*k0 + b)*a + (Y*m0 - a)*b. And since X >= a*b you can always get both coefficients to be non-negative in such a way. (Note: this is obviously not the most efficient way to find a suitable pair of those coefficients but since you only ask for whether such coefficients exist it should be sufficient.)

3. So the only gray area is numbers X divisible by GCD(a,b) that lie between in the (0, a*b) range. I'm not aware of any general rule about this area but you can check it explicitly.

So you can just do pre-calculations described in #3 and then you can answer this question pretty much immediately with simple comparison + possibly checking against pre-calculated array of booleans for the (0, a*b) range.

If you actual question is about k*a + m*b + c form where a, b and c are fixed, it is easily converted to the k*a + m*b question by just subtracting c from X.

Update (Big values of a and b)

If your a and b are big so you can't cache the (0, a*b) range beforehand, the only idea I have is to do the check for values in that range on demand by a reasonably efficient algorithm. The code goes like this:

function egcd(a0, b0) {
    let a = a0;
    let b = b0;
    let ca = [1, 0];
    let cb = [0, 1];

    while ((a !== b) && (b !== 0)) {
        let r = a % b;
        let q = (a - r) / b;
        let cr = [ca[0] - q * cb[0], ca[1] - q * cb[1]];
        a = b;
        ca = cb;
        b = r;
        cb = cr;
    }

    return {
        gcd: a,
        coef: ca
    };
}

function check(a, b, x) {
    let eg = egcd(a, b);
    let gcd = eg.gcd;
    let c0 = eg.coef;

    if (x % gcd !== 0)
        return false;

    if (x >= a * b)
        return true;

    let c1a = c0[0] * x / gcd;
    let c1b = c0[1] * x / gcd;
    if (c1a < 0) {
        let fixMul = -Math.floor(c1a / (b / gcd));
        let c1bFixed = c1b - fixMul * (a / gcd);
        return c1bFixed >= 0;
    }
    else { //c1b < 0
        let fixMul = -Math.floor(c1b / (a / gcd));
        let c1aFixed = c1a - fixMul * (b / gcd);
        return c1aFixed >= 0;
    }
}

The idea behind this code is based on the logic described in the step #2 above:

1. Calculate GCD and Bézout coefficients using the Extended Euclidean algorithm (if a and b are fixed, this can be cached, but even if not this is fairly fast anyway).
2. Check for conditions #1 (definitely no) and #2 (definitely yes) from the above
3. For value in the (0, a*b) range fix some coefficients by just multiplying Bézout coefficients by X/gcd. F
4. Find which of the two is negative and find the minimum multiplier to fix it by trading one coefficient for another.
5. Apply this multiplier to the other (initially positive) coefficient and check if it remains positive.

This algorithm works because all the possible solutions for X = k*a + m*b can be obtained from some base solution (k0, m0) using as (k0 + n*b/gcd, m0 + n*a/gcd) for some integer n. So to find out if there is a solution with both k >= 0 and m >= 0, all you need is to find the solution with minimum positive k and check m for it.

Complexity of this algorithm is dominated by the Extended Euclidean algorithm which is logarithmic. If it can be cached, everything else is just constant time.

Answer 2

Theorem: it is possible to represent number 2 and any number >= 4 using this formula.

Answer: the easiest test is to check if the number equals 2 or is greater or equals 4.

Proof: n=2k+2+3p where k>=0, p>=0, n>=0 is the same as n=2m+3p where m>0, p>=0 and m=k+1. Using p=0 one can represent any even number, e.g. with m=10 one can represent n=20. The odd number to the left of this even number can be represented using m'=m-2, p=1, e.g. 19=2*8+3. The odd number to the right can be represented with m'=m-1, p=1, e.g. 21=2*9+3. This rule holds for m greater or equal 3, that is starting from n=5. It is easy to see that for p=0 two additional values are also possible, n=2, n=4.

Answer 3

By inspection, 2 is the smallest valid even number and 5 is the smallest valid odd number:

2 is valid (k=0, p=0)
5 is valid (k=0, p=1)

All even numbers >= 2 and all odd numbers >= 5 are valid.
Even numbers: k=n/2-1, p=0
odd numbers: k=(n-3)/2-1, p=1

What we're doing here is incrementing k to add 2s to the smallest valid even and odd numbers to get all larger even and odd numbers.

All values of n >= 2 are valid except for 3.