WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: Re: Re: Re: smallest

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
>>>>
>>>>
>>>>
>>>>
>>>
>>
>>
>
>
  • Prev by Date: Re: Rotation of 3D objects
  • Next by Date: Re: Counting nonzeros
  • Previous by thread: Re: Re: Re: Re: smallest
  • Next by thread: Re: smallest fraction