Message Boards Message Boards

0
|
2920 Views
|
3 Replies
|
5 Total Likes
View groups...
Share
Share this post:

How to Generate Random Integers That Fits Into an Equation

Given an equation where a, b, c and d are known,
a*x + b*y + c*z = d
please suggest and algorithm to generate random three integers x, y and z those fit into the given equation.
Brute force (generating random integers until the equation is correct) is not a way.
I don't want to generate doubles, only integers. Hence, generating two of the three and extracting the third one is NOT a solution.
Without constraint solvers, is there a way?

Edit: I need to generate many (x,y,z) triplets. Not only one.
POSTED BY: Onur Cagirici
3 Replies
Just one more thing...
Once we have the solutions, we can of course systematically plot all of them in a given range; here 1<= x,y <=20:
solutions =
  Flatten[Table[{x, y, z} /. Solve[{sols /. {C[1] -> i, C[2] -> j}}, {x, y, z}], {i, 1, 20}, {j, 1, 20}], 2];
Plotting that with the plane given by
5*x + 3*y + 1*z == 6
using
Show[ContourPlot3D[5*x + 3*y + 1*z == 6, {x, 0, 20}, {y, 0, 20}, {z, 0, -150}, Mesh -> None],
ListPointPlot3D[solutions, PlotStyle -> {PointSize[Large]}]]
we get this figure



The integer solutions are marked as dots on the surface which represents the solutions in the reals.

M.
POSTED BY: Marco Thiel
I am not quite sure whether this is at all what you want, but perhaps it is useful. As you are saying that a,b,c,d are known, I actually use specific numbers.
a-> 5, b-> 3, c-> 1, d-> 6
Now I can use Reduce to find general solutions to the Diophantine equation:
sols = Reduce[5*x + 3*y + 1*z == 6, {x, y, z}, Integers]
This gives
(C[1] | C[2]) \[Element] Integers && x == C[1] && y == C[2] &&
z == 6 - 5 C[1] - 3 C[2]
That means that I can choose x and y as I like and then calculate z. Of course, you can now generate as many integer triples as you want:
Table[{sols} /. {C[1] -> RandomInteger[{-100, 100}],
   C[2] -> RandomInteger[{-100, 100}]}, {i, 1, 10}]
This gives ten triples such as
 {{x == -78 && y == -89 && z == 663},
 {x == 5 && y == 74 && z == -241},
 {x == 53 && y == -52 && z == -103},
 {x == -60 && y == 34 && z == 204},
 {x == 70 && y == 44 && z == -476},
 {x == 98 && y == -37 && z == -373},
 {x == -33 && y == 71 && z == -42},
 {x == -37 && y == -5 && z == 206},
 {x == 56 && y == 5 &&z == -289},
{x == 35 && y == 10 && z == -199}}

They are all integers as required.  This does not appear to work if the parameters are not further specified, but rather left as a,b,c,d in the equation.

M.
POSTED BY: Marco Thiel
The problem with these questions is usually what "random" means.  Sometimes people just mean, "give me some integers that satisfy these conditions", and don't think much about a well defined mathematical meaning of "random".  In that case use FindInstance.

A more careful consideration of the problem with consider the specific distribution of (x,y,z), usually a uniform distribution.  Since if your equation has any solutions, it'll have an infinite number of them, you can't have a uniform distribution unless you restrict the allowed range of (x,y,z).  So that's the first thing you need to do: define the domain of (x,y,z).

Next, realize that your equation describes a lattice on a plane.  Once you find the basis vectors of this lattice, it'll be easy to generate random points from it with equal probability. You can use Reduce[] to find the basis vectors.
POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract