Re: FindInstance over Integers
- To: mathgroup at smc.vnet.net
- Subject: [mg101164] Re: FindInstance over Integers
- From: Valeri Astanoff <astanoff at gmail.com>
- Date: Thu, 25 Jun 2009 07:16:23 -0400 (EDT)
- References: <h1qd0b$830$1@smc.vnet.net>
On 23 juin, 13:06, "zac.ernst" <zac.er... at gmail.com> wrote:
> Hello --
>
> I'm working on a project which requires the program to determine
> whether a given set of equalities and inequalities is satisfiable over
> the integers. Of course, this problem is not decidable in general.
> But I just need a "good enough" function that will at least report
> that a set of constraints is satisfiable only if it actually is, and
> work across some fairly easy cases. FindInstance is the obvious
> function to use, but it seems to fail for constraints that are very
> easy to satisfy. The simplest example I can come up with is this:
>
> FindInstance[x == 2^y && x > 2, {x, y}, Integers]
>
> Clearly, {x->4, y->2} would satisfy these constraints, but Mathematica
> reports that "the methods available to FindInstance are
> insufficient...".
>
> It may be relevant that if I change "x > 2" to "x > 1", then
> Mathematica has no problem finding a solution.
>
> Are there any workarounds or alternatives to this approach?
>
> Thanks very much,
> -Zac
Good day,
A modest proposal :
In[1]:= myFindInstance[ex_, vars_List, Integers, n_:1, m_:100]:=
Module[{tup = Tuples[Range[-m, m], Length[vars]], fun, sel, res},
fun = Function[vars, {vars, ex}];
sel = Select[fun[#[[1]], #[[2]]]& /@ tup, Last] [[All,1]];
res = Thread[{x,y}->#]& /@ sel;
res[[1 ;; n]]
];
In[2]:= myFindInstance[x == 2^y && x > 2, {x, y}, Integers, 2]
Out[2]= {{x -> 4, y -> 2}, {x -> 8, y -> 3}}
In[3]:= FindInstance[x == 2^y && x > 2, {x, y}, Integers, 2]
FindInstance::nsmet: The methods available to FindInstance
are insufficient to find the requested instances or prove they do not
exist. >>
Out[3]= FindInstance[x == 2^y && x > 2, {x, y}, Integers, 2]
--
V.Astanoff