Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: *slowing down* a Mathematica process (Dynamic/Refresh question)
  • Next by Date: Re: Re: Re: Putting an If in my function
  • Previous by thread: Re: FindInstance over Integers
  • Next by thread: Re: FindInstance over Integers