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? > 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? 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 @Giacomo: when you say that i have not read the text of the assignment i tend to disagree. Therefore could you point out what it is i overlooked that should help me prove my assumption for the generalisation? Enjoy the sausages btw :) tnx Baba -- http://mail.python.org/mailman/listinfo/python-list
