6
$\begingroup$

Let $m,k,p$ be fixed positive integers. I want to create a table of k-tuples $(x_1,x_2,\ldots,x_k)$ comprised of solutions in positive integers to the equation below:

$$x_1+x_2+\cdots+x_k=m\quad\text{where }1\leq{}x_1,x_2,\ldots,x_k\leq{}p$$

For example, if I set $m=16,k=3$, and $p=6$. How can I make mathematica generate the set (table) of integer triples $(x_1,x_2,x_3)$ such that $$x_1+x_2+x_3=16$$ where $1\leq{}x_1,x_2,x_3\leq{}6$.

Also, how would I seperately generate a table of positive integral triples $(x_1,x_2,x_3)$ for which $$x_1+x_2+x_3\geq{}16 \quad \text{and } 1\leq{}x_1,x_2,x_3\leq{}6.$$

$\endgroup$
5
$\begingroup$

Try to read Documentation on functions Solve and Reduce and tutorial Solving Equations. Look through this forum, I bet this is a duplicate question. There is also a guide: Diophantine Equations.

{x1, x2, x3} /. 
 Solve[x1 + x2 + x3 == 16 && 1 <= x1 <= 6 && 1 <= x2 <= 6 && 
   1 <= x3 <= 6, {x1, x2, x3}, Integers]

{{4, 6, 6}, {5, 5, 6}, {5, 6, 5}, {6, 4, 6}, {6, 5, 5}, {6, 6, 4}}

or alternatively

Reduce[x1 + x2 + x3 == 16 && 1 <= x1 <= 6 && 1 <= x2 <= 6 && 
  1 <= x3 <= 6, {x1, x2, x3}, Integers]

(x1 == 4 && x2 == 6 && x3 == 6) || (x1 == 5 && x2 == 5 && x3 == 6) || (x1 == 5 && x2 == 6 && x3 == 5) || (x1 == 6 && x2 == 4 && x3 == 6) || (x1 == 6 && x2 == 5 && x3 == 5) || (x1 == 6 && x2 == 6 && x3 == 4)

Your 2nd question would be

{x1, x2, x3} /. 
 Solve[x1 + x2 + x3 >= 16 && 1 <= x1 <= 6 && 1 <= x2 <= 6 && 
   1 <= x3 <= 6, {x1, x2, x3}, Integers]

{{4, 6, 6}, {5, 5, 6}, {5, 6, 5}, {5, 6, 6}, {6, 4, 6}, {6, 5, 5}, {6, 5, 6}, {6, 6, 4}, {6, 6, 5}, {6, 6, 6}}

$\endgroup$
  • $\begingroup$ Thanks for the code and references. $\endgroup$ – Black Milk Mar 31 '13 at 5:34
  • $\begingroup$ I don't know why but when I try to upvote your answer it gives me a -1 instead. $\endgroup$ – Black Milk Mar 31 '13 at 6:07
  • $\begingroup$ @EdwinMontufar Strange... you just have to click "upper" arrow for up-vote. Not sure if you experiencing a bug or clicking on a wrong thing. I hope I won't go negative 25K suddenly ;) $\endgroup$ – Vitaliy Kaurov Mar 31 '13 at 6:14
  • $\begingroup$ I'm definitely clicking that upper arrow =) $\endgroup$ – Black Milk Mar 31 '13 at 6:23
  • $\begingroup$ @EdwinMontufar you got it now, a +1 from you, thanks. I think that -1 is from someone else. $\endgroup$ – Vitaliy Kaurov Mar 31 '13 at 6:28
6
$\begingroup$

It seems to me that for your first stated problem there is a much better method than Solve or Reduce:

{m, k, p} = {16, 3, 6};
IntegerPartitions[m, {k}, Range@p]
{{6, 6, 4}, {6, 5, 5}}

If you want all permutations just use Permutations:

Join @@ Permutations /@ %
{{6, 6, 4}, {6, 4, 6}, {4, 6, 6}, {6, 5, 5}, {5, 6, 5}, {5, 5, 6}}

For your second stated problem I believe this will be more efficient than Solve or Reduce:

Join @@ Table[IntegerPartitions[x, {k}, Range@p], {x, m, k*p}]
{{6, 6, 4}, {6, 5, 5}, {6, 6, 5}, {6, 6, 6}}
$\endgroup$
1
$\begingroup$

Just for completeness, don't forget about one of @Artes' favourite functions: FrobeniusSolve. The Pick statements select solutions with positive integers less than or equal to p.

kTuples[m_Integer, k_Integer, p_Integer] :=
   Block[{s = FrobeniusSolve[ConstantArray[1, k], m]},
         s = Pick[s, UnitStep[Apply[Sequence, Table[p - s[[All, i]], {i, k}]]], 1];
         Pick[s, Map[FreeQ[#, 0] &, s]]
   ]

For your second question generating solutions greater than or equal to m:

kTuples2[min_Integer, k_Integer, p_Integer] :=
   Block[{s},
      Flatten[Table[
         s = FrobeniusSolve[ConstantArray[1, k], m];
         s = Pick[s, UnitStep[Apply[Sequence, Table[p - s[[All, i]], {i, k}]]], 1];
         Pick[s, Map[FreeQ[#, 0] &, s]],
         {m, min, k*p}], 1]
   ]

The method becomes inefficient as m, k, and p increase because valid solutions must be selected from a possibly very large number of solutions returned by FrobeniusSolve.

$\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.