There is an especially useful function for this kind of task: FrobeniusSolve[{a, b, c}, d]
for finding the list of all solutions to the equation a x + b y + c z == d
, where a
,b
,c
are given positive integers and d
is an integer, while x
,y
,z
are non-negative integers to be found. There are many solutions (884
of them):
FrobeniusSolve[{2, 3, 1}, 100] // Short
{{0, 0, 100}, {0, 1, 97}, {0, 2, 94}, {0, 3, 91}, <<876>>, {48, 0, 4},
{48, 1, 1}, {49, 0, 2}, {50, 0, 0}}
Note that I used Short
which omitted 876
solutions.
If you need only positive solutions you can use e.g. DeleteCases
to get lists free of 0
:
DeleteCases[ FrobeniusSolve[{2, 3, 1}, 100], {___, 0, ___}] // Length
784
Edit
FrobeniusSolve
is not a superfluous function since it is much more efficient than an adequate use of Solve
. Consider e.g. the analogous equation 2 x + 3 y + z == 1000
. We compare the timings of solving the same equation:
Solve[{2*x + 3*y + z == 1000, x >= 0, y >= 0, z >= 0}, {x, y, z}, Integers] //
Length // AbsoluteTiming
FrobeniusSolve[ {2, 3, 1}, 1000] // Length // AbsoluteTiming
{76.9510000, 83834}
{0.1900000, 83834}
This huge efficiency difference doesn't really change if we are to find positive solutions:
Solve[{2*x + 3*y + z == 1000, x > 0, y > 0, z > 0}, {x, y, z}, Integers] //
Length // AbsoluteTiming
DeleteCases[ FrobeniusSolve[{2, 3, 1}, 1000], {___, 0, ___}] // Length // AbsoluteTiming
{77.9720000, 82834}
{0.2420000, 82834}
Moreover, the lists of solutions have the same orderings; e.g.:
DeleteCases[ FrobeniusSolve[{2, 3, 1}, 200], {___, 0, ___}] ===
Solve[{2*x + 3*y + z == 200, x > 0, y > 0, z > 0}, {x, y, z}, Integers][[All, All, 2]]
True
Length[]
on the result ? $\endgroup$ – b.gates.you.know.what Sep 13 '12 at 8:24