mersenneforum.org Fastest way to check whether ax+by+cz=d has positive integer solutions
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-17, 02:31 #1 MARTHA   Jan 2018 43 Posts Fastest way to check whether ax+by+cz=d has positive integer solutions 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?
2019-02-17, 18:22   #2
Dr Sardonicus

Feb 2017
Nowhere

2×11×263 Posts

Quote:
 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

2019-02-17, 21:42   #3
MARTHA

Jan 2018

1010112 Posts

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.

Quote:
 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

 2019-02-18, 13:37 #4 CRGreathouse     Aug 2006 597910 Posts 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 Code: gap> LoadPackage("NumericalSgps"); ---------------------------------------------------------------- Loading NumericalSgps 0.980 For help, type: ?NumericalSgps: ---------------------------------------------------------------- true gap> s := NumericalSemigroup("generators",101,103,107); gap> 1000 in s; false gap> 10000 in s; true The latest version is 1.1.10 as can be seen on github.
2019-02-18, 14:25   #5
MARTHA

Jan 2018

43 Posts

Quote:
 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..

2019-02-18, 14:31   #6
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 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.

Last fiddled with by CRGreathouse on 2019-02-18 at 14:32

 2019-02-18, 14:38 #7 CRGreathouse     Aug 2006 3·1,993 Posts GAP seems to have no problem constructing and working with Code: 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?)
2019-02-18, 14:52   #8
MARTHA

Jan 2018

43 Posts

Quote:
 Originally Posted by CRGreathouse GAP seems to have no problem constructing and working with Code: 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 !!

 Similar Threads Thread Thread Starter Forum Replies Last Post Madpoo Data 12 2016-06-29 19:00 ixfd64 Data 3 2016-03-14 22:11 sixblueboxes PrimeNet 90 2014-07-24 05:51 Andi47 GMP-ECM 7 2007-10-21 20:38 Pi Rho Lounge 4 2003-04-23 14:11

All times are UTC. The time now is 07:35.

Thu May 26 07:35:04 UTC 2022 up 42 days, 5:36, 0 users, load averages: 1.37, 1.34, 1.33