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 ?...

```

• Prev by Date: Re: Ansatz?
• Next by Date: Re: changing color, size etc on text
• Previous by thread: Re: FindInstance over Integers
• Next by thread: display of graphics primitives