Re: Re: smallest fraction
- To: mathgroup at smc.vnet.net
- Subject: [mg86815] Re: [mg86804] Re: [mg86771] smallest fraction
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 22 Mar 2008 00:52:05 -0500 (EST)
- References: <200803200757.CAA29500@smc.vnet.net> <200803210655.BAA18456@smc.vnet.net>
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
- References:
- smallest fraction
- From: masmoudi <mas_atef@yahoo.fr>
- Re: smallest fraction
- From: danl@wolfram.com
- smallest fraction