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