9
$\begingroup$

I want to count total number of the natural solutions (different from 0) of the equation $2x + 3y + z = 100$, but don't know how. How can I calculate it using Mathematica? I tried:

Solve[{2*x + 3*y + z == 100, x > 0, y > 0, z > 0}, {x, y, z}, Integers]
|improve this question
$\endgroup$
11
$\begingroup$

This should work:

sols = Solve[{2*x + 3*y + z == 100, x > 0, y > 0, z > 0}, 
        {x, y, z}, Integers];
Length@sols
|improve this answer
$\endgroup$
29
$\begingroup$

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
|improve this answer
$\endgroup$
  • 2
    $\begingroup$ +1 for my favorite Frobenius* functions! $\endgroup$ – Silvia Sep 15 '12 at 18:48
  • $\begingroup$ @Silvia Thanks ! Functions like FrobeniusSolve are indeed really useful. I think its documentation might be a bit more comprehensive. $\endgroup$ – Artes Sep 15 '12 at 19:56
7
$\begingroup$

There are also power series methods for counting these.

SeriesCoefficient[
 x^(1 + 2 + 3)/(1 - x^1)*1/(1 - x^2)*1/(1 - x^3), {x, 0, 100}]

(* Out[118]= 784 *)

See also "Supplement to 'Perplexities Related to Fourier's 17 Line Problem'."

|improve this answer
$\endgroup$

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.