4
$\begingroup$

I want to use Mathematica to solve the problem:

Find the maximum $k$ such that $6x+9y+20z=k$ does not have a non-negative solution.

I tried FrobeniusSolve. But what is the elegant way to find the maximum?

I know the theoretical background of this problem, and I know other ways of getting the solution. But I want to see how this can be done elegantly in Mathematica.

Improve this question
$\endgroup$
10
  • $\begingroup$ I'm not sure I understand this. If positive x, y, z are a solution for a given k, then nx, ny and nz are a solution for nk. So it seems to me there is no maximum k. $\endgroup$
    – Sjoerd C. de Vries
    May 28 '13 at 20:35
  • $\begingroup$ @SjoerdC.deVries it is expected that there are infinitely many k that have a solution. In fact the question seem to assume that for some N, all k>N have solutions. We wish to find the smallest such N. That is the same as to say, we wish to find the largest k that does not have a solution. I think. $\endgroup$
    – Jacob Akkerboom
    May 28 '13 at 20:43
  • 2
    $\begingroup$ The short answer to this question is to use FrobeniusNumber[{6, 9, 20}]. $\endgroup$
    – Jacob Akkerboom
    May 28 '13 at 20:53
  • $\begingroup$ mathworld.wolfram.com/CoinProblem.html if you want to implement something yourself. There is a downloadable notebook. $\endgroup$
    – Jacob Akkerboom
    May 28 '13 at 20:56
  • $\begingroup$ @JacobAkkerboom I guess we're reading different things in the question and I'm afraid I don't see any grounds for your interpretation based on the literal text of the question. The question asks for a maximum k and I feel it's pretty clear there can generally not be a maximum k. $\endgroup$
    – Sjoerd C. de Vries
    May 28 '13 at 20:58
4
$\begingroup$

You should use FrobeniusNumber instead of FrobeniusSolve, since it serves this purpose

The Frobenius number of $a_{1}, ... a_{n}$,.is the largest integer b for which the Frobenius equation $a_{1} x_{1}+ ... a_{n} x_{n} = k$ has no non-negative integer solutions. The $a_{i}$ must be positive integers.

FrobeniusNumber[{6, 9, 20}]

43

Nevertheless you can still get the result playing with FrobeniusSolve, there might be many possible ways, let's point out one of them using Cases with an appropriate replacement rule e.g.

Max @ Cases[ Table[{ k, FrobeniusSolve[{6, 9, 20}, k] != {}}, {k, 100}], {a_, False} -> a]

43

In case of not knowing FrobeniusNumber, one can get an idea also with Reduce or Solve although these ways are not recommended for diophantine equations, see e.g. Finding the number of solutions to a diophantine equation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That looks good, I am glad you did it, I will go to sleep :). $\endgroup$
    – Jacob Akkerboom
    May 28 '13 at 22:26
  • $\begingroup$ I'd use FindInstance in preference to Reduce, for the particular task of deciding existence (of solutions). $\endgroup$
    – Daniel Lichtblau
    May 28 '13 at 22:46
  • $\begingroup$ @Artes Yeah, no surprise the quantifier elimination would need either infinite time or memory, and possibly both. $\endgroup$
    – Daniel Lichtblau
    May 29 '13 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.