mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-02-17, 02:31   #1
MARTHA
 
Jan 2018

43 Posts
Default 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?
MARTHA is offline   Reply With Quote
Old 2019-02-17, 18:22   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×11×263 Posts
Default

Quote:
Originally Posted by MARTHA View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2019-02-17, 21:42   #3
MARTHA
 
Jan 2018

1010112 Posts
Talking

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 View Post
IIRC there is actually a good algorithm known for making the determination, but I'm too lazy to look it up
:-D
MARTHA is offline   Reply With Quote
Old 2019-02-18, 13:37   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

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);
<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.
CRGreathouse is offline   Reply With Quote
Old 2019-02-18, 14:25   #5
MARTHA
 
Jan 2018

43 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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..
MARTHA is offline   Reply With Quote
Old 2019-02-18, 14:31   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by MARTHA View Post
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
CRGreathouse is offline   Reply With Quote
Old 2019-02-18, 14:38   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

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?)
CRGreathouse is offline   Reply With Quote
Old 2019-02-18, 14:52   #8
MARTHA
 
Jan 2018

43 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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 !!
MARTHA is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fun with a false positive Madpoo Data 12 2016-06-29 19:00
another false positive? ixfd64 Data 3 2016-03-14 22:11
positive LL test? sixblueboxes PrimeNet 90 2014-07-24 05:51
Feature request: integer check on input Andi47 GMP-ECM 7 2007-10-21 20:38
False positive? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔