Fastest way to check whether ax+by+cz=d has positive integer solutions

[MARTHA]

Hi again..

What is the fastest way to check whether ax+by+cz=d has positive integer solutions, exact solutions are not required.

We know if gcd(a,b,c) is not a factor of d, it does not have solutions, but if it is factor it can not guarantee of existence of solution.

Is the problem far more complex than it seems?

[Dr Sardonicus]

Originally Posted by MARTHA

Hi again..

What is the fastest way to check whether ax+by+cz=d has positive integer solutions, exact solutions are not required.

We know if gcd(a,b,c) is not a factor of d, it does not have solutions, but if it is factor it can not guarantee of existence of solution.

Is the problem far more complex than it seems?

By dividing out gcd(a,b,c) you may assume that gcd(a,b,c) = 1. I believe there are good results in this case.

There is a well-known result in the two-variable case: if a and b are positive integers with gcd(a, b) = 1, then

a*x + b*y = N

is solvable in non-negative integers x and y for all N > a*b - a - b. So obviously, it will be solvable in positive x and y for N > a*b. You don't need to find exact solutions to know they exist.

Checking smaller N, I don't remember how to do that.

Now when you increase the number of variables, life becomes more complicated. In particular, you can have gcd(a, b, c) = 1 with gcd(a, b) > 1, gcd(b, c) > 1, and gcd(a, c) > 1 (e.g. a = 2*3, b = 2*5, c = 3*5). Even so, it does not look too hard to show that all "sufficiently large" d will be representable, and to find decent bounds.

IIRC there is actually a good algorithm known for making the determination, but I'm too lazy to look it up
:-D

[MARTHA]

Yes Sir, for any d>"Frobenius number", equation is solvable with positive integers..The Frobenius-type lower bound is also possible to be calculated..

In fact if we keep changing the value of z, the equation is as easy as with two variables, but then it is too slow just to determine..

a trick could be to check whether the positive integer solution exists for:
ax+by=d
ax+cz=d
OR
by+cz=d.. if any of the solution exist, ax+by+cz=d is also solvable with positive integers.

Originally Posted by Dr Sardonicus

IIRC there is actually a good algorithm known for making the determination, but I'm too lazy to look it up
:-D

[CRGreathouse]

There's an algorithm in GAP, due to Delgado & Sánchez:
Manuel Delgado and Pedro A. García Sánchez, numericalsgps, a GAP package for numerical semigroups, ACM Communications in Computer Algebra, 50 (2016) 12-24. doi:10.1145/2930964.2930966

gap> LoadPackage("NumericalSgps");
----------------------------------------------------------------
Loading  NumericalSgps 0.980
For help, type: ?NumericalSgps:
----------------------------------------------------------------
true
gap> s := NumericalSemigroup("generators",101,103,107);
<Numerical semigroup with 3 generators>
gap> 1000 in s;
false
gap> 10000 in s;
true

The latest version is 1.1.10 as can be seen on github.

[MARTHA]

Originally Posted by CRGreathouse

The latest version is 1.1.10 as can be seen on github.

Thanks a lot indeed.. cause going through the internet, it seemed like a NP-hard problem.. before I dig it in GAP, pl confirm whether it works for big numbers as well..2^100 type..

[CRGreathouse]

Originally Posted by MARTHA

before I dig it in GAP, pl confirm whether it works for big numbers as well..2^100 type..

Would you give an example? I'm not sure which numbers become large.

[CRGreathouse]

GAP seems to have no problem constructing and working with

NumericalSemigroup(2^100+1,10^30+1,7^35+1);

but testing membership is limited in some cases to numbers less than 2^28. (I guess if you can abort early enough it can handle larger numbers?)

[MARTHA]

Originally Posted by CRGreathouse

GAP seems to have no problem constructing and working with

NumericalSemigroup(2^100+1,10^30+1,7^35+1);

but testing membership is limited in some cases to numbers less than 2^28. (I guess if you can abort early enough it can handle larger numbers?)

That is good enough.... just wanted it to be feasibly fast....

thanks again sire !!