On Aug 17, 2:44 pm, Baba <raoul...@gmail.com> wrote: > On Aug 16, 6:28 pm, "cbr...@cbrownsystems.com" > > <cbr...@cbrownsystems.com> wrote: > > First, suppose d = gcd(x, y, z); then for some x', y', z' we have that > > x = d*x', y = d*y', z = d*z'; and so for any a, b, c: > > could you explain the notation? > > what is the difference btw x and x' ? > > what is x = d*x', y supposed to say?
x', y', z' are names for three natural numbers; I could have chosen r, s, t. "x=d*x'" above simply notes that since x is divisible by d, it can be written as the product of d and some other natural number, and the same is true for both y and z. therefore sums of multiples of x, y and z are always divisible by d. > > > To go the other way, if d = 1, then there exists integers (not > > neccessarily positive) such that > > > a*x + b*y + c*z = 1 > > what's the link with 6*a+9*b+20*c=n except the similarity? > The link is that it shows that if we have some u, v, and w with 6*u + 9*v + 20*w = n, and we can find some a, b, and c which satisfy 6*a + 9*b + 20*c = 1 then if we let r = u + a, s = v + b, and t = w + c, we get that 6*r + 9*s + 20*t = n+1 although r, s, and t are not neccessarily positive numbers (as they must be to solve your original problem). However, if u, v, and w are sufficiently large compared to a, b, and c, then r, s and t WILL all be positive. But we can only find such an a,b, and c because the gcd of 6, 9, and 20 is equal to 1; that is why you can't solve this problem for nugget pack sizes 6, 12, and 21. Note that if there is one solution (a,b,c) to the gcd equation, there infinitely many tuples (a,b,c) which satisfy the gcd equation, for example: 6*0 + 9*9 + 20*(-4) = 1 6*(-5) + 9*(-1) + 20*2 = 1 6*2 + 9*1 + 20*(-1) = 1 So the proof I gave regarded the /existence/ of a largest unobtainable, not an algorithm for obtaining one. However from the last of those three examples, we can see (details are in my original proof) that the largest unobtainable must be less than 6*0 + 9*0 + 20*(1*5) = 100 so it is potentially helpful for finding an upper bound to the problem. > furthermore i came across this: > > For k = 3, efficient algorithms > have been given by Greenberg and Davison ; if x1 < x2 < x3, these > algorithms run in > time bounded by a polynomial in log x3. Kannan gave a very > complicated algorithm > that runs in polynomial time in log xk if k is fixed, but is wildly > exponential in k. However, > Ram´ırez Alfons´ın proved that the general problem is NP-hard, under > Turing reductions, > by reducing from the integer knapsack problem. So it seems very likely > that there is no > simple formula for computing g(x1, x2, . . . , xk) for arbitrary k. > > source:http://arxiv.org/PS_cache/arxiv/pdf/0708/0708.3224v1.pdf > > i would be interested in the answer to problem 3: explain in English > why the theorem is true > I haven't looked at the link; but to be honest it's unlikely you would understand it if you are having trouble with the much simpler question regarding solutions in the case of 6, 12, and 21. Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list