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

MathGroup Archive 2008

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

Search the Archive

Re: Re: smallest fraction


On 21 Mar 2008, at 07:55, danl at wolfram.com 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
>
> One method is to use Minimize over integers, setting up appropriate
> bounding constraints.
>
> 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]
>
> For example, we'll work with the interval from 2/7 to 4/9 inclusive.
>
> In[11]:= minFraction[2/7, 4/9]
> Out[11]= {4, {p -> 1, q -> 3}}
>
> If you want to enforce that the interval be strictly inside (0,1)  
> you can
> have constraint q>=2. More generally you might try to strengthen
> constraints based on the input, should speed become an issue.
>
> Daniel Lichtblau
> Wolfram Research
>
>
>


There is a small mathematical point involved here, that I thought it  
might be interesting to make explicit. Maximize looks for an returns  
only one maximum. For example:

Minimize[{-x^2, -1 <= x <= 1}, {x}]
{-1, {x -> -1}}


returns only the maximum at -1 and not the one at 1. So naturally,  
there arises the question: is the solution of this problem provided by  
minFraction always unique?
The answer is yes, and the proof is trivial but cute, so I would like  
first to give it.

Suppose the solution is not unique for some 0<=lo<hi<=1. Let a/b and c/ 
d be two distinct solutions. In other words, {a,b} and {c,d} are two  
pairs of relatively prime non-negative integers with a+b==c+d and 0<a/ 
b < c/d<=1.
That implies  that a<=c and b>=d (and we can't have two equalities).  
Now consider the fraction a/d. This is larger than a/b and smaller  
than c/d. Moreover, a+d is smaller than c+d. (As a concrete examaple,  
tak 1/9 and 3/7, both having the sum 10. Then 1/9<1/7<3/7 and 1/7 has  
sum 8). Thus we would have another fraction between our two fractions  
with a smaller sum of numerator and denominator (this is still the  
case if a cancellation occurs). Hence the minimum is unique so we can  
be confident that Minimize finds the unique answer.

If it were not the case, one could still solve the problem using reduce.
Consdier the function

f[a_, b_] /;
   0 < a < b := {p,
    q} /. {ToRules[
     Reduce[
      a <= p/q <= b && (p - 1)/q < a && p/(q - 1) > b && p >= 1 && q  
 >= 1, {p,
       q}, Integers]]}

Then

  f[1/9, 3/7]
{{1, 3}}

  minFraction[1/9, 3/7]
{4, {p -> 1, q -> 3}}

In general f will return a finite list of pairs, the first of which  
has the smallest sum (hence is the solution of the problem):

f[7/8, 17/18]
{{7, 8}, {8, 9}, {9, 10}, {10, 11}, {11, 12}, {12, 13}, {13, 14}, {14,
   15}, {18, 20}, {19, 21}, {20, 22}, {21, 23}}

while

  minFraction[7/8, 17/18]
{15, {p -> 7, q -> 8}}

minFraction is, as expected, considerably faster.

Andrzej Kozlowski





  • Prev by Date: Re: Poisson equation with boundary conditions on rectangle
  • Next by Date: Re: Mixing immediate assignment and delayed assignment
  • Previous by thread: Re: smallest fraction
  • Next by thread: Re: smallest fraction