# Optimization of the denominator in a rational number under constraints

A problem in the 2005 Indian National Math Olympiad states:

Let $$a,b \in \mathbb{N}$$ such that:

$$\frac{43}{197} < \frac{a}{b} < \frac{17}{77} .$$

Find $${\rm min}(b)$$.

(Incidentally, the answer is $$b=32$$ with $$a=7$$.)

There is an algorithm for finding the solution in which we invert all ratios (which of course reverses $$<\ \to\ >$$), then subtract off integers from all terms (thereby preserving the inequalities). If the flanking rationals have different integral parts, then choose the unknown middle fraction to be the upper integer (thereby preserving the inequalities but minimizing the size of the numerator). If instead the flanking numbers have the same integer parts, invert the ratios and iterating this procedure.

Frankly, this method is very obscure, complicated, and of narrow applicability.

I'm wondering if there is a more direct method exploiting Mathematica's symbol manipulation functionality, including functions such as Rationalize, Minimize, and so on. I'm very much not interested in some exhaustive search of positive integers for numerators and denominators, as that truly doesn't exploit abstract symbol manipulation.

As for instance the naive and dull and computationally costly approach here:

thelist = Flatten[Table[a/b, {a, 1, 40}, {b, 1, 40}]];
Select[thelist, 43/197 < # < 17/77 &]


(* 7/32 *)

(Or said another way, one could perform such a search in Python or other language without using true symbol manipulation.)

Unfortunately, all of my attempts, which exploit Rationalize, Maximize, and logical tests as variations on:

Minimize[{a, 43/197 < a/b < 17/77}, {a, b} \[Element] Integers]


all fail.

I could find no similar problems on this site.

Suggestions?

GOT IT!!!

z = N[Mean[{43/197, 17/77}]];

Rationalize[z, (17/77 - 43/197)/2]


(* 7/32 *)

Let $$z$$ be the mean of the two limits. Then use Rationalize WITH A TOLERANCE that is half the range between the limits. This finds any number in the full range that has the smallest denominator.... just as needed.

Bingo!

• Your approach using Rationalize is essentially using Mathematica as a black box to solve the problem. That is, you don't know what it is doing inside the black box. It could be doing "some exhaustive search of positive integers" inside. Commented Aug 25, 2021 at 18:41
• The whole point is that we need NOT know what Mathematica is doing inside some black box. Yes... we're using it as a black box, and that is great! That is the whole point of automation. Regardless, it is almost certainly not doing some exhaustive search of positive integers. A simple test of timing for illustrative cases proves that (e.g., Rationalize[6.25] versus Rationalize[6.25000000001], where the latter is faster.). see: ted.com/talks/… Commented Aug 25, 2021 at 19:04
• I like the Rationalize method. This also works: In[307]:= Minimize[{b, 197*a > 43*b, 77*a < 17*b, a > 0, b > 0}, {a, b}, Integers] Out[307]= {32, {a -> 7, b -> 32}} Commented Aug 27, 2021 at 14:00
• Yep... closely equivalent. Thanks. Commented Aug 27, 2021 at 16:23

cd = CylindricalDecomposition[a > 0 && 43/197 < a/b < 17/77, {a, b}]

Minimize[{b, cd}, {a, b}, Integers]

(*   {32, {a -> 7, b -> 32}}   *)


Or for negatives

cd = CylindricalDecomposition[a < 0 && 43/197 < a/b < 17/77, {a, b}]

Maximize[{b, cd}, {a, b}, Integers]

(*   {-32, {a -> -7, b -> -32}}   *)

• I certainly had never heard of this function, and am still trying to understand it. But thanks very much! ($+1$) Commented Aug 25, 2021 at 14:52
• red = Reduce[a > 0 && 43/197 < a/b < 17/77, {a, b}] does the same in this case. Commented Aug 25, 2021 at 15:44
• Again, very helpful. I still don't fully understand why either of your two solutions work (while my first did not), but I'll read and think about it. Commented Aug 25, 2021 at 15:54
• Minimize/Maximize often have problems with denominators. In other cases it helps to apply //Together or for equations (lhs-rhs//Together//Numerator)==0 Commented Aug 25, 2021 at 16:01
• I didn't know that problem concerning denominators. I'll keep in mind Together[] in the future... and I've used in in other contexts. (I'm impressed you knew about CylindricalDecomposition... quite an esoteric function!) Commented Aug 25, 2021 at 16:04