Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: smallest fraction

Who know which is minimalize function is used by Mathematica in 
following approximation function by rational fractions:

<< NumberTheory`Recognize`   (*In Mathematica 6 RootApproximant[] 
inspite Recognize[]*)

k = Recognize[N[Pi, 6], 1, x];Solve[k==0,x]

if we have rational fraction p/q (where p,q are both integers)
is minimalize function: p+q, p*q, p^2+q^2 or other ?

ARTUR JASINSKI




Andrzej Kozlowski pisze:
> 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
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>           
>>>       
>>     
>
>
>
> __________ NOD32 Informacje 2701 (20071204) __________
>
> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> http://www.nod32.com lub http://www.nod32.pl 
>
>
>
>
  • Prev by Date: Re: Intersection of 2D Surfaces in 3D
  • Next by Date: Convert Array to Simple List
  • Previous by thread: Re: Re: Re: Re: Re: smallest
  • Next by thread: Re: Re: smallest fraction