Simplest intermediate fraction - example
kfost...@my-deja.com
problem which, is, I hope, illustrative.
Find positive integers m and n, n minimal, so that
19/37 < m/n < 11/20.
One has 11*37 - 19*20 = 407 - 380 = 27 > 1. The "obvious"
intermediate is (19+11)/(37+20) = 30/57 = 10/19. But that's
not the answer.
I sketch 3 simple continued fraction (SCF) computations, and
a Farey series development, all of which do give the correct
answer, 6/11.
I note that in NONE of the SCF computations does the answer
appear as one of the convergents to the SCF being developed.
(1) Develop 11/20 as a SCF: 0/1, 1/1, 1/2, 5/9, 11/20
None of the convergents are within the given interval.
Checking the intermediate convergents between 5/9 and 11/20,
we find that there's only one, namely 6/11, and it's within
the given interval. (However, 6/11 does appear if you use the
"n = n-1 + 1/1" trick on the last partial quotient, 2.)
(2) Develop 19/37 as a SCF: 0/1, 1/1, 1/2, 19/37
Again none of the convergents are within the given interval.
Checking the intermediate convergents between 1/2 and 19/37,
the fifth one, 6/11, is within the given interval.
(3) Develop (1/2)(19/37 + 11/20) = 787/1480 as a SCF
0/1, 1/1, 1/2, 8/15, ...
The convergent 8/15 is within the given interval. Checking the
intermediate convergents between 1/2 and 8/15 again turns up 6/11
on the fifth try.
(4) Develop the Farey series of order 37 starting with 19/37
until you reach 11/20. (The work of coming up with 18/35 is the
same as developing 19/37 as a SCF. Once it is in hand, producing
the succeeding terms is done using a standard recursion. This
seems to be less work than developing the whole Farey series of
order 37, which has 432 terms!)
19/37, 18/35, 17/33, 16/31, 15/29, 14/27, 13/25, 12/23, 11/21,
10/19, 19/36, 9/17, 17/32, 8/15, 15/28, 7/13, 20/37, 13/24,
19/35, 6/11, 17/31, 11/20
The answer, 6/11, is third from the last term.
----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email ab...@newsone.net
Gerry Myerson
wrote:
> Here's an example of a "simplest intermediate fraction"
> problem which, is, I hope, illustrative.
> Find positive integers m and n, n minimal, so that
>
> 19/37 < m/n < 11/20.
Someone else* suggested expanding both endpoints as continued frax
and noting where the partial quotients first differ.
The partial quotients are
19/37: 0, 1, 1, 18
11/20: 0, 1, 1, 4, 2
So they 1st differ where 4 isn't 18. So get something in between
by using 0, 1, 1, 5, which is 6/11, as kfoster gets.
*Sorry, didn't save the post, can't remember who it was.
Gerry Myerson (ge...@mpce.mq.edu.au)
Iain Davidson
<kfost...@my-deja.com> wrote in message
news:9aiea6$5jl$1...@news.netmar.com...
> Here's an example of a "simplest intermediate fraction"
> problem which, is, I hope, illustrative.
> Find positive integers m and n, n minimal, so that
>
> 19/37 < m/n < 11/20.
>
> One has 11*37 - 19*20 = 407 - 380 = 27 > 1. The "obvious"
> intermediate is (19+11)/(37+20) = 30/57 = 10/19. But that's
> not the answer.
However, any fraction between 19/37 and 11/20
can be represented as (19a +11b)/(37a + 20b) a,b >1
As 27 is the greatest common factor of
(19a +11b) and (37a + 20b), the smallest denominator
is obtained by finding the smallest k such that
(37a + 20b) = 27k and dividing by 27.
37*1 + 20*13 = 27x11
(19*1 +11*13)/(37*1 + 20*13) = 162/297 = 6/11
If you consider the two lines with slopes of 19/37 and 11/20 that
pass through the origin with integer points A(19,37) and
B(11,20) on the lines, the minimum fraction question is
equivalent to finding the integer point with the min y coordinate
inside the parallelogram O,A, B, A+B.
Say there were three integer points A,B,C with
coordinates A(Ax,Ay,Az), B(Bx,By,Bz), C(Cx,Cy,Cz) on
lines through the origin.
How to find the min. integer point, if any, inside the parallelopiped
O, A,B, C,..,A+B+C ?
Analogously, the necessary condition that there be no
integer points inside the parallelopiped is that the determinant
with the rows (Ax,Ay,Az), (Bx,By,Bz),(Cx,Cy,Cz) be 1.
But is this sufficient ?
ayatollah potassium
> > integers m and n, n minimal, so that 19/37 < m/n < 11/20.
>
> Someone else* suggested expanding both endpoints as continued frax
> and noting where the partial quotients first differ.
That was me. Maybe a better way to say it is: compute as much of
the continued fraction expansion of m/n as is determined by the
CF expansion of the endpoints, then choose the smallest possible
value for the first entry not so determined. This minimizes m and n.
'Expand both endpoints' means applying the same process to
the whole interval at once. If you want 1 < m/n < 2,
although 1 and 2 already disagree at the first position, you transform
them as (1,2) = 1 + (0,1) = 1 + 1/(1,+infinity), producing
m/n = 1 + 1/2 as answer.
> The partial quotients are
>
> 19/37: 0, 1, 1, 18
> 11/20: 0, 1, 1, 4, 2
>
> So they 1st differ where 4 isn't 18. So get something in between
> by using 0, 1, 1, 5, which is 6/11, as kfoster gets.
Right. There is no other choice, because m and n increase as you
step through the possible values from 5 up to 17.
Domingo Gomez Morin
Of course there is a very simple method which properly speaking
has nothing to do with Farey fractions but with Stern-Brocot Tree,
moreover, all this is related to a more general concept called the
"Rational Mean" and the "Rational Process".
Given the fractions: a/b < b/c
Consider the initial values:
0/1, 1/1
Denoting the fraction to the left (the lesser) by "L" and
the fraction to the right (the greater) by "R"
we have:
L=0/1, R=1/1, x=Mediant[L, R]= 1/2
LOOP{
If a/b>=x AND b/c>x then {L=x: x= Mediant[L,R] }
Else
{If a/b<x AND b/c <= x then {R=x: x= Mediant[L,R] }
Else {Print "Output="; x : END LOOP}
}
}
The american philosopher Charles Sanders Peirce also worked with
Stern-Brocot fractions, however it is really surpriseng to realize
that
all of them (including Farey and many others since ancient times)
were not acquainted with the trivial fact that
the Mediant is just a very special case of a more general concept
called the "Rational Mean" (Rational Process)
which is a fundamental principle for generating transcendental
numbers,
the power series expansions, roots solving of algebraic equations of
any degree
and many other math procedures. (Including the well known methods of
Halley, Newton,
Bernoulli, etc. all of them now developed by means of simple
arithmetic, that is,
without the aid of any derivatives nor decimal fractions. From now on,
even our children
at primary school will be able to handle all these new root solving
methods).
All this brand new stuff can be found in the book:
"The Fifth Arithmetical Operation. Number Revolution"
You can find a brief introduction on the subject at the web page:
www.etheron.net/usuarios/dgomez
Regards,
Domingo Gomez Morin
email:
d...@usm.edu.ve
ration...@my-deja.com
Domingo Gomez Morin
Sorry for the typo in my last message.
I said:
given a/b<b/c
instead of:
given a/b<c/d
Anyway, the process is fairly clear.
Bill Dubuque
Simply perform a Farey mediant binary search until you
find the first mediant lying between said fractions:
0/1,1/0 0/1,1/1 1/2,1/1 1/2,2/3
1/2,3/5 1/2,4/7 1/2,5/9 1/2,6/11
Thus 6/11 is the desired fraction.
-Bill Dubuque
Iain Davidson
Bill Dubuque <w...@nestle.ai.mit.edu> wrote in message
news:y8zwv4x...@nestle.ai.mit.edu...
Or apply "Euclid's Algorithm" simultaneously
to 19/37, 11/20
| -1 1| |19 11| = | 18 9|
| 1 0| |37 20| | 19 11|
| -1 1| |18 9| = | 1 2|
| 1 0| |19 11| | 18 9|
| -4 1| | 1 2| = | 14 1|
| 1 0| |18 9| | 1 2|
| 0 1| | 0 1| |0 1| |1| = | 6|
| 1 1| |1 1| |1 4| |1| |11|
[0,1,1,5] is the SCF of 6/11
Herman Rubin
> 0/1,1/0 0/1,1/1 1/2,1/1 1/2,2/3
> 1/2,3/5 1/2,4/7 1/2,5/9 1/2,6/11
This can also be done by finding the standard
continued fraction for each; doing if for both
at once can minimize the amount of work.
For 19/37, the cf is 1/(1+1/(1+1/18)). For
11/20, it is 1/(1+1/(1+1/(4+1/2))). The result,
6/11, has the cf 1/(1+1/(1+1/5)), and 5 is the
smallest integer between 4+1/2 and 18.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
ayatollah potassium
> kfost...@my-deja.com wrote:
> >
> > Find positive integers m and n, n minimal,
> > so that 19/37 < m/n < 11/20. [...]
This was discussed here a few months ago, search
news archives for a detailed discussion (there were
several Subject lines, but you can find them all by
searching for kfoster's articles).
> Simply perform a Farey mediant binary search until you
> find the first mediant lying between said fractions:
That was one approach suggested in the earlier discussion.
It is more efficient to compute a (partial) continued fraction of
the entire open interval between the two values. Eventually
you reach an expression [a1 ; a2; ....ak; (x,y)]
where (x,y) is an open interval containing a least integer N
in its interior. Then [a1 ; a2 ; ... ak ; N] is the simplest fraction.
David T. Ashley
> > so that 19/37 < m/n < 11/20. [...]
Hi Guys,
I'm walking in on this problem "cold", and for some reason my newsgroup
server doesn't have the original message.
But let me take a whack at it:
This problem is, I believe, equivalent to the problem of finding the
rational number with the smallest denominator in an interval. I looked at
this problem a little bit as part of the problem of bounding the error when
one is using the Farey series to approximate in an interval that does not
cross an integer boundary. The maximum error is tied to the fraction with
the smallest denominator.
My solution is available by going to http://ijutools.sourceforge.net, then
file downloads, then just get the book .PDF and look in Chapter 5. It will
be an algorithm near the end, and I believe that I credit Dave Einstein and
Dave Eppstein for it.
You actually don't need to process both of the endpoints. You can make the
following statement (attributable to Dave Einstein):
THE RATIONAL NUMBER WITH THE SMALLEST DENOMINATOR IN AN INTERVAL IS THE BEST
APPROXIMATION OF SOME ORDER TO THE MIDPOINT OF THE INTERVAL.
So, here is the general approach.
a)Compute the midpoint of the interval, ((19/37) + (11/20)) / 2.
b)For each partial quotient of the midpoint, note that the series of
intermediate fractions formable is either an increasing sequence or a
decreasing sequence with respect to the integer parameter "i". There is an
inequality you can solve to figure out what is the smallest-ordered
intermediate fraction that might be in the interval. You only need to check
this one.
c)Keep going until you get one. Because you are checking in order of
increasing denominator, the first one you find will be the one with the
smallest denominator.
d)One can show this algorithm is O(log N), where N is the denominator of the
midpoint, because of the guaranteed minimum exponential increase of CF
convergent denominators, and because there is one step per partial quotient.
I have written software that does this calculation. According to this
software, I've put its answer below. The fraction should be 6/11.
Please give me a good whack if I've made a mistake or a mis-statement.
Dave.
----------------------------------------------------------------------------
--
RAP ($Revision: 21 $ $Date: 11/13/00 3:59a $) execution begins.
----------------------------------------------------------------------------
--
l_h: 19 ( 2 digits)
----------------------------------------------------------------------------
--
l_k: 37 ( 2 digits)
----------------------------------------------------------------------------
--
r_h: 11 ( 2 digits)
----------------------------------------------------------------------------
--
r_k: 20 ( 2 digits)
----------------------------------------------------------------------------
--
midpoint_h: 787 ( 3 digits)
----------------------------------------------------------------------------
--
midpoint_k: 1,480 ( 4 digits)
----------------------------------------------------------------------------
--
***************** CF Representation Of Interval Midpoint
*****************
************************ Inputs To CF Calculation
************************
----------------------------------------------------------------------------
--
h_in: 787 ( 3 digits)
----------------------------------------------------------------------------
--
k_in: 1,480 ( 4 digits)
----------------------------------------------------------------------------
--
************************** CF Partial Quotients
**************************
----------------------------------------------------------------------------
--
a(0): 0 ( 1 digit)
----------------------------------------------------------------------------
--
a(1): 1 ( 1 digit)
----------------------------------------------------------------------------
--
a(2): 1 ( 1 digit)
----------------------------------------------------------------------------
--
a(3): 7 ( 1 digit)
----------------------------------------------------------------------------
--
a(4): 2 ( 1 digit)
----------------------------------------------------------------------------
--
a(5): 1 ( 1 digit)
----------------------------------------------------------------------------
--
a(6): 2 ( 1 digit)
----------------------------------------------------------------------------
--
a(7): 5 ( 1 digit)
----------------------------------------------------------------------------
--
a(8): 2 ( 1 digit)
----------------------------------------------------------------------------
--
***************************** CF Convergents
*****************************
----------------------------------------------------------------------------
--
p(0): 0 ( 1 digit)
q(0): 1 ( 1 digit)
----------------------------------------------------------------------------
--
p(1): 1 ( 1 digit)
q(1): 1 ( 1 digit)
----------------------------------------------------------------------------
--
p(2): 1 ( 1 digit)
q(2): 2 ( 1 digit)
----------------------------------------------------------------------------
--
p(3): 8 ( 1 digit)
q(3): 15 ( 2 digits)
----------------------------------------------------------------------------
--
p(4): 17 ( 2 digits)
q(4): 32 ( 2 digits)
----------------------------------------------------------------------------
--
p(5): 25 ( 2 digits)
q(5): 47 ( 2 digits)
----------------------------------------------------------------------------
--
p(6): 67 ( 2 digits)
q(6): 126 ( 3 digits)
----------------------------------------------------------------------------
--
p(7): 360 ( 3 digits)
q(7): 677 ( 3 digits)
----------------------------------------------------------------------------
--
p(8): 787 ( 3 digits)
q(8): 1,480 ( 4 digits)
----------------------------------------------------------------------------
--
******** A Rational Number With Smallest Denominator In Interval
********
----------------------------------------------------------------------------
--
result_h: 6 ( 1 digit)
----------------------------------------------------------------------------
--
result_k: 11 ( 2 digits)
----------------------------------------------------------------------------
--
RAP execution ends.
----------------------------------------------------------------------------
--
David T. Ashley
> > Find positive integers m and n, n minimal,
> > so that 19/37 < m/n < 11/20. [...]
Hi Guys,