Re: Re: Re: Re: Re: smallest

*To*: mathgroup at smc.vnet.net*Subject*: [mg86874] Re: [mg86871] Re: [mg86833] Re: [mg86828] Re: [mg86792] Re: [mg86771] smallest*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Tue, 25 Mar 2008 01:13:55 -0500 (EST)*References*: <200803200757.CAA29500@smc.vnet.net> <200803210653.BAA18315@smc.vnet.net> <200803220554.AAA00496@smc.vnet.net> <200803230600.BAA25688@smc.vnet.net> <47E65E16.4010608@wolfram.com> <200803240645.BAA17083@smc.vnet.net>

Somehow I never saw any of this discussion so could not respond earlier. The reason why my procedure using Reduce does not work in this particular case, is that I forgot that Reduce will not list a finite set of solutions when it is larger than a certain bound. So, for example: cond[a_, b_] := Reduce[a < p/q < b && (p - 1)/q < a && p/(q - 1) > b && p >= 1 && q >= 1, {p, q}, Integers] cond[23/26, 29/30] Out[5]= (p == 8 && q == 9) || (p == 9 && q == 10) || (p == 10 && q == 11) || (p == 11 && q == 12) || (p == 12 && q == 13) || (p == 13 && q == 14) || (p == 14 && q == 15) || (p == 15 && q == 16) || (p == 16 && q == 17) (the first element gives the solution), but with a larger number of solutions: cond[113/355, 106/333] Out[6]= Element[p | q, Integers] && ((1 <= p <= 11978 && (333*p)/106 < q < (355*p)/113) || (11979 <= p <= 37630 && (333*p)/106 < q < (1/106)*(333*p + 106)) || (37631 <= p <= 49607 && (1/113)*(355*p - 355) < q < (1/106)*(333*p + 106))) However, the bound can be user controlled, as follows: Developer`SetSystemOptions[ "ReduceOptions" -> ("DiscreteSolutionBound" -> 10^3)] And then: First[cond[113/355, 106/333]] p == 219 && q == 688 Of course I never recommended this method, which is much slower than using Minimize. It can however find complete solutions with situations when the solution is not unique, for example if we tried to minimize the difference of squares between the denominator and the numerator etc. Andrzej Kozlowski On 24 Mar 2008, at 07:45, Carl Woll wrote: > Carl Woll wrote: > >> Artur wrote: >> >>> If we want to find rational fraction f =p/q such that >>> 113/355<f<106/333 and sum p+q is minimal >>> anyone procedure proposed up to now doesn't work >>> good result should be >>> {137563,{p->13215,q->104348}} >>> but isn't >>> >>> >> Your good result isn't so good, consider: >> >> In[36]:= 113/355 < 219/688 < 106/333 >> >> Out[36]= True >> >> One idea (similar to your Recognize approach) is to use Rationalize >> or >> RootApproximant with SetPrecision: >> >> In[71]:= Rationalize[SetPrecision[(106/333 + 113/355)/2, 6], 0] >> >> Out[71]= 219/688 >> >> In[72]:= RootApproximant[SetPrecision[(106/333 + 113/355)/2, 6], 1] >> >> Out[72]= 219/688 >> >> I'm not sure of the correct method to determine the precision to use. >> It could be something like: >> >> Choose largest prec such that: >> >> IntervalMemberQ[Interval[{lo, hi}], SetPrecision[midpoint, prec]] >> >> is still True. >> >> Carl Woll >> Wolfram Research > > I should add that Daniel Lichtblau's minFraction just needs to be > tweaked a bit to find this result: > > minFraction[lo_Rational, hi_Rational] /; 0 < lo < hi := > Minimize[{p + q, {Denominator[lo]*p - Numerator[lo]*q > 0, > Denominator[hi]*p - Numerator[hi]*q < 0, p >= 1, q >= 1}}, {p, q}, > Integers] > > In[81]:= minFraction[113/355, 106/333] > > Out[81]= {907,{p->219,q->688}} > > Carl Woll > Wolfram Research > >> >>> ARTUR >>> >>> Artur pisze: >>> >>> >>>> If value p/q is known >>>> smallest Abs[p]+Abs[q ] should be >>>> << NumberTheory`Recognize` >>>> Recognize[p/q,1,x] >>>> >>>> see also >>>> http://www.research.att.com/~njas/sequences/A138335 >>>> >>>> Best wishes, >>>> Artur >>>> >>>> Curtis Osterhoudt pisze: >>>> >>>> >>>> >>>>> I doubt this is in the spirit of the problem, but if p and q >>>>> (assumed integers) aren't restricted to be _positive_, then taking >>>>> them both to be very large negative numbers would both fit the p/q >>>>> in I requirement, and p+q as "small" as possible. >>>>> C.O. >>>>> >>>>> On Thursday 20 March 2008 01:57:30 masmoudi wrote: >>>>> >>>>> >>>>> >>>>>> hi >>>>>> >>>>>> suppose that we have an interval I belong to [0,1] >>>>>> >>>>>> I want to know how to calculate a fraction p/q >>>>>> belong to I and p+q is the smallest possible >>>>>> >>>>> >>>>> >>>>> >>>> >>>> __________ NOD32 Informacje 2701 (20071204) __________ >>>> >>>> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32 >>>> http://www.nod32.com lub http://www.nod32.pl >>>> >>>> >>>> >>>> >>> >> >> > >

**Follow-Ups**:**Re: smallest fraction***From:*Artur <grafix@csl.pl>

**References**:**smallest fraction***From:*masmoudi <mas_atef@yahoo.fr>

**Re: smallest fraction***From:*Curtis Osterhoudt <cfo@lanl.gov>

**Re: Re: smallest fraction***From:*Artur <grafix@csl.pl>

**Re: Re: Re: smallest fraction***From:*Artur <grafix@csl.pl>

**Re: Re: Re: Re: smallest***From:*Carl Woll <carlw@wolfram.com>