Re: FindInstance over Integers

*To*: mathgroup at smc.vnet.net*Subject*: [mg101210] Re: FindInstance over Integers*From*: Valeri Astanoff <astanoff at gmail.com>*Date*: Fri, 26 Jun 2009 06:55:13 -0400 (EDT)*References*: <h1qd0b$830$1@smc.vnet.net> <h1vm8t$agd$1@smc.vnet.net>

On 25 juin, 13:15, Valeri Astanoff <astan... at gmail.com> wrote: > 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- Masquer le texte des messages pr=E9c=E9dents - > > - Afficher le texte des messages pr=E9c=E9dents - I omitted to replace {x,y} by 'vars' but I need some help because there is still something wrong with "vars" : "local scope conflict". What should I modify ?...