Is there a rational number (with denominator not greater than 200) between 15/106 and 16/113?
Is there a rational number (with denominator not greater than 200) between 15/106 and 16/113?
-
5`Select[Flatten[Table[m/n, {n, 2, 200}, {m, 1, n - 1}]], (15/106 < # < 16/113) &]` in *Mathematica* says "no". – 2010-11-24
-
4@J.M. why not answer as an answer? `:)` – 2010-11-24
-
0A general approach to such questions uses continued fractions. See e.g. Knuth's volume.on Semi-numerical Algorithms under best rational approximatiions. – 2010-11-24
6 Answers
The sandwich ${15\over 106}<{p\over q}< {16\over 113}$ implies $15 q<106p$ and $16q>113p$, so necessarily $q>7p$. Write $q=7p+ q_1$ with $q_1>0$. It follows that $15q_1
p$, so necessarily $p= 15 q_1+p_1$ with $0
-
1Note that the optimal choice is 31/219 = (15+16)/(106+113), which is explained by the geometric construction referred to in Bill Dubuque's answer. [Draw the vectors (106,15) and (113,16), and all linear combinations of them with positive integer coefficients, and look at the slopes. The intermediate slope with smallest denominator is given by the linear combination with smallest x-coordinate, which is simply the sum (106+113,15+16) of the two given vectors.] – 2010-11-24
-
0Thanks Hans for the compact and easy-to-follow solution. – 2010-11-25
HINT $\ \ $Google "farey sequence" and "mediant" and / or see my many sci.math posts on these topics, e.g. see this post which explains the lucid lattice geometric viewpoint, and see this post on how to apply this to perform Farey mediant binary searching to find the simplest fraction(s) between two fractions. See also my other posts on these topics, which includes the fascinating connection with Pick's theorem on the area of lattice polygons.
NOTE $\ \ $ If someone here is handy with graphing programs and/or Java you'd be doing a great service if you could draw/animate the mediant lattice construction depicted in ascii art in my first post. Or perhaps someone has done this elsewhere? That yields a "proof without words" that succinctly captures the essence of the matter.
-
0Thank Bill, you are so smart :D – 2010-11-25
A brute-force search in Mathematica, using
Select[Flatten[Table[m/n, {n, 2, 200}, {m, 1, n - 1}]], (15/106 < # < 16/113) &]
indicates that there is no rational number satisfying your requirement.
-
1analytical approach please :D thank you in advance. – 2010-11-24
-
0I don't have any. I'm not an expert in number theory, by any means. – 2010-11-24
-
0It even works in WA: http://www.wolframalpha.com/input/?i=Select[Flatten[Table[m/n,+{n,+2,+200},+{m,+1,+n+-+1}]],+(15/106+%3C+%23+%3C+16/113)+%26] – 2010-11-24
-
0@vonjd: Heh, I was half-expecting Alpha to choke on brute-force stuff like that. Good to know! – 2010-11-24
-
0Thank J.M., your solution is also great. It enriches my knowledge on Mathematica commands. – 2010-11-25
Any rational number between 15/106 and 16/113 is closer to their mean than either of them.
Of course this mean 3391/(2*106*113) has denominator larger than 200. However if we examine the best approximations to this mean by rational numbers of increasing denominators, we will find if there are any before the denominator 200 is reached.
We say a rational number $p/q$ is a best rational approximation to real number $x$ iff no rational number with denominator of smaller absolute value is closer to x. Without loss of generality we restrict discussion to the case p,q,x > 0.
The sequence of such best rational approximations can be derived from the convergents of its continued fraction expansion. The convergents are themselves entries in this sequence, and the only other entries are "interpolants" between the convergents in the following sense.
Suppose $p_1/q_1$ and $p_2/q_2$ are a consecutive pair of convergents to $x$ (in the terminology of continued fractions). The next convergent $p_3/q_3$ will by definition have the form $(p_1 + d*p_2)/(q_1 + d*q_2)$ where $d$ is a positive integer unless already $x$ = $p_2/q_2$. For integers $a = 1,...,d-1$ the "semiconvergents" $(p_1 + a*p_2)/(q_1 + a*q_2)$ are also best rational approximations, and having denominators between $q_2$ and $q_3$, they furnish the entries in the sequence of best rational approximations between $p_2/q_2$ and $p_3/q_3$.
We thus begin by forming the convergents to 3391/(2*106*113) until denominators exceed 200:
0/1
1/7
15/106
31/219
...
Notice that the only semiconvergent between the last two convergents is exactly:
16/113 = (1+15)/(7+106)
This proves there is no rational number between 15/106 and 16/113 with denominator less than the next entry in the sequence 31/219, whose denominator exceeds 200.
-
0Thank hardmath for the solution. It is great also! – 2010-11-25
It happens that $\frac{16}{113} - \frac{15}{106} = \frac{1}{113 \cdot 106}$, which implies that $\frac{16}{113}$ and $\frac{15}{106}$ are Farey neighbors. If $a/b$ and $c/d$ are Farey neighbors, then the “simplest” rational number between them (the one with the smallest denominator) is always $\frac{a+c}{b+d}$, or, in this case, $\frac{31}{219}$.
From the continued-fraction expansions:
$\frac{15}{106} = [0;7,15]$ and $\frac{16}{113} = [0;7,16]$
it is immediate that the simplest fraction between them is
$[0;7,15,2] = \frac{31}{219}$