/[dtapublic]/pubs/books/ucbka/trunk/c_fry0/c_fry0.tex
ViewVC logotype

Diff of /pubs/books/ucbka/trunk/c_fry0/c_fry0.tex

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 4 by dashley, Thu Oct 6 03:15:02 2016 UTC revision 140 by dashley, Mon Jul 3 01:59:16 2017 UTC
# Line 1  Line 1 
1  %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_fry0/c_fry0.tex,v 1.7 2004/03/17 01:37:52 dtashley Exp $  %$Header$
2    
3  \chapter{\cfryzerolongtitle{}}  \chapter{\cfryzerolongtitle{}}
4    
5  \label{cfry0}  \label{cfry0}
6    
7  \beginchapterquote{``\ldots{} Beauty is the first test:  there is no permanent  \beginchapterquote{``\ldots{} Beauty is the first test:  there is no permanent
8                     place in the world for ugly mathematics.''}                     place in the world for ugly mathematics.''}
9                     {G. H. Hardy \cite[p.85]{bibref:b:mathematiciansapology:1940}}                     {G. H. Hardy \cite[p.85]{bibref:b:mathematiciansapology:1940}}
10                                     \index{Hardy, G. H.}                                     \index{Hardy, G. H.}
11    
12  \section{Introduction}  \section{Introduction}
13  %Section Tag: INT  %Section Tag: INT
14  \label{cfry0:sint}  \label{cfry0:sint}
15    
16  The \emph{Farey series  The \emph{Farey series
17  of order $N$},\index{Farey series} denoted $F_{N}$,\index{F@$F_N$}  of order $N$},\index{Farey series} denoted $F_{N}$,\index{F@$F_N$}
18  is the ordered set of all irreducible  is the ordered set of all irreducible
19  rational numbers $h/k$ in the interval  rational numbers $h/k$ in the interval
20  [0,1]  [0,1]
21  with denominator $k\leq N$.  with denominator $k\leq N$.
22  As examples, the Farey series of  As examples, the Farey series of
23  orders 1 through 7, $F_1$ through $F_7$, are shown  orders 1 through 7, $F_1$ through $F_7$, are shown
24  in (\ref{eq:cfry0:sint:eq0001a}) through (\ref{eq:cfry0:sint:eq0001g}).  in (\ref{eq:cfry0:sint:eq0001a}) through (\ref{eq:cfry0:sint:eq0001g}).
25    
26  \begin{equation}  \begin{equation}
27  \label{eq:cfry0:sint:eq0001a}  \label{eq:cfry0:sint:eq0001a}
28  F_1  = \left\{ {\frac{0}{1},\frac{1}{1}} \right\}  F_1  = \left\{ {\frac{0}{1},\frac{1}{1}} \right\}
29  \end{equation}  \end{equation}
30    
31  \begin{equation}  \begin{equation}
32  \label{eq:cfry0:sint:eq0001b}  \label{eq:cfry0:sint:eq0001b}
33  F_2  = \left\{ {\frac{0}{1},\frac{1}{2},\frac{1}{1}} \right\}  F_2  = \left\{ {\frac{0}{1},\frac{1}{2},\frac{1}{1}} \right\}
34  \end{equation}  \end{equation}
35    
36  \begin{equation}  \begin{equation}
37  \label{eq:cfry0:sint:eq0001c}  \label{eq:cfry0:sint:eq0001c}
38  F_3  = \left\{ {\frac{0}{1},\frac{1}{3},\frac{1}{2},  F_3  = \left\{ {\frac{0}{1},\frac{1}{3},\frac{1}{2},
39                  \frac{2}{3},\frac{1}{1}} \right\}                  \frac{2}{3},\frac{1}{1}} \right\}
40  \end{equation}  \end{equation}
41    
42  \begin{equation}  \begin{equation}
43  \label{eq:cfry0:sint:eq0001d}  \label{eq:cfry0:sint:eq0001d}
44  F_4  = \left\{ {\frac{0}{1},\frac{1}{4},  F_4  = \left\{ {\frac{0}{1},\frac{1}{4},
45                  \frac{1}{3},\frac{1}{2},                  \frac{1}{3},\frac{1}{2},
46                  \frac{2}{3},\frac{3}{4},                  \frac{2}{3},\frac{3}{4},
47                  \frac{1}{1}} \right\}                  \frac{1}{1}} \right\}
48  \end{equation}  \end{equation}
49    
50  \begin{equation}  \begin{equation}
51  \label{eq:cfry0:sint:eq0001e}  \label{eq:cfry0:sint:eq0001e}
52  F_5  = \left\{ {\frac{0}{1},\frac{1}{5},\frac{1}{4},  F_5  = \left\{ {\frac{0}{1},\frac{1}{5},\frac{1}{4},
53                  \frac{1}{3},\frac{2}{5},\frac{1}{2},                  \frac{1}{3},\frac{2}{5},\frac{1}{2},
54                  \frac{3}{5},\frac{2}{3},\frac{3}{4},                  \frac{3}{5},\frac{2}{3},\frac{3}{4},
55                  \frac{4}{5},\frac{1}{1}} \right\}                  \frac{4}{5},\frac{1}{1}} \right\}
56  \end{equation}  \end{equation}
57    
58  \begin{equation}  \begin{equation}
59  \label{eq:cfry0:sint:eq0001f}  \label{eq:cfry0:sint:eq0001f}
60  F_6  = \left\{ {\frac{0}{1},\frac{1}{6},\frac{1}{5},  F_6  = \left\{ {\frac{0}{1},\frac{1}{6},\frac{1}{5},
61                  \frac{1}{4},                  \frac{1}{4},
62                  \frac{1}{3},\frac{2}{5},\frac{1}{2},                  \frac{1}{3},\frac{2}{5},\frac{1}{2},
63                  \frac{3}{5},\frac{2}{3},                  \frac{3}{5},\frac{2}{3},
64                  \frac{3}{4},                  \frac{3}{4},
65                  \frac{4}{5},                  \frac{4}{5},
66                  \frac{5}{6},\frac{1}{1}} \right\}                  \frac{5}{6},\frac{1}{1}} \right\}
67  \end{equation}  \end{equation}
68    
69    
70  \begin{equation}  \begin{equation}
71  \label{eq:cfry0:sint:eq0001g}  \label{eq:cfry0:sint:eq0001g}
72  F_7  = \left\{ {\frac{0}{1},\frac{1}{7},\frac{1}{6},\frac{1}{5},  F_7  = \left\{ {\frac{0}{1},\frac{1}{7},\frac{1}{6},\frac{1}{5},
73                  \frac{1}{4},\frac{2}{7},                  \frac{1}{4},\frac{2}{7},
74                  \frac{1}{3},\frac{2}{5},\frac{3}{7},\frac{1}{2},                  \frac{1}{3},\frac{2}{5},\frac{3}{7},\frac{1}{2},
75                  \frac{4}{7},\frac{3}{5},\frac{2}{3},                  \frac{4}{7},\frac{3}{5},\frac{2}{3},
76                  \frac{5}{7},\frac{3}{4},                  \frac{5}{7},\frac{3}{4},
77                  \frac{4}{5},                  \frac{4}{5},
78                  \frac{5}{6},\frac{6}{7},\frac{1}{1} } \right\}                  \frac{5}{6},\frac{6}{7},\frac{1}{1} } \right\}
79  \end{equation}  \end{equation}
80    
81    
82  The distribution of Farey rational numbers in  The distribution of Farey rational numbers in
83  [0,1] is repeated  [0,1] is repeated
84  in any  in any
85  $[i,i+1]$, $i\in \vworkintset$; so that the distribution of  $[i,i+1]$, $i\in \vworkintset$; so that the distribution of
86  Farey rationals in [0,1] supplies complete  Farey rationals in [0,1] supplies complete
87  information about the distribution in  information about the distribution in
88  all of $\vworkrealset$.  We  all of $\vworkrealset$.  We
89  occasionally abuse the proper nomenclature by referring  occasionally abuse the proper nomenclature by referring
90  to sequential rational numbers outside the  to sequential rational numbers outside the
91  interval [0,1] as Farey terms or as part of  interval [0,1] as Farey terms or as part of
92  $F_N$, which, technically, they are not.  $F_N$, which, technically, they are not.
93  All of the results presented in  All of the results presented in
94  this chapter, with the exception of results concerning the number  this chapter, with the exception of results concerning the number
95  of terms, can be shown to apply  of terms, can be shown to apply
96  everywhere in $\vworkrealsetnonneg$, so this abuse  everywhere in $\vworkrealsetnonneg$, so this abuse
97  is not harmful.  is not harmful.
98    
99  The study of the Farey series is a topic from number theory  The study of the Farey series is a topic from number theory
100  (a branch of mathematics).  The Farey series finds application  (a branch of mathematics).  The Farey series finds application
101  in microcontroller work because very often it is economical  in microcontroller work because very often it is economical
102  to linearly scale an integer $x$ using a rational approximation  to linearly scale an integer $x$ using a rational approximation
103  of the form $\lfloor hx/k \rfloor$, $h \in \vworkintsetnonneg$,  of the form $\lfloor hx/k \rfloor$, $h \in \vworkintsetnonneg$,
104  $k \in \vworkintsetpos$ (a single integer multiplication followed by  $k \in \vworkintsetpos$ (a single integer multiplication followed by
105  a single integer division with the remainder discarded).  a single integer division with the remainder discarded).
106  The economy of this type of linear scaling comes about because  The economy of this type of linear scaling comes about because
107  many microcontrollers have integer multiplication and division  many microcontrollers have integer multiplication and division
108  instructions.  However, the technique requires that we be  instructions.  However, the technique requires that we be
109  able to choose $h$ and $k$ so as to place $h/k$ as close  able to choose $h$ and $k$ so as to place $h/k$ as close
110  as possible to the real number $r_I$ that we wish to  as possible to the real number $r_I$ that we wish to
111  approximate; always subject to the constraints  approximate; always subject to the constraints
112  $h \leq{} h_{MAX}$ and $k \leq k_{MAX}$ (since microcontroller  $h \leq{} h_{MAX}$ and $k \leq k_{MAX}$ (since microcontroller
113  multiplication and division instructions are constrained in  multiplication and division instructions are constrained in
114  the size of the operands they can accomodate).  the size of the operands they can accomodate).
115    
116  Without the relevant results from number theory, it is  Without the relevant results from number theory, it is
117  very difficult to find the rational numbers $h/k$:  very difficult to find the rational numbers $h/k$:
118  $h \in \vworkintsetnonneg, \leq{} h_{MAX}$, $k \in \vworkintsetpos, \leq k_{MAX}$  $h \in \vworkintsetnonneg, \leq{} h_{MAX}$, $k \in \vworkintsetpos, \leq k_{MAX}$
119  closest to  closest to
120  an arbitrary $r_I \in \vworkrealsetnonneg$, even for moderate  an arbitrary $r_I \in \vworkrealsetnonneg$, even for moderate
121  choices of $h_{MAX}, k_{MAX}$ (see Example \ref{ex:cfry0:sint:01}).  choices of $h_{MAX}, k_{MAX}$ (see Example \ref{ex:cfry0:sint:01}).
122  A poorly-written brute-force  A poorly-written brute-force
123  algorithm might iterate over all $h$ and all $k$ to find the  algorithm might iterate over all $h$ and all $k$ to find the
124  rational numbers closest to $r_I$; and thus might be  rational numbers closest to $r_I$; and thus might be
125  approximately $O(h_{MAX} k_{MAX})$.  A refined brute-force  approximately $O(h_{MAX} k_{MAX})$.  A refined brute-force
126  algorithm might refine the search and be approximately  algorithm might refine the search and be approximately
127  $O(min(h_{MAX}, k_{MAX}))$.  However, for implementation on powerful  $O(min(h_{MAX}, k_{MAX}))$.  However, for implementation on powerful
128  computers which have machine instructions to multiply and  computers which have machine instructions to multiply and
129  divide large integers, or for extended-precision integer arithmetic, even algorithms  divide large integers, or for extended-precision integer arithmetic, even algorithms
130  which are $O(min(h_{MAX}, k_{MAX}))$ are not  practical.  The best  which are $O(min(h_{MAX}, k_{MAX}))$ are not  practical.  The best
131  algorithm presented in this work (utilizing the  algorithm presented in this work (utilizing the
132  framework of continued fractions), is $O(log \; max(h_{MAX}, k_{MAX}))$,  framework of continued fractions), is $O(log \; max(h_{MAX}, k_{MAX}))$,
133  and so is practical even for very large $h_{MAX}$ and $k_{MAX}$.  and so is practical even for very large $h_{MAX}$ and $k_{MAX}$.
134    
135  \begin{vworkexamplestatement}  \begin{vworkexamplestatement}
136  \label{ex:cfry0:sint:01}  \label{ex:cfry0:sint:01}
137  Find the rational numbers  Find the rational numbers
138  $h/k$ which enclose $1/e \approx 0.3678794412$  $h/k$ which enclose $1/e \approx 0.3678794412$
139  subject to the constraint $k \leq 2^{16} - 1 = 65\vworkthousandsdigsepinmathmode{}535$.%  subject to the constraint $k \leq 2^{16} - 1 = 65\vworkthousandsdigsepinmathmode{}535$.%
140  \footnote{This example is intended to demonstrate the difficulty of  \footnote{This example is intended to demonstrate the difficulty of
141  finding suitable rational numbers near an arbitrary $r_I$ without the  finding suitable rational numbers near an arbitrary $r_I$ without the
142  relevant results from number theory.}  relevant results from number theory.}
143  \end{vworkexamplestatement}  \end{vworkexamplestatement}
144  \begin{vworkexampleparsection}{Solution}  \begin{vworkexampleparsection}{Solution}
145  $1/e$ is irrational, and so has left and right neighbors in  $1/e$ is irrational, and so has left and right neighbors in
146  the Farey series of any order.  Using algorithms that will be presented later in the  the Farey series of any order.  Using algorithms that will be presented later in the
147  work, these two enclosing rational numbers subject to the  work, these two enclosing rational numbers subject to the
148  constraint $k \leq 2^{16}-1$ are  constraint $k \leq 2^{16}-1$ are
149  $18\vworkthousandsdigsepinmathmode{}089/49\vworkthousandsdigsepinmathmode{}171$  $18\vworkthousandsdigsepinmathmode{}089/49\vworkthousandsdigsepinmathmode{}171$
150  and  and
151  $9\vworkthousandsdigsepinmathmode{}545/25\vworkthousandsdigsepinmathmode{}946$.  $9\vworkthousandsdigsepinmathmode{}545/25\vworkthousandsdigsepinmathmode{}946$.
152  \end{vworkexampleparsection}  \end{vworkexampleparsection}
153  \vworkexamplefooter{}  \vworkexamplefooter{}
154    
155  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
156  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
157  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
158  \section{History Of The Farey Series}  \section{History Of The Farey Series}
159  %Section tag:  HFS  %Section tag:  HFS
160    
161  \index{Farey series!history of}  \index{Farey series!history of}
162  The Farey series owes its name to John Farey,  The Farey series owes its name to John Farey,
163  \index{Farey, John} a British geologist who in 1816  \index{Farey, John} a British geologist who in 1816
164  published the statement to the effect that in the Farey series the middle  published the statement to the effect that in the Farey series the middle
165  of any three consecutive terms is the mediant of the other two  of any three consecutive terms is the mediant of the other two
166  \cite{bibref:w:CutTheKnotMainPage}\footnote{\label{fn:cfry0:hfs01}Exact URL:  \cite{bibref:w:CutTheKnotMainPage}\footnote{\label{fn:cfry0:hfs01}Exact URL:
167  \texttt{http://www.cut-the-knot.com/blue/FareyHistory.html}.} (Thm.  \texttt{http://www.cut-the-knot.com/blue/FareyHistory.html}.} (Thm.
168  \ref{thm:cfry0:spfs:03} in this work).  \ref{thm:cfry0:spfs:03} in this work).
169  However, many mathematicians  However, many mathematicians
170  believe that credit for the Farey series is misplaced, and that the  believe that credit for the Farey series is misplaced, and that the
171  series should not have been named after Farey.  In  series should not have been named after Farey.  In
172  \emph{A Mathematician's Apology}  \emph{A Mathematician's Apology}
173  \cite[pp. 81-82]{bibref:b:mathematiciansapology:1940},  \cite[pp. 81-82]{bibref:b:mathematiciansapology:1940},
174  Hardy cites the Farey series as one of the rare examples in scientific  Hardy cites the Farey series as one of the rare examples in scientific
175  history where credit is misplaced:  history where credit is misplaced:
176    
177  \begin{indentedquote}  \begin{indentedquote}
178  ``\ldots{} Farey is immortal because he failed to understand a theorem  ``\ldots{} Farey is immortal because he failed to understand a theorem
179  which Haros had proved perfectly fourteen years  which Haros had proved perfectly fourteen years
180  before \ldots{} but on the whole the history of science is fair, and  before \ldots{} but on the whole the history of science is fair, and
181  this is particularly  this is particularly
182  true in mathematics \ldots{} and the men who are remembered are almost  true in mathematics \ldots{} and the men who are remembered are almost
183  always the men who merit it.''  always the men who merit it.''
184  \end{indentedquote}  \end{indentedquote}
185    
186  Hardy and Wright also provide a footnote about the history  Hardy and Wright also provide a footnote about the history
187  of the Farey series, \cite[pp. 36-37]{bibref:b:HardyAndWrightClassic}:  of the Farey series, \cite[pp. 36-37]{bibref:b:HardyAndWrightClassic}:
188    
189  \begin{indentedquote}  \begin{indentedquote}
190  ``The history of the Farey series is very curious.  ``The history of the Farey series is very curious.
191  Theorems 28 and 29\footnote{Theorems  Theorems 28 and 29\footnote{Theorems
192  \ref{thm:cfry0:spfs:02} and \ref{thm:cfry0:spfs:03},  \ref{thm:cfry0:spfs:02} and \ref{thm:cfry0:spfs:03},
193  respectively, in this chapter.} seem to have been stated and proved first by  respectively, in this chapter.} seem to have been stated and proved first by
194  Haros in 1802; see Dickson, \emph{History}, i. 156.  Haros in 1802; see Dickson, \emph{History}, i. 156.
195  Farey did not publish anything on the subject until  Farey did not publish anything on the subject until
196  1816, when he stated Theorem 29 in a note in the  1816, when he stated Theorem 29 in a note in the
197  \emph{Philosophical Magazine}.  He gave no proof, and it is unlikely that he  \emph{Philosophical Magazine}.  He gave no proof, and it is unlikely that he
198  had found one, since he seems to have been at the best an  had found one, since he seems to have been at the best an
199  indifferent mathematician.  indifferent mathematician.
200    
201  Cauchy, however, saw Farey's statement, and supplied the  Cauchy, however, saw Farey's statement, and supplied the
202  proof (\emph{Exercices de math\'ematiques}, i. 114-116).  Mathematicians  proof (\emph{Exercices de math\'ematiques}, i. 114-116).  Mathematicians
203  generally have followed Cauchy's example in attributing the results to  generally have followed Cauchy's example in attributing the results to
204  Farey, and the results will no doubt continue to bear his name.''  Farey, and the results will no doubt continue to bear his name.''
205  \end{indentedquote}  \end{indentedquote}
206    
207  \cite{bibref:w:CutTheKnotMainPage}$^{\ref{fn:cfry0:hfs01}}$ contains the best  \cite{bibref:w:CutTheKnotMainPage}$^{\ref{fn:cfry0:hfs01}}$ contains the best
208  account of the history of the Farey series on the Web (and contains  account of the history of the Farey series on the Web (and contains
209  information on many other  information on many other
210  interesting topics related to mathematics and number theory, as well).  At this  interesting topics related to mathematics and number theory, as well).  At this
211  site, Dr. Alexander Bogomolny  site, Dr. Alexander Bogomolny
212  \index{Bogomolny, Alexander} has included John Farey's  \index{Bogomolny, Alexander} has included John Farey's
213  original letter to the \emph{Philosophical Magazine}, and much historical  original letter to the \emph{Philosophical Magazine}, and much historical
214  and human perspective.  This site is highly recommended for anyone who has  and human perspective.  This site is highly recommended for anyone who has
215  an interest in mathematics, number theory, and history.  an interest in mathematics, number theory, and history.
216    
217    
218  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
219  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
220  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
221    
222  \section{Properties Of Terms Of The Farey Series}  \section{Properties Of Terms Of The Farey Series}
223  %Section tag:  PFS  %Section tag:  PFS
224    
225  \index{Farey series!properties of}  \index{Farey series!properties of}
226  In Section \ref{cfry0:sint}, we hinted that the properties  In Section \ref{cfry0:sint}, we hinted that the properties
227  of the Farey series (which, technically,  of the Farey series (which, technically,
228  consists of irreducible rational numbers $h/k$  consists of irreducible rational numbers $h/k$
229  only in $[0,1]$) hold in any interval $[n,n+1]$,  only in $[0,1]$) hold in any interval $[n,n+1]$,
230  $n \in \vworkintsetpos$.  We would first like to show  $n \in \vworkintsetpos$.  We would first like to show
231  that if $h/k \in [0,1]$ is irreducible, then  that if $h/k \in [0,1]$ is irreducible, then
232  any of its corresponding rational numbers $(h+ik)/k$ in  any of its corresponding rational numbers $(h+ik)/k$ in
233  $[i,i+1]$, $i \in \vworkintsetpos$ are also irreducible.  $[i,i+1]$, $i \in \vworkintsetpos$ are also irreducible.
234    
235  \begin{vworktheoremstatement}  \begin{vworktheoremstatement}
236  \label{thm:cfry0:spfs:01}  \label{thm:cfry0:spfs:01}
237  Iff $h/k$, $k \in \vworkintsetpos$, $h \in \{0, 1, \ldots{}, k\}$  Iff $h/k$, $k \in \vworkintsetpos$, $h \in \{0, 1, \ldots{}, k\}$
238  is irreducible, then  is irreducible, then
239    
240  \begin{equation}  \begin{equation}
241  \frac{h}{k} + i = \frac{h + ik}{k}  \frac{h}{k} + i = \frac{h + ik}{k}
242  \end{equation}  \end{equation}
243    
244  is also irreducible for $i \in \vworkintsetnonneg$.  is also irreducible for $i \in \vworkintsetnonneg$.
245  \end{vworktheoremstatement}  \end{vworktheoremstatement}
246  \begin{vworktheoremproof}  \begin{vworktheoremproof}
247  Let $\{p_k^{a_k}\} = p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M}$ be the prime  Let $\{p_k^{a_k}\} = p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M}$ be the prime
248  factorization of $h$.  factorization of $h$.
249  Let $\{q_k^{b_k}\} = q_1^{b_1} q_2^{b_2} \ldots{} q_M^{b_M}$ be the prime  Let $\{q_k^{b_k}\} = q_1^{b_1} q_2^{b_2} \ldots{} q_M^{b_M}$ be the prime
250  factorization of $k$.  The coprimality of $h$ and $k$ ensures that  factorization of $k$.  The coprimality of $h$ and $k$ ensures that
251  $\{p_k^{a_k}\} \bigcap \{q_k^{b_k}\} = \oslash$.  We are interested in the  $\{p_k^{a_k}\} \bigcap \{q_k^{b_k}\} = \oslash$.  We are interested in the
252  irreducibility (or lack thereof) of  irreducibility (or lack thereof) of
253    
254  \begin{equation}  \begin{equation}
255  \label{eq:cfry0:spfs:01}  \label{eq:cfry0:spfs:01}
256  \frac{h}{k} + i =  \frac{h}{k} + i =
257  \frac{p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M} +  \frac{p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M} +
258  i(q_1^{b_1} q_2^{b_2} \ldots{} q_N^{b_N})}  i(q_1^{b_1} q_2^{b_2} \ldots{} q_N^{b_N})}
259  {q_1^{b_1}  q_2^{b_2} \ldots{} q_N^{b_N}}  {q_1^{b_1}  q_2^{b_2} \ldots{} q_N^{b_N}}
260  \end{equation}  \end{equation}
261    
262  In order for the expression in (\ref{eq:cfry0:spfs:01}) to be reducible,  In order for the expression in (\ref{eq:cfry0:spfs:01}) to be reducible,
263  it is necessary for at least one $q_k \in \{q_1, q_2, \ldots{}, q_N\}$  it is necessary for at least one $q_k \in \{q_1, q_2, \ldots{}, q_N\}$
264  to divide the numerator, which is possible only if  to divide the numerator, which is possible only if
265  $\{p_k\} \bigcap \{q_k\} \neq \oslash$.  (The degenerate cases  $\{p_k\} \bigcap \{q_k\} \neq \oslash$.  (The degenerate cases
266  of $h=1$ or $k=1$ are left for the reader as  of $h=1$ or $k=1$ are left for the reader as
267  Exercise \ref{exe:cfry0:sexe0:01}.)  Exercise \ref{exe:cfry0:sexe0:01}.)
268  \end{vworktheoremproof}  \end{vworktheoremproof}
269  \begin{vworktheoremparsection}{Remarks}  \begin{vworktheoremparsection}{Remarks}
270  On the other hand, if $h/k$ is reducible, let  On the other hand, if $h/k$ is reducible, let
271  $\{p_k^{a_k}\} = p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M}$  $\{p_k^{a_k}\} = p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M}$
272  be the prime factors of $h$ which do not appear in $k$, let  be the prime factors of $h$ which do not appear in $k$, let
273  $\{q_k^{b_k}\} = q_1^{b_1} q_2^{b_2} \ldots{} q_N^{b_N}$  $\{q_k^{b_k}\} = q_1^{b_1} q_2^{b_2} \ldots{} q_N^{b_N}$
274  be the prime factors of $k$ which do not appear in $h$,  be the prime factors of $k$ which do not appear in $h$,
275  and let  and let
276  $\{s_k^{c_k}\} = s_1^{c_1} s_2^{c_2} \ldots{} s_L^{c_L}$  $\{s_k^{c_k}\} = s_1^{c_1} s_2^{c_2} \ldots{} s_L^{c_L}$
277  be the prime factors which appear in both $h$ and $k$.  be the prime factors which appear in both $h$ and $k$.
278  We are interested in the irreducibility (or lack thereof)  We are interested in the irreducibility (or lack thereof)
279  of  of
280    
281  \begin{equation}  \begin{equation}
282  \label{eq:cfry0:spfs:02}  \label{eq:cfry0:spfs:02}
283  \frac{h}{k} + i =  \frac{h}{k} + i =
284  \frac{ \{ s_k^{c_k} \} \{ p_k^{a_k} \} + i \{ s_k^{c_k} \} \{ q_k^{b_k} \} }  \frac{ \{ s_k^{c_k} \} \{ p_k^{a_k} \} + i \{ s_k^{c_k} \} \{ q_k^{b_k} \} }
285  { \{ s_k^{c_k} \} \{ q_k^{b_k} \} }.  { \{ s_k^{c_k} \} \{ q_k^{b_k} \} }.
286  \end{equation}  \end{equation}
287    
288  It is clear that any choice of  It is clear that any choice of
289  $i \in \vworkintsetnonneg$ will allow $\{s_k^{c_k}\}$  $i \in \vworkintsetnonneg$ will allow $\{s_k^{c_k}\}$
290  to divide both the numerator and the denominator.  to divide both the numerator and the denominator.
291  \end{vworktheoremparsection}  \end{vworktheoremparsection}
292  \vworktheoremfooter{}  \vworktheoremfooter{}
293    
294  \index{rational number!comparison of}  \index{rational number!comparison of}
295  Very frequently, it is necessary to compare rational numbers  Very frequently, it is necessary to compare rational numbers
296  to determine if they are equal; and if not, which is larger.  to determine if they are equal; and if not, which is larger.
297  This need occurs both in symbolic manipulation (derivations and  This need occurs both in symbolic manipulation (derivations and
298  proofs), and in calculations.  We present a property which is  proofs), and in calculations.  We present a property which is
299  useful for comparison of non-negative rational numbers.  useful for comparison of non-negative rational numbers.
300    
301  \begin{vworklemmastatement}  \begin{vworklemmastatement}
302  \label{lem:cfry0:spfs:02b}  \label{lem:cfry0:spfs:02b}
303  For $a,c \geq 0$ and $b,d > 0$,  For $a,c \geq 0$ and $b,d > 0$,
304    
305  \begin{equation}  \begin{equation}
306  \begin{array}{lr}  \begin{array}{lr}
307  \displaystyle{\frac{a}{b} < \frac{c}{d}},      &  iff \;\; ad < bc             \\  \displaystyle{\frac{a}{b} < \frac{c}{d}},      &  iff \;\; ad < bc             \\
308                                                 &                               \\                                                 &                               \\
309  \displaystyle{\frac{a}{b} = \frac{c}{d}},      &  iff \;\; ad = bc             \\  \displaystyle{\frac{a}{b} = \frac{c}{d}},      &  iff \;\; ad = bc             \\
310                                                 &                               \\                                                 &                               \\
311  \displaystyle{\frac{a}{b} > \frac{c}{d}},      &  iff \;\; ad > bc              \displaystyle{\frac{a}{b} > \frac{c}{d}},      &  iff \;\; ad > bc            
312  \end{array}  \end{array}
313  \end{equation}  \end{equation}
314  \end{vworklemmastatement}  \end{vworklemmastatement}
315  \begin{vworklemmaproof}  \begin{vworklemmaproof}
316  Assume $a,c \geq 0$ and $b,d > 0$.  Assume $a,c \geq 0$ and $b,d > 0$.
317  Under these assumptions, $a/b < c/d \vworkequiv a < bc/d \vworkequiv ad < bc$.  Under these assumptions, $a/b < c/d \vworkequiv a < bc/d \vworkequiv ad < bc$.
318  Similarly, under the same assumptions,  Similarly, under the same assumptions,
319  $a/b = c/d \vworkequiv a = bc/d \vworkequiv ad = bc$ and  $a/b = c/d \vworkequiv a = bc/d \vworkequiv ad = bc$ and
320  $a/b > c/d \vworkequiv a > bc/d \vworkequiv ad > bc$.  $a/b > c/d \vworkequiv a > bc/d \vworkequiv ad > bc$.
321  \end{vworklemmaproof}  \end{vworklemmaproof}
322  \begin{vworklemmaparsection}{Remarks}  \begin{vworklemmaparsection}{Remarks}
323  Note it is not required that  Note it is not required that
324  $a, b, c, d \in \vworkintset$, although this is the way in which  $a, b, c, d \in \vworkintset$, although this is the way in which
325  the lemma is used exclusively in this work.  Note also that the lemma does  the lemma is used exclusively in this work.  Note also that the lemma does
326  not cover the case when any of the components $a,b,c,d$ are $<0$.  not cover the case when any of the components $a,b,c,d$ are $<0$.
327  For comparing rational numbers  For comparing rational numbers
328  \index{rational number!comparison of}  \index{rational number!comparison of}
329  with non-negative components, this lemma presents  with non-negative components, this lemma presents
330  the most convenient method.  the most convenient method.
331  \end{vworklemmaparsection}  \end{vworklemmaparsection}
332  \vworklemmafooter{}  \vworklemmafooter{}
333    
334  Some properties and results concerning the Farey series rely  Some properties and results concerning the Farey series rely
335  on the \emph{mediant}\index{mediant}\index{rational number!mediant of}  on the \emph{mediant}\index{mediant}\index{rational number!mediant of}
336  of two rational numbers,  of two rational numbers,
337  which is defined now.  which is defined now.
338    
339  \begin{vworkdefinitionstatementpar}{Mediant}  \begin{vworkdefinitionstatementpar}{Mediant}
340  \label{def:cfry0:spfs:02}  \label{def:cfry0:spfs:02}
341  The \emph{mediant} of two [irreducible] rational numbers  The \emph{mediant} of two [irreducible] rational numbers
342  $h/k$ and $h'/k'$ is the [reduced form of the] fraction  $h/k$ and $h'/k'$ is the [reduced form of the] fraction
343  \begin{equation}  \begin{equation}
344  \frac{h+h'}{k+k'} .  \frac{h+h'}{k+k'} .
345  \end{equation}  \end{equation}
346  \end{vworkdefinitionstatementpar}  \end{vworkdefinitionstatementpar}
347  \begin{vworkdefinitionparsection}{Remarks}  \begin{vworkdefinitionparsection}{Remarks}
348  Note that the mediant of two rational numbers---even  Note that the mediant of two rational numbers---even
349  irreducible rational numbers---is not necessarily irreducible.  irreducible rational numbers---is not necessarily irreducible.
350  For example, the mediant of 1/3 and 2/3 is 3/6, which is  For example, the mediant of 1/3 and 2/3 is 3/6, which is
351  not irreducible.  Note also that the mediant of two rational  not irreducible.  Note also that the mediant of two rational
352  numbers is ambiguously defined if we don't require that the  numbers is ambiguously defined if we don't require that the
353  rational numbers be irreducible.  For example,  rational numbers be irreducible.  For example,
354  the mediant of 1/3 and 2/3 is 3/6 = 1/2, but the  the mediant of 1/3 and 2/3 is 3/6 = 1/2, but the
355  mediant of 2/6 and 2/3 is 4/9 (a different number than  mediant of 2/6 and 2/3 is 4/9 (a different number than
356  1/2).  Normally, in this work, we will calculate the mediant  1/2).  Normally, in this work, we will calculate the mediant
357  only of irreducible rational numbers, and we will define  only of irreducible rational numbers, and we will define
358  the result to be the reduced form of the fraction calculated.  the result to be the reduced form of the fraction calculated.
359  \end{vworkdefinitionparsection}  \end{vworkdefinitionparsection}
360  \vworkdefinitionfooter{}  \vworkdefinitionfooter{}
361    
362  The mediant of two rational numbers always lies between them in value (but  The mediant of two rational numbers always lies between them in value (but
363  is not necessarily the midpoint).  A somewhat stronger  is not necessarily the midpoint).  A somewhat stronger
364  statement about mediants can be made, and is  statement about mediants can be made, and is
365  presented as Lemma \ref{lem:cfry0:spfs:02c}, below.  presented as Lemma \ref{lem:cfry0:spfs:02c}, below.
366    
367  \begin{vworklemmastatement}  \begin{vworklemmastatement}
368  \label{lem:cfry0:spfs:02c}  \label{lem:cfry0:spfs:02c}
369  For  For
370  $a,c \geq 0$,  $a,c \geq 0$,
371  $b,d,i,j > 0$, and  $b,d,i,j > 0$, and
372  $a/b < c/d$,  $a/b < c/d$,
373    
374  \begin{equation}  \begin{equation}
375  \frac{a}{b} < \frac{ia + jc}{ib + jd} < \frac{c}{d} ,  \frac{a}{b} < \frac{ia + jc}{ib + jd} < \frac{c}{d} ,
376  \end{equation}  \end{equation}
377    
378  or, equivalently,  or, equivalently,
379    
380  \begin{equation}  \begin{equation}
381  \frac{ia + jc}{ib + jd} \in \left( { \frac{a}{b} , \frac{c}{d} } \right) .  \frac{ia + jc}{ib + jd} \in \left( { \frac{a}{b} , \frac{c}{d} } \right) .
382  \end{equation}  \end{equation}
383    
384  \end{vworklemmastatement}  \end{vworklemmastatement}
385  \begin{vworklemmaproof}  \begin{vworklemmaproof}
386  Under the restrictions on $a,b,c,d,i$, and $j$;  Under the restrictions on $a,b,c,d,i$, and $j$;
387  $ad < bc \vworkhimp ijad < ijbc \vworkhimp i^2ab+ijad < i^2ab + ijbc$  $ad < bc \vworkhimp ijad < ijbc \vworkhimp i^2ab+ijad < i^2ab + ijbc$
388  $\vworkhimp ia(ib+jd) < ib(ia+jc) \vworkhimp ia/ib < (ia+jc)/(ib+jd)$  $\vworkhimp ia(ib+jd) < ib(ia+jc) \vworkhimp ia/ib < (ia+jc)/(ib+jd)$
389  (employing Lemma \ref{lem:cfry0:spfs:02b}).  A similar implication  (employing Lemma \ref{lem:cfry0:spfs:02b}).  A similar implication
390  can be used to show that $(ia+jc)/(ib+jd) < jc/jd$.  can be used to show that $(ia+jc)/(ib+jd) < jc/jd$.
391  \end{vworklemmaproof}  \end{vworklemmaproof}
392  \begin{vworklemmaparsection}{Remarks}  \begin{vworklemmaparsection}{Remarks}
393  A special case of this lemma is the result that the mediant of two  A special case of this lemma is the result that the mediant of two
394  rational numbers is always between them ($i=j=1$).  This lemma gives  rational numbers is always between them ($i=j=1$).  This lemma gives
395  some insight into the arrangement of  some insight into the arrangement of
396  intermediate fractions\index{intermediate fraction}\index{continued fraction!intermediate fraction}  intermediate fractions\index{intermediate fraction}\index{continued fraction!intermediate fraction}
397  between  between
398  two convergents\index{continued fraction!convergent}  two convergents\index{continued fraction!convergent}
399  (see \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},  (see \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
400  \emph{\ccfrzeroshorttitle{}}).  \emph{\ccfrzeroshorttitle{}}).
401  \end{vworklemmaparsection}  \end{vworklemmaparsection}
402  %\vworklemmafooter{}  %\vworklemmafooter{}
403    
404  \begin{vworktheoremstatement}  \begin{vworktheoremstatement}
405  \label{thm:cfry0:spfs:02ba}  \label{thm:cfry0:spfs:02ba}
406  If $h/k$ and $h'/k'$ are two successive terms  If $h/k$ and $h'/k'$ are two successive terms
407  of $F_N$, then $k + k' > N$.  of $F_N$, then $k + k' > N$.
408  \end{vworktheoremstatement}  \end{vworktheoremstatement}
409  \begin{vworktheoremproof}  \begin{vworktheoremproof}
410  By Lemma \ref{lem:cfry0:spfs:02c},  By Lemma \ref{lem:cfry0:spfs:02c},
411  the mediant of $h/k$ and $h'/k'$ lies between them, i.e.  the mediant of $h/k$ and $h'/k'$ lies between them, i.e.
412    
413  \begin{equation}  \begin{equation}
414  \label{eq:cfry0:spfs:02baa}  \label{eq:cfry0:spfs:02baa}
415  \frac{h + h'}{k + k'} \in \left( { \frac{h}{k}, \frac{h'}{k'}} \right) .  \frac{h + h'}{k + k'} \in \left( { \frac{h}{k}, \frac{h'}{k'}} \right) .
416  \end{equation}  \end{equation}
417    
418  Note that if $k+k' \leq N$, the denominator of the mediant, $k+k'$, is less than  Note that if $k+k' \leq N$, the denominator of the mediant, $k+k'$, is less than
419  $N$, so that either the fraction specified by (\ref{eq:cfry0:spfs:02baa}) or its  $N$, so that either the fraction specified by (\ref{eq:cfry0:spfs:02baa}) or its
420  reduced form is in $F_N$; hence there is another term between $h/k$ and  reduced form is in $F_N$; hence there is another term between $h/k$ and
421  $h'/k'$ in $F_N$.  (See \cite[Thm. 30, p. 23]{bibref:b:HardyAndWrightClassic}.)  $h'/k'$ in $F_N$.  (See \cite[Thm. 30, p. 23]{bibref:b:HardyAndWrightClassic}.)
422  \end{vworktheoremproof}  \end{vworktheoremproof}
423  %\vworktheoremfooter{}  %\vworktheoremfooter{}
424    
425  \begin{vworktheoremstatement}  \begin{vworktheoremstatement}
426  \label{thm:cfry0:spfs:02c}  \label{thm:cfry0:spfs:02c}
427  For $N > 1$, no two consecutive terms of $F_N$ have the  For $N > 1$, no two consecutive terms of $F_N$ have the
428  same denominator.  same denominator.
429  \end{vworktheoremstatement}  \end{vworktheoremstatement}
430  \begin{vworktheoremproof}  \begin{vworktheoremproof}
431  Assume that $h/k$ and $h'/k$ are the two consecutive terms with  Assume that $h/k$ and $h'/k$ are the two consecutive terms with
432  the same denominator.  Note that the only choice of $h'$ which  the same denominator.  Note that the only choice of $h'$ which
433  could be the numerator of a consecutive term is $h'=h+1$; otherwise  could be the numerator of a consecutive term is $h'=h+1$; otherwise
434  we would have $h/k < (h+1)/k < h'/k$, which implies that $h/k$  we would have $h/k < (h+1)/k < h'/k$, which implies that $h/k$
435  and $h'/k'$ are not consecutive, a contradiction.  With  and $h'/k'$ are not consecutive, a contradiction.  With
436  $h'=h+1$ (the only possibility), let's examine the inequality $h/k < h/(k-1) < (h+1)/k$.  $h'=h+1$ (the only possibility), let's examine the inequality $h/k < h/(k-1) < (h+1)/k$.
437  $h/k < h/(k-1)$ is always true for any choice of $k>1$.    $h/k < h/(k-1)$ is always true for any choice of $k>1$.  
438  It can be shown using Lemma \ref{lem:cfry0:spfs:02b}  It can be shown using Lemma \ref{lem:cfry0:spfs:02b}
439  that $h/(k-1) < (h+1)/k$ is true iff $h < k -1$.  So,  that $h/(k-1) < (h+1)/k$ is true iff $h < k -1$.  So,
440  for any $h \in \{2, \ldots{} , k - 2 \}$, we can always use  for any $h \in \{2, \ldots{} , k - 2 \}$, we can always use
441  the fraction $h/(k-1)$ as an intermediate term to show that  the fraction $h/(k-1)$ as an intermediate term to show that
442  $h/k$ and $(h+1)/k$ are not consecutive in $F_N$.  $h/k$ and $(h+1)/k$ are not consecutive in $F_N$.
443  If $h=k-1$, then we are considering the two fractions  If $h=k-1$, then we are considering the two fractions
444  $(k-1)/k$ and $k/k$, and $k/k$ cannot be in lowest  $(k-1)/k$ and $k/k$, and $k/k$ cannot be in lowest
445  terms---after reducing $k/k$ the two fractions  terms---after reducing $k/k$ the two fractions
446  being considered no longer have the  being considered no longer have the
447  same denominator. (See \cite[Thm. 31, p. 24]{bibref:b:HardyAndWrightClassic}.)  same denominator. (See \cite[Thm. 31, p. 24]{bibref:b:HardyAndWrightClassic}.)
448  \end{vworktheoremproof}  \end{vworktheoremproof}
449  %\vworktheoremfooter{}  %\vworktheoremfooter{}
450    
451  \begin{vworktheoremstatement}  \begin{vworktheoremstatement}
452  \label{thm:cfry0:spfs:02}  \label{thm:cfry0:spfs:02}
453  If $h/k$ and $h'/k'$ are two successive terms of $F_N$, then  If $h/k$ and $h'/k'$ are two successive terms of $F_N$, then
454    
455  \begin{equation}  \begin{equation}
456  \label{eq:cfry0:spfs:thm02aa}  \label{eq:cfry0:spfs:thm02aa}
457  h'k - h k' = 1.  h'k - h k' = 1.
458  \end{equation}  \end{equation}
459  \end{vworktheoremstatement}  \end{vworktheoremstatement}
460    
461  \begin{vworktheoremproof}  \begin{vworktheoremproof}
462  For any $h/k$, Lemma \cprizeroxrefhyphen\ref{lem:cpri0:ppn0:00a} guarantees  For any $h/k$, Lemma \cprizeroxrefhyphen\ref{lem:cpri0:ppn0:00a} guarantees
463  that an $h'/k'$ satisfying (\ref{eq:cfry0:spfs:thm02aa}) exists.  that an $h'/k'$ satisfying (\ref{eq:cfry0:spfs:thm02aa}) exists.
464  If $h'=x_0, k'=y_0$ is a solution, then  If $h'=x_0, k'=y_0$ is a solution, then
465  $h'=x_0 + r h, k'=y_0 + r k, r \in \vworkintset$ is also  $h'=x_0 + r h, k'=y_0 + r k, r \in \vworkintset$ is also
466  a solution, and Lemma \cprizeroxrefhyphen\ref{lem:cpri0:ppn0:000p}  a solution, and Lemma \cprizeroxrefhyphen\ref{lem:cpri0:ppn0:000p}
467  guarantees that any $h', k'$ so chosen will be coprime.  guarantees that any $h', k'$ so chosen will be coprime.
468  Note that $r$ can be chosen so that $0 \leq N-k < k' \leq N$, and  Note that $r$ can be chosen so that $0 \leq N-k < k' \leq N$, and
469  that h'/k' will be $\in F_N$.  that h'/k' will be $\in F_N$.
470    
471  However, it still needs to be established that $h'/k'$ is the  However, it still needs to be established that $h'/k'$ is the
472  \emph{next} term in $F_N$ (i.e. that there can be no intervening  \emph{next} term in $F_N$ (i.e. that there can be no intervening
473  terms).  To show this, assume that an intervening term  terms).  To show this, assume that an intervening term
474  $a/b$ exists, so that $h/k < a/b < h'/k'$, with $b \leq N$.  $a/b$ exists, so that $h/k < a/b < h'/k'$, with $b \leq N$.
475  In this case, the distance from $h/k$ to $a/b$ is  In this case, the distance from $h/k$ to $a/b$ is
476    
477  \begin{equation}  \begin{equation}
478  \label{eq:cfry0:spfs:thm02ab}  \label{eq:cfry0:spfs:thm02ab}
479  \frac{a}{b}-\frac{h}{k} = \frac{ak-bh}{bk} \geq \frac{1}{bk} .  \frac{a}{b}-\frac{h}{k} = \frac{ak-bh}{bk} \geq \frac{1}{bk} .
480  \end{equation}  \end{equation}
481    
482  Similarly, the distance from $a/b$ to $h'/k'$ is  Similarly, the distance from $a/b$ to $h'/k'$ is
483    
484  \begin{equation}  \begin{equation}
485  \label{eq:cfry0:spfs:thm02ab2}  \label{eq:cfry0:spfs:thm02ab2}
486  \frac{h'}{k'}-\frac{a}{b} = \frac{h'b-k'a}{k'b} \geq \frac{1}{k'b} .  \frac{h'}{k'}-\frac{a}{b} = \frac{h'b-k'a}{k'b} \geq \frac{1}{k'b} .
487  \end{equation}  \end{equation}
488    
489  (The inequalities in Eqns. \ref{eq:cfry0:spfs:thm02ab}  (The inequalities in Eqns. \ref{eq:cfry0:spfs:thm02ab}
490  and \ref{eq:cfry0:spfs:thm02ab2} come  and \ref{eq:cfry0:spfs:thm02ab2} come
491  about through Lemma \ref{lem:cfry0:spfs:02b}---the numerator  about through Lemma \ref{lem:cfry0:spfs:02b}---the numerator
492  in each case must be at least $1$ if it is assumed  in each case must be at least $1$ if it is assumed
493  $h/k < a/b < h'/k'$.)  $h/k < a/b < h'/k'$.)
494    
495  The distance from $h/k$ to $h'/k'$ is  The distance from $h/k$ to $h'/k'$ is
496    
497  \begin{equation}  \begin{equation}
498  \label{eq:cfry0:spfs:thm02ac}  \label{eq:cfry0:spfs:thm02ac}
499  \frac{h'}{k'}-\frac{h}{k} = \frac{h'k-hk'}{kk'} = \frac{1}{kk'} .  \frac{h'}{k'}-\frac{h}{k} = \frac{h'k-hk'}{kk'} = \frac{1}{kk'} .
500  \end{equation}  \end{equation}
501    
502  The distance from $h/k$ to $h'/k'$ must be the sum of the distances  The distance from $h/k$ to $h'/k'$ must be the sum of the distances
503  from $h/k$ to $a/b$ and from $a/b$ to $h'/k'$:  from $h/k$ to $a/b$ and from $a/b$ to $h'/k'$:
504    
505  \begin{equation}  \begin{equation}
506  \label{eq:cfry0:spfs:thm02ad}  \label{eq:cfry0:spfs:thm02ad}
507  \left( { \frac{h'}{k'} - \frac{h}{k} } \right)  \left( { \frac{h'}{k'} - \frac{h}{k} } \right)
508  =  =
509  \left( { \frac{a}{b} - \frac{h}{k} } \right)  \left( { \frac{a}{b} - \frac{h}{k} } \right)
510  +  +
511  \left( { \frac{h'}{k'} - \frac{a}{b} } \right) .  \left( { \frac{h'}{k'} - \frac{a}{b} } \right) .
512  \end{equation}  \end{equation}
513    
514  Substituting (\ref{eq:cfry0:spfs:thm02ab}),  Substituting (\ref{eq:cfry0:spfs:thm02ab}),
515  (\ref{eq:cfry0:spfs:thm02ab2}),  (\ref{eq:cfry0:spfs:thm02ab2}),
516  and (\ref{eq:cfry0:spfs:thm02ac})  and (\ref{eq:cfry0:spfs:thm02ac})
517  into (\ref{eq:cfry0:spfs:thm02ad}) leads  into (\ref{eq:cfry0:spfs:thm02ad}) leads
518  to  to
519    
520  \begin{equation}  \begin{equation}
521  \label{eq:cfry0:spfs:thm02ae}  \label{eq:cfry0:spfs:thm02ae}
522  \frac{1}{kk'}  \frac{1}{kk'}
523  \geq  \geq
524  \frac{1}{bk}+\frac{1}{k'b}  \frac{1}{bk}+\frac{1}{k'b}
525  =\frac{k'}{bkk'}+\frac{k}{bkk'}  =\frac{k'}{bkk'}+\frac{k}{bkk'}
526  =\frac{k'+k}{bkk'}  =\frac{k'+k}{bkk'}
527  >  >
528  \frac{N}{bkk'}  \frac{N}{bkk'}
529  >  >
530  \frac{1}{kk'} ,  \frac{1}{kk'} ,
531  \end{equation}  \end{equation}
532    
533  a contradiction.  Therefore, $a/b$ must be $h'/k'$ and  a contradiction.  Therefore, $a/b$ must be $h'/k'$ and
534  $h'k-hk'=1$.  (See \cite{bibref:b:HardyAndWrightClassic}, Thm. 28, p. 23,  $h'k-hk'=1$.  (See \cite{bibref:b:HardyAndWrightClassic}, Thm. 28, p. 23,
535  and the second proof on pp. 25-26.)  and the second proof on pp. 25-26.)
536  \end{vworktheoremproof}  \end{vworktheoremproof}
537  %\vworktheoremfooter{}  %\vworktheoremfooter{}
538    
539  \begin{vworklemmastatement}  \begin{vworklemmastatement}
540  \label{lem:cfry0:spfs:03b}  \label{lem:cfry0:spfs:03b}
541  For $h/k$, $h'/k'$ and $h''/k''$; $h, h', h'' \in \vworkintsetnonneg$,  For $h/k$, $h'/k'$ and $h''/k''$; $h, h', h'' \in \vworkintsetnonneg$,
542  $k, k', k'' \in \vworkintsetpos$, with  $k, k', k'' \in \vworkintsetpos$, with
543    
544  \begin{equation}  \begin{equation}
545  h'k-hk' = h''k'-h'k''=1 ,  h'k-hk' = h''k'-h'k''=1 ,
546  \end{equation}  \end{equation}
547    
548  \begin{equation}  \begin{equation}
549  (k'>k'') \vworkhimp  (k'>k'') \vworkhimp
550  \left( {  \left( {
551  \frac{h'}{k'}-\frac{h}{k}<\frac{h''}{k''}-\frac{h}{k}  \frac{h'}{k'}-\frac{h}{k}<\frac{h''}{k''}-\frac{h}{k}
552  } \right) .  } \right) .
553  \end{equation}  \end{equation}
554  \end{vworklemmastatement}  \end{vworklemmastatement}
555  \begin{vworklemmaproof}  \begin{vworklemmaproof}
556  \begin{equation}  \begin{equation}
557  \frac{h'}{k'}-\frac{h}{k} = \frac{1}{kk'}  \frac{h'}{k'}-\frac{h}{k} = \frac{1}{kk'}
558  \end{equation}  \end{equation}
559  \begin{equation}  \begin{equation}
560  \frac{h''}{k''}-\frac{h}{k} = \frac{1}{kk''}  \frac{h''}{k''}-\frac{h}{k} = \frac{1}{kk''}
561  \end{equation}  \end{equation}
562  \begin{equation}  \begin{equation}
563  (k' > k'') \vworkhimp \left( {  (k' > k'') \vworkhimp \left( {
564  \frac{1}{kk'} < \frac{1}{kk''}  \frac{1}{kk'} < \frac{1}{kk''}
565  } \right)  } \right)
566  \end{equation}  \end{equation}
567  \end{vworklemmaproof}  \end{vworklemmaproof}
568  \begin{vworklemmaparsection}{Remarks}  \begin{vworklemmaparsection}{Remarks}
569  This lemma essentially says that if more than one potential successor to  This lemma essentially says that if more than one potential successor to
570  $h/k$ in $F_N$, $h'/k'$ and $h''/k''$, both meet the necessary test  $h/k$ in $F_N$, $h'/k'$ and $h''/k''$, both meet the necessary test
571  provided by Theorem \ref{thm:cfry0:spfs:02}, the potential successor  provided by Theorem \ref{thm:cfry0:spfs:02}, the potential successor
572  with the largest denominator is the successor, because it is closer to  with the largest denominator is the successor, because it is closer to
573  $h/k$.  This lemma is used in proving Theorem \ref{thm:cfry0:sgfs0:01}.  $h/k$.  This lemma is used in proving Theorem \ref{thm:cfry0:sgfs0:01}.
574  \end{vworklemmaparsection}  \end{vworklemmaparsection}
575  %\vworklemmafooter{}  %\vworklemmafooter{}
576    
577  \begin{vworktheoremstatement}  \begin{vworktheoremstatement}
578  \label{thm:cfry0:spfs:03}  \label{thm:cfry0:spfs:03}
579  If $h/k$, $h'/k'$, and $h''/k''$ are three successive terms of $F_N$, then  If $h/k$, $h'/k'$, and $h''/k''$ are three successive terms of $F_N$, then
580    
581  \begin{equation}  \begin{equation}
582  \frac{h'}{k'} = \frac{h+h''}{k+k''}.  \frac{h'}{k'} = \frac{h+h''}{k+k''}.
583  \end{equation}  \end{equation}
584  \end{vworktheoremstatement}  \end{vworktheoremstatement}
585  \begin{vworktheoremproof}  \begin{vworktheoremproof}
586  Starting from Theorem \ref{thm:cfry0:spfs:02}:  Starting from Theorem \ref{thm:cfry0:spfs:02}:
587  \begin{equation}  \begin{equation}
588  h'k-hk' = h''k' - h'k''=1  h'k-hk' = h''k' - h'k''=1
589  \end{equation}  \end{equation}
590  \begin{equation}  \begin{equation}
591  h'(k+k'')=k'(h+h'')  h'(k+k'')=k'(h+h'')
592  \end{equation}  \end{equation}
593  \begin{equation}  \begin{equation}
594  \frac{h'}{k'} = \frac{h+h''}{k+k''}.  \frac{h'}{k'} = \frac{h+h''}{k+k''}.
595  \end{equation}  \end{equation}
596  \end{vworktheoremproof}  \end{vworktheoremproof}
597  \vworktheoremfooter{}  \vworktheoremfooter{}
598    
599    
600  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
601  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
602  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
603  \section{Generation Of Terms Of The Farey Series}  \section{Generation Of Terms Of The Farey Series}
604  \label{cfry0:sgfs0}  \label{cfry0:sgfs0}
605  %Section tag:  GFS0  %Section tag:  GFS0
606    
607    
608  \index{Farey series!generation of terms}  \index{Farey series!generation of terms}
609  Earlier sections of this chapter have enumerated important properties of the  Earlier sections of this chapter have enumerated important properties of the
610  Farey series.  However, these properties are of limited practical value  Farey series.  However, these properties are of limited practical value
611  because they don't help to solve practical problems in microcontroller  because they don't help to solve practical problems in microcontroller
612  work---one would like to be able to generate (in order, of course) all of  work---one would like to be able to generate (in order, of course) all of
613  the terms of a Farey series so that one can choose suitable terms  the terms of a Farey series so that one can choose suitable terms
614  near some $r_I \in \vworkrealsetnonneg$ that one wishes to approximate  near some $r_I \in \vworkrealsetnonneg$ that one wishes to approximate
615  with $r_A = h/k$.  with $r_A = h/k$.
616    
617  Fortunately, the properties presented in earlier sections do allow the  Fortunately, the properties presented in earlier sections do allow the
618  generation of successive Farey terms, as the following theorem shows.  generation of successive Farey terms, as the following theorem shows.
619    
620  \begin{vworktheoremstatement}  \begin{vworktheoremstatement}
621  \label{thm:cfry0:sgfs0:01}  \label{thm:cfry0:sgfs0:01}
622  For a Farey series of order $N$,  For a Farey series of order $N$,
623    
624  \begin{equation}  \begin{equation}
625  F_N = \left\{ {  F_N = \left\{ {
626  \frac{h_0}{k_0},    \frac{h_0}{k_0},  
627  \frac{h_1}{k_1},  \frac{h_1}{k_1},
628  \frac{h_2}{k_2},  \frac{h_2}{k_2},
629  \frac{h_3}{k_3},  \frac{h_3}{k_3},
630  \ldots  \ldots
631  } \right\} ,  } \right\} ,
632  \end{equation}  \end{equation}
633    
634  the recursive relationships in  the recursive relationships in
635  (\ref{eq:cfry0:sgfs0:thm:01:eq01}),  (\ref{eq:cfry0:sgfs0:thm:01:eq01}),
636  (\ref{eq:cfry0:sgfs0:thm:01:eq02}),  (\ref{eq:cfry0:sgfs0:thm:01:eq02}),
637  (\ref{eq:cfry0:sgfs0:thm:01:eq03}), and  (\ref{eq:cfry0:sgfs0:thm:01:eq03}), and
638  (\ref{eq:cfry0:sgfs0:thm:01:eq04}) apply.  (\ref{eq:cfry0:sgfs0:thm:01:eq04}) apply.
639  \index{Farey series!recursive formulas}  \index{Farey series!recursive formulas}
640    
641  \begin{equation}  \begin{equation}
642  \label{eq:cfry0:sgfs0:thm:01:eq01}  \label{eq:cfry0:sgfs0:thm:01:eq01}
643  h_{j}  = \left\lfloor {\frac{{k_{j-2}  h_{j}  = \left\lfloor {\frac{{k_{j-2}
644       + N}}{{k_{j - 1} }}} \right\rfloor h_{j - 1}  - h_{j-2}       + N}}{{k_{j - 1} }}} \right\rfloor h_{j - 1}  - h_{j-2}
645  \end{equation}  \end{equation}
646    
647  \begin{equation}  \begin{equation}
648  \label{eq:cfry0:sgfs0:thm:01:eq02}  \label{eq:cfry0:sgfs0:thm:01:eq02}
649  k_{j}  = \left\lfloor {\frac{{k_{j-2}  + N}}{{k_{j  k_{j}  = \left\lfloor {\frac{{k_{j-2}  + N}}{{k_{j
650       - 1} }}} \right\rfloor k_{j - 1}  - k_{j-2}       - 1} }}} \right\rfloor k_{j - 1}  - k_{j-2}
651  \end{equation}  \end{equation}
652    
653  \begin{equation}  \begin{equation}
654  \label{eq:cfry0:sgfs0:thm:01:eq03}  \label{eq:cfry0:sgfs0:thm:01:eq03}
655  h_j  = \left\lfloor {\frac{{k_{j + 2}  + N}}{{k_{j + 1} }}}  h_j  = \left\lfloor {\frac{{k_{j + 2}  + N}}{{k_{j + 1} }}}
656  \right\rfloor h_{j + 1}  - h_{j + 2}  \right\rfloor h_{j + 1}  - h_{j + 2}
657  \end{equation}  \end{equation}
658    
659  \begin{equation}  \begin{equation}
660  \label{eq:cfry0:sgfs0:thm:01:eq04}  \label{eq:cfry0:sgfs0:thm:01:eq04}
661  k_j  = \left\lfloor {\frac{{k_{j + 2}  + N}}{{k_{j + 1} }}}  k_j  = \left\lfloor {\frac{{k_{j + 2}  + N}}{{k_{j + 1} }}}
662  \right\rfloor k_{j + 1}  - k_{j + 2}  \right\rfloor k_{j + 1}  - k_{j + 2}
663  \end{equation}  \end{equation}
664  \end{vworktheoremstatement}  \end{vworktheoremstatement}
665  \begin{vworktheoremproof}  \begin{vworktheoremproof}
666  Only (\ref{eq:cfry0:sgfs0:thm:01:eq01}) and  Only (\ref{eq:cfry0:sgfs0:thm:01:eq01}) and
667  (\ref{eq:cfry0:sgfs0:thm:01:eq02}) are  (\ref{eq:cfry0:sgfs0:thm:01:eq02}) are
668  proved---(\ref{eq:cfry0:sgfs0:thm:01:eq03}) and  proved---(\ref{eq:cfry0:sgfs0:thm:01:eq03}) and
669  (\ref{eq:cfry0:sgfs0:thm:01:eq04}) come by symmetry.  (\ref{eq:cfry0:sgfs0:thm:01:eq04}) come by symmetry.
670    
671  Assume that $h_{j-2}/k_{j-2}$ and $h_{j-1}/k_{j-1}$ are known and we wish  Assume that $h_{j-2}/k_{j-2}$ and $h_{j-1}/k_{j-1}$ are known and we wish
672  to find $h_{j}/k_{j}$.  to find $h_{j}/k_{j}$.
673    
674  Note that by Theorem \ref{thm:cfry0:spfs:02},  Note that by Theorem \ref{thm:cfry0:spfs:02},
675    
676  \begin{equation}  \begin{equation}
677  \label{eq:cfry0:sgfs0:thm:01:eq05}  \label{eq:cfry0:sgfs0:thm:01:eq05}
678  h_{j-1} k_{j-2} - h_{j-2} k_{j-1} = 1  h_{j-1} k_{j-2} - h_{j-2} k_{j-1} = 1
679  \end{equation}  \end{equation}
680    
681  and  and
682    
683  \begin{equation}  \begin{equation}
684  \label{eq:cfry0:sgfs0:thm:01:eq06}  \label{eq:cfry0:sgfs0:thm:01:eq06}
685  h_{j} k_{j-1} - h_{j-1} k_{j} = 1 .  h_{j} k_{j-1} - h_{j-1} k_{j} = 1 .
686  \end{equation}  \end{equation}
687    
688  We desire to identify the set of rational numbers $\{ h_j / k_j \}$ that satisfy  We desire to identify the set of rational numbers $\{ h_j / k_j \}$ that satisfy
689  (\ref{eq:cfry0:sgfs0:thm:01:eq06}).  If this set is identified, by Lemma  (\ref{eq:cfry0:sgfs0:thm:01:eq06}).  If this set is identified, by Lemma
690  \ref{lem:cfry0:spfs:03b}, we can simply choose the member of the set that has the  \ref{lem:cfry0:spfs:03b}, we can simply choose the member of the set that has the
691  largest denominator.  largest denominator.
692    
693  Choose as trial solutions  Choose as trial solutions
694    
695  \begin{equation}  \begin{equation}
696  \label{eq:cfry0:sgfs0:thm:01:eq07}  \label{eq:cfry0:sgfs0:thm:01:eq07}
697  h_j = i h_{j-1} - h_{j-2}  h_j = i h_{j-1} - h_{j-2}
698  \end{equation}  \end{equation}
699    
700  and  and
701    
702  \begin{equation}  \begin{equation}
703  \label{eq:cfry0:sgfs0:thm:01:eq08}  \label{eq:cfry0:sgfs0:thm:01:eq08}
704  k_j = i k_{j-1} - k_{j-2} ,  k_j = i k_{j-1} - k_{j-2} ,
705  \end{equation}  \end{equation}
706    
707  where $i \in \vworkintset$ is an integer parameter; i.e. define  where $i \in \vworkintset$ is an integer parameter; i.e. define
708  as the trial set of solutions all $h_j /k_j$ that can be formed  as the trial set of solutions all $h_j /k_j$ that can be formed
709  by $i \in \vworkintset$ substituted into  by $i \in \vworkintset$ substituted into
710  (\ref{eq:cfry0:sgfs0:thm:01:eq07}) and  (\ref{eq:cfry0:sgfs0:thm:01:eq07}) and
711  (\ref{eq:cfry0:sgfs0:thm:01:eq08}).  Substitution of this trial  (\ref{eq:cfry0:sgfs0:thm:01:eq08}).  Substitution of this trial
712  solution into (\ref{eq:cfry0:sgfs0:thm:01:eq06}) yields  solution into (\ref{eq:cfry0:sgfs0:thm:01:eq06}) yields
713    
714  \begin{equation}  \begin{equation}
715  \label{eq:cfry0:sgfs0:thm:01:eq09}  \label{eq:cfry0:sgfs0:thm:01:eq09}
716  (i h_{j-1} - h_{j-2}) k_{j-1} - h_{j-1} (i k_{j-1} - k_{j-2} )  (i h_{j-1} - h_{j-2}) k_{j-1} - h_{j-1} (i k_{j-1} - k_{j-2} )
717  = h_{j-1} k_{j-2} - h_{j-2} k_{j-1} = 1.  = h_{j-1} k_{j-2} - h_{j-2} k_{j-1} = 1.
718  \end{equation}  \end{equation}
719    
720  Thus, any solution in the form of  Thus, any solution in the form of
721  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
722  will meet the necessary test posed  will meet the necessary test posed
723  by Theorem \ref{thm:cfry0:spfs:02}.  by Theorem \ref{thm:cfry0:spfs:02}.
724    
725  However, we must also demonstrate that solutions of the form  However, we must also demonstrate that solutions of the form
726  suggested by  suggested by
727  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
728  are the \emph{only} solutions which meet  are the \emph{only} solutions which meet
729  the necessary test posed by Theorem \ref{thm:cfry0:spfs:02}, and  the necessary test posed by Theorem \ref{thm:cfry0:spfs:02}, and
730  also demonstrate how to pick the solution of this form  also demonstrate how to pick the solution of this form
731  with the largest denominator $k_{j} \leq N$.  with the largest denominator $k_{j} \leq N$.
732    
733  To demonstrate that  To demonstrate that
734  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
735  are the only solutions, solve (\ref{eq:cfry0:sgfs0:thm:01:eq06})  are the only solutions, solve (\ref{eq:cfry0:sgfs0:thm:01:eq06})
736  for $h_j$, yielding  for $h_j$, yielding
737    
738  \begin{equation}  \begin{equation}
739  \label{eq:cfry0:sgfs0:thm:01:eq10}  \label{eq:cfry0:sgfs0:thm:01:eq10}
740  h_j = \frac{h_{j-1}}{k_{j-1}} k_j + \frac{1}{k_{j-1}} .  h_j = \frac{h_{j-1}}{k_{j-1}} k_j + \frac{1}{k_{j-1}} .
741  \end{equation}  \end{equation}
742    
743  Since $h_{j-1}$ and $k_{j-1}$ are known, it is clear that  Since $h_{j-1}$ and $k_{j-1}$ are known, it is clear that
744  (\ref{eq:cfry0:sgfs0:thm:01:eq10}) defines a required linear relationship  (\ref{eq:cfry0:sgfs0:thm:01:eq10}) defines a required linear relationship
745  between $h_j$ and $k_j$, and that the only solutions are the values of  between $h_j$ and $k_j$, and that the only solutions are the values of
746  $h_j$ and $k_j$ meeting  $h_j$ and $k_j$ meeting
747  (\ref{eq:cfry0:sgfs0:thm:01:eq10})  (\ref{eq:cfry0:sgfs0:thm:01:eq10})
748  which are integers. Assume that a particular integer  which are integers. Assume that a particular integer
749  solution $\overline{h_j}, \overline{k_j}$ to  solution $\overline{h_j}, \overline{k_j}$ to
750  (\ref{eq:cfry0:sgfs0:thm:01:eq10}) is known  (\ref{eq:cfry0:sgfs0:thm:01:eq10}) is known
751  and that a second integer solution  and that a second integer solution
752  $\widehat{h_j}, \widehat{k_j}$ is sought.  In order for  $\widehat{h_j}, \widehat{k_j}$ is sought.  In order for
753  $\widehat{h_j}$ to be an integer, it must  $\widehat{h_j}$ to be an integer, it must
754  differ from $\overline{h_j}$ by an  differ from $\overline{h_j}$ by an
755  integer, implying  integer, implying
756    
757  \begin{equation}  \begin{equation}
758  \label{eq:cfry0:sgfs0:thm:01:eq11}  \label{eq:cfry0:sgfs0:thm:01:eq11}
759  \frac{h_{j-1}}{k_{j-1}} ( \widehat{k_j} - \overline{k_j} ) \in \vworkintset{} .  \frac{h_{j-1}}{k_{j-1}} ( \widehat{k_j} - \overline{k_j} ) \in \vworkintset{} .
760  \end{equation}  \end{equation}
761    
762  It is easy to see from the form of (\ref{eq:cfry0:sgfs0:thm:01:eq11}) that  It is easy to see from the form of (\ref{eq:cfry0:sgfs0:thm:01:eq11}) that
763  because $h_{j-1}$ and $k_{j-1}$ are coprime, in order for  because $h_{j-1}$ and $k_{j-1}$ are coprime, in order for
764  (\ref{eq:cfry0:sgfs0:thm:01:eq11}) to be met,  (\ref{eq:cfry0:sgfs0:thm:01:eq11}) to be met,
765  $\widehat{k_j} - \overline{k_j}$  $\widehat{k_j} - \overline{k_j}$
766  must contain every prime factor of $k_{j-1}$ in at least  must contain every prime factor of $k_{j-1}$ in at least
767  equal multiplicity, implying  equal multiplicity, implying
768  $| \widehat{k_j} - \overline{k_j} | \geq k_{j-1}$.  It follows  $| \widehat{k_j} - \overline{k_j} | \geq k_{j-1}$.  It follows
769  that  that
770  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})  (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
771  are the only solutions  are the only solutions
772  which meet  which meet
773  the necessary test posed by Theorem \ref{thm:cfry0:spfs:02}.  We only  the necessary test posed by Theorem \ref{thm:cfry0:spfs:02}.  We only
774  need find the solution with the largest denominator.  need find the solution with the largest denominator.
775    
776  Solving $i k_{j-1} - k_{j-2} \leq N$ for the largest integral  Solving $i k_{j-1} - k_{j-2} \leq N$ for the largest integral
777  value of $i$ leads to  value of $i$ leads to
778    
779  \begin{equation}  \begin{equation}
780  \label{eq:cfry0:sgfs0:thm:01:eq12}  \label{eq:cfry0:sgfs0:thm:01:eq12}
781  i = \left\lfloor {  i = \left\lfloor {
782  \frac{k_{j-2} + N}{k_{j-1}}  \frac{k_{j-2} + N}{k_{j-1}}
783  } \right\rfloor  } \right\rfloor
784  \end{equation}  \end{equation}
785    
786  and directly to (\ref{eq:cfry0:sgfs0:thm:01:eq01})  and directly to (\ref{eq:cfry0:sgfs0:thm:01:eq01})
787  and (\ref{eq:cfry0:sgfs0:thm:01:eq02}).  and (\ref{eq:cfry0:sgfs0:thm:01:eq02}).
788  \end{vworktheoremproof}  \end{vworktheoremproof}
789  \vworktheoremfooter{}  \vworktheoremfooter{}
790    
791  Given two consecutive Farey terms, Theorem \ref{thm:cfry0:sgfs0:01} suggests  Given two consecutive Farey terms, Theorem \ref{thm:cfry0:sgfs0:01} suggests
792  a way to generate as many neighboring terms as desired in either the  a way to generate as many neighboring terms as desired in either the
793  descending or ascending direction.  Note that at an integer $i$,  descending or ascending direction.  Note that at an integer $i$,
794  $(iN-1)/N$, $i/1$, and $(iN+1)/N$ are always consecutive terms  $(iN-1)/N$, $i/1$, and $(iN+1)/N$ are always consecutive terms
795  in $F_N$; thus it is typically convenient to build the Farey series  in $F_N$; thus it is typically convenient to build the Farey series
796  starting at an integer.  This method is presented as  starting at an integer.  This method is presented as
797  Algorithm \ref{alg:cfry0:sgfs0:02}.  Algorithm \ref{alg:cfry0:sgfs0:02}.
798    
799  \begin{vworkalgorithmstatementpar}{\mbox{\boldmath $O(N^2)$} Exhaustive  \begin{vworkalgorithmstatementpar}{\mbox{\boldmath $O(N^2)$} Exhaustive
800                                     Construction                                     Construction
801                                     Algorithm For Finding Enclosing                                     Algorithm For Finding Enclosing
802                                     Neighbors To \mbox{\boldmath $r_I$}                                     Neighbors To \mbox{\boldmath $r_I$}
803                                     In \mbox{\boldmath $F_N$}}                                     In \mbox{\boldmath $F_N$}}
804  \label{alg:cfry0:sgfs0:02}  \label{alg:cfry0:sgfs0:02}
805  \begin{itemize}  \begin{itemize}
806  \item Choose $i = \lfloor r_I + 1/2 \rfloor$ as the integer from which  \item Choose $i = \lfloor r_I + 1/2 \rfloor$ as the integer from which
807        to construct consecutive Farey terms (i.e. the nearest integer        to construct consecutive Farey terms (i.e. the nearest integer
808        to $r_I$).        to $r_I$).
809    
810  \item Choose $i/1$ and $(iN+1)/N$ as the two consecutive Farey terms from  \item Choose $i/1$ and $(iN+1)/N$ as the two consecutive Farey terms from
811        which to start construction.        which to start construction.
812    
813  \item Use (\ref{eq:cfry0:sgfs0:thm:01:eq01}) and  \item Use (\ref{eq:cfry0:sgfs0:thm:01:eq01}) and
814        (\ref{eq:cfry0:sgfs0:thm:01:eq02}) or          (\ref{eq:cfry0:sgfs0:thm:01:eq02}) or  
815        (\ref{eq:cfry0:sgfs0:thm:01:eq03}) and        (\ref{eq:cfry0:sgfs0:thm:01:eq03}) and
816        (\ref{eq:cfry0:sgfs0:thm:01:eq04}) to construct Farey terms        (\ref{eq:cfry0:sgfs0:thm:01:eq04}) to construct Farey terms
817        in the increasing or decreasing direction until $r_I$ is        in the increasing or decreasing direction until $r_I$ is
818        enclosed.        enclosed.
819  \end{itemize}  \end{itemize}
820  \end{vworkalgorithmstatementpar}  \end{vworkalgorithmstatementpar}
821  \vworkalgorithmfooter{}  \vworkalgorithmfooter{}
822    
823  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
824  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
825  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
826  \section{Number Of Terms In The Farey Series}  \section{Number Of Terms In The Farey Series}
827  %Section tag:  NTM0  %Section tag:  NTM0
828    
829  The number of terms\footnote{In the interval $[0,1]$ only.}  The number of terms\footnote{In the interval $[0,1]$ only.}
830  \index{Farey series!number of terms}  \index{Farey series!number of terms}
831  $C(N)$ in the Farey series of order $N$, $F_N$, is  $C(N)$ in the Farey series of order $N$, $F_N$, is
832    
833  \begin{equation}  \begin{equation}
834  C(N) = 1 + \sum_{k=1}^{N} \phi (k) ,  C(N) = 1 + \sum_{k=1}^{N} \phi (k) ,
835  \end{equation}  \end{equation}
836    
837  \noindent{}where $\phi(\cdot{})$ is Euler's totient  \noindent{}where $\phi(\cdot{})$ is Euler's totient
838  function \cite{bibref:w:PkuCnFareyPage}.  The  function \cite{bibref:w:PkuCnFareyPage}.  The
839  asymptotic limit for this function $C(N)$ is  asymptotic limit for this function $C(N)$ is
840    
841  \begin{equation}  \begin{equation}
842  C(N) \sim{} \frac{3 N^2}{\pi{}^2} \approx 0.3040 N^2 .  C(N) \sim{} \frac{3 N^2}{\pi{}^2} \approx 0.3040 N^2 .
843  \end{equation}  \end{equation}
844    
845  Because the number of terms in $F_N$ is approximately  Because the number of terms in $F_N$ is approximately
846  $O(N^2)$, the method presented in the previous section  $O(N^2)$, the method presented in the previous section
847  (Algorithm \ref{alg:cfry0:sgfs0:02}) is  (Algorithm \ref{alg:cfry0:sgfs0:02}) is
848  only practical for moderate $N$ (a few hundred or less).  For Farey  only practical for moderate $N$ (a few hundred or less).  For Farey
849  series of large order, building the Farey series until $r_I$ is  series of large order, building the Farey series until $r_I$ is
850  enclosed is not a practical method.  enclosed is not a practical method.
851    
852  For example, $F_{2^{32}-1}$ (a Farey series of interest for  For example, $F_{2^{32}-1}$ (a Farey series of interest for
853  computer work, because many processors can multiply 32-bit integers)  computer work, because many processors can multiply 32-bit integers)
854  contains about $1.8 \times 10^{19}$ elements.  Even using a computer  contains about $1.8 \times 10^{19}$ elements.  Even using a computer
855  that could generate $10^{9}$ Farey terms per second (an unrealistic  that could generate $10^{9}$ Farey terms per second (an unrealistic
856  assumption at the time of this writing), building  assumption at the time of this writing), building
857  $F_{2^{32}-1}$ between two consecutive integers would require over 500  $F_{2^{32}-1}$ between two consecutive integers would require over 500
858  years.  It is also noteworthy that certainly $2^{32}-1$ is not an upper  years.  It is also noteworthy that certainly $2^{32}-1$ is not an upper
859  bound on the order of Farey series that are useful in practice---with  bound on the order of Farey series that are useful in practice---with
860  scientific computers, it may be advantageous to be able to find best  scientific computers, it may be advantageous to be able to find best
861  approximations in $F_{2^{64}-1}$, $F_{2^{128}-1}$, or Farey series  approximations in $F_{2^{64}-1}$, $F_{2^{128}-1}$, or Farey series
862  of even higher order.  of even higher order.
863    
864  Algorithm \ref{alg:cfry0:sgfs0:02} is useful to illustrate concepts, or  Algorithm \ref{alg:cfry0:sgfs0:02} is useful to illustrate concepts, or
865  to find best approximations in Farey series of moderate order.  However,  to find best approximations in Farey series of moderate order.  However,
866  for Farey series of large order, this algorithm isn't usable.    for Farey series of large order, this algorithm isn't usable.  
867  \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},  \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
868  \emph{\ccfrzeroshorttitle{}}, presents algorithms based on the framework  \emph{\ccfrzeroshorttitle{}}, presents algorithms based on the framework
869  of continued fractions which are suitable for finding best rational  of continued fractions which are suitable for finding best rational
870  approximations in Farey series of large order.  approximations in Farey series of large order.
871    
872    
873  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
874  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
875  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
876  \section[Probabilistic Results Surrounding $| r_I - r_A |$]  \section[Probabilistic Results Surrounding $| r_I - r_A |$]
877          {Probabilistic Results Surrounding \mbox{\boldmath $| r_I - r_A |$}}          {Probabilistic Results Surrounding \mbox{\boldmath $| r_I - r_A |$}}
878  %Section tag:  PRS0  %Section tag:  PRS0
879    
880  \index{Farey series!probabilistic results surrounding rI-rA@probabilistic results  \index{Farey series!probabilistic results surrounding rI-rA@probabilistic results
881         surrounding $"|r_I-r_A"|$}         surrounding $"|r_I-r_A"|$}
882  If rational numbers of the form $r_A = h/k$, subject to the constraint  If rational numbers of the form $r_A = h/k$, subject to the constraint
883  $k \leq k_{MAX}$, are used to approximate arbitrary real numbers  $k \leq k_{MAX}$, are used to approximate arbitrary real numbers
884  $r_I$, it might not be clear how close we can ``typically'' choose  $r_I$, it might not be clear how close we can ``typically'' choose
885  $r_A$ to an aribtrary $r_I$ under the constraint.  $r_A$ to an aribtrary $r_I$ under the constraint.
886  We consider different asymptotics for  We consider different asymptotics for
887  the precision of the approximation of an arbitrary $r_I$ by a  the precision of the approximation of an arbitrary $r_I$ by a
888  rational number  rational number
889  $r_A=h/k$ with $k \leq k_{MAX}$. For simplicity of notation  $r_A=h/k$ with $k \leq k_{MAX}$. For simplicity of notation
890  we  we
891  denote $\alpha= r_I$ and $N=k_{ \rm MAX }$ and assume, without  denote $\alpha= r_I$ and $N=k_{ \rm MAX }$ and assume, without
892  loss of generality, that  loss of generality, that
893  $ \alpha \in [0,1]$.  $ \alpha \in [0,1]$.
894    
895  We are thus interested in the asymptotic behaviour, when $N  We are thus interested in the asymptotic behaviour, when $N
896  \rightarrow \infty$,  \rightarrow \infty$,
897  of the quantity  of the quantity
898   $$   $$
899  %\begin{equation}  %\begin{equation}
900  \label{eq:cfry0:prs0:01}  \label{eq:cfry0:prs0:01}
901  \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, ,  \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, ,
902  $$  $$
903  %\end{equation}  %\end{equation}
904  which is the distance between $\alpha$ and $F_N$, the Farey  which is the distance between $\alpha$ and $F_N$, the Farey
905  series of order $N$.  series of order $N$.
906    
907  The worst--case scenario is not very interesting: from the  The worst--case scenario is not very interesting: from the
908  construction of the Farey series  construction of the Farey series
909  we observe that for a fixed $N$ the longest intervals between the  we observe that for a fixed $N$ the longest intervals between the
910  neighbours of  $F_N$  neighbours of  $F_N$
911  are $[0,1/N]$ and  $[1-1/N,1]$ and therefore for all $N$,  are $[0,1/N]$ and  $[1-1/N,1]$ and therefore for all $N$,
912  \begin{equation}  \begin{equation}
913  \label{eq:cfry0:prs0:02}  \label{eq:cfry0:prs0:02}
914  \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, .  \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, .
915  \end{equation}  \end{equation}
916  (This supremum is achieved at the points $1/(2N)$ and $1-1/(2N)$.)  (This supremum is achieved at the points $1/(2N)$ and $1-1/(2N)$.)
917    
918  However, such behaviour of $\rho_N(\alpha)$ is not typical: as  However, such behaviour of $\rho_N(\alpha)$ is not typical: as
919  is shown below,  is shown below,
920  typical values of the approximation error $\rho_N(\alpha)$ are  typical values of the approximation error $\rho_N(\alpha)$ are
921  much smaller.  much smaller.
922    
923  First consider the behaviour of $\rho_N(\alpha)$ for almost all  First consider the behaviour of $\rho_N(\alpha)$ for almost all
924  $\alpha \in [0,1]$.\footnote{ A statement is true  $\alpha \in [0,1]$.\footnote{ A statement is true
925  for almost all $\alpha \in [0,1]$ if the measure of the set where this  for almost all $\alpha \in [0,1]$ if the measure of the set where this
926  statement is wrong has measure zero.}  statement is wrong has measure zero.}
927  We then have (see  \cite{bibref:b:Harman}, \cite{bibref:p:KargaevZ})  We then have (see  \cite{bibref:b:Harman}, \cite{bibref:p:KargaevZ})
928  that for almost all $\alpha \in [0,1]$ and any $\varepsilon >0$,  that for almost all $\alpha \in [0,1]$ and any $\varepsilon >0$,
929  (\ref{eq:cfry0:prs0:03}) and (\ref{eq:cfry0:prs0:04}) hold.  (\ref{eq:cfry0:prs0:03}) and (\ref{eq:cfry0:prs0:04}) hold.
930    
931  \begin{equation}  \begin{equation}
932  \label{eq:cfry0:prs0:03}  \label{eq:cfry0:prs0:03}
933  \lim_{N\rightarrow\infty}\rho_N(\alpha) N^2 \log^{1+\varepsilon} N =  \lim_{N\rightarrow\infty}\rho_N(\alpha) N^2 \log^{1+\varepsilon} N =
934  + \infty, \quad  + \infty, \quad
935  \liminf_{N\rightarrow\infty}  \rho_N(\alpha) N^2 \log N = 0  \liminf_{N\rightarrow\infty}  \rho_N(\alpha) N^2 \log N = 0
936  \end{equation}  \end{equation}
937    
938  \begin{equation}  \begin{equation}
939  \label{eq:cfry0:prs0:04}  \label{eq:cfry0:prs0:04}
940  \limsup_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log N } = +  \limsup_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log N } = +
941  \infty, \quad  \infty, \quad
942  \lim_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{  \lim_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{
943  \log^{1+\varepsilon} N } = 0  \log^{1+\varepsilon} N } = 0
944  \end{equation}  \end{equation}
945    
946  Even more is true: in (\ref{eq:cfry0:prs0:03}) and (\ref{eq:cfry0:prs0:04})  Even more is true: in (\ref{eq:cfry0:prs0:03}) and (\ref{eq:cfry0:prs0:04})
947  one can replace $\log N$ by $\log N \log \log N $, $\log N \log \log  one can replace $\log N$ by $\log N \log \log N $, $\log N \log \log
948  N \log \log \log N$, and so on.  N \log \log \log N$, and so on.
949  Analogously,   $\log^{1+\varepsilon} N$ could be replaced by  Analogously,   $\log^{1+\varepsilon} N$ could be replaced by
950  $\log N (\log \log N)^{1+\varepsilon} $, $\log N \log \log N (\log \log  $\log N (\log \log N)^{1+\varepsilon} $, $\log N \log \log N (\log \log
951  \log N)^{1+\varepsilon}$, and so on.  \log N)^{1+\varepsilon}$, and so on.
952    
953  These statements are analogues of Khinchin's metric theorem,  These statements are analogues of Khinchin's metric theorem,
954  the classic result  the classic result
955  in metric number theory, see e.g. \cite{bibref:b:Harman}.  in metric number theory, see e.g. \cite{bibref:b:Harman}.
956    
957  The asymptotic distribution of the suitably normalized  The asymptotic distribution of the suitably normalized
958  $\rho_N(\alpha)$  $\rho_N(\alpha)$
959  was derived in  \cite{bibref:p:KargaevZ1}.  A main result of this  was derived in  \cite{bibref:p:KargaevZ1}.  A main result of this
960  paper is that  paper is that
961  the sequence of functions  the sequence of functions
962  $N^2\rho_N(\alpha)$ converges in distribution, when $N\rightarrow  $N^2\rho_N(\alpha)$ converges in distribution, when $N\rightarrow
963  \infty$,  \infty$,
964  to the probability measure on $[0, \infty)$ with the density given  to the probability measure on $[0, \infty)$ with the density given
965  by (\ref{eq:cfry0:prs0:04b}).  by (\ref{eq:cfry0:prs0:04b}).
966    
967  \begin{equation}  \begin{equation}
968  \label{eq:cfry0:prs0:04b}  \label{eq:cfry0:prs0:04b}
969  {p}(\tau) =  {p}(\tau) =
970  \left\{\begin{array}{l}  \left\{\begin{array}{l}
971                   6/\pi^2, \hfill\mbox{ if $0 \leq \tau \leq \frac{1}{2}$ }\\                   6/\pi^2, \hfill\mbox{ if $0 \leq \tau \leq \frac{1}{2}$ }\\
972                   \\                   \\
973                   \frac{6}{\pi^2 \tau} \left(1 + \log \tau - \tau                   \frac{6}{\pi^2 \tau} \left(1 + \log \tau - \tau
974                 \right), \hfill\mbox{ if $\frac{1}{2}\leq \tau\leq 2 $ } \\                 \right), \hfill\mbox{ if $\frac{1}{2}\leq \tau\leq 2 $ } \\
975                   \\                   \\
976                 \frac{ 3}{\pi^2 \tau}\left(2\log(2 \tau)\!                 \frac{ 3}{\pi^2 \tau}\left(2\log(2 \tau)\!
977                 -\!4\log(\sqrt{\tau}\!+\!\sqrt{\tau\!-\!2})\!                 -\!4\log(\sqrt{\tau}\!+\!\sqrt{\tau\!-\!2})\!
978                 -\! (\sqrt{\tau}\!-\!\sqrt{\tau\!-\!2})^2 \right),                 -\! (\sqrt{\tau}\!-\!\sqrt{\tau\!-\!2})^2 \right),
979                               \\                               \\
980                               \hfill \mbox{ if $2 \leq \tau < \infty  $ } \\                               \hfill \mbox{ if $2 \leq \tau < \infty  $ } \\
981                    \end{array}                    \end{array}
982               \right.               \right.
983  \end{equation}  \end{equation}
984    
985  This means that  This means that
986  for all $a,A$  for all $a,A$
987  such that  such that
988   $0<a<A<\infty$,   $0<a<A<\infty$,
989  (\ref{eq:cfry0:prs0:05}) applies,  (\ref{eq:cfry0:prs0:05}) applies,
990  where  where
991  {\rm `meas'} denotes for the standard Lebesgue measure on $[0,1]$.  {\rm `meas'} denotes for the standard Lebesgue measure on $[0,1]$.
992    
993  \begin{equation}  \begin{equation}
994  \label{eq:cfry0:prs0:05}  \label{eq:cfry0:prs0:05}
995  {\rm meas}  \{ \alpha \in [0,1]: \;a < N^2 \rho_N(\alpha) \leq A \}  {\rm meas}  \{ \alpha \in [0,1]: \;a < N^2 \rho_N(\alpha) \leq A \}
996  \rightarrow  \rightarrow
997  \int_a^A {p}(\tau) d \tau\,  \int_a^A {p}(\tau) d \tau\,
998  \;\;{\rm as}\; N \rightarrow \infty  \;\;{\rm as}\; N \rightarrow \infty
999  \end{equation}  \end{equation}
1000    
1001  Another  result in \cite{bibref:p:KargaevZ1} concerns the asymptotic  Another  result in \cite{bibref:p:KargaevZ1} concerns the asymptotic
1002  behavior  behavior
1003  of the moments of the approximation error $\rho_N(\alpha) $. It  of the moments of the approximation error $\rho_N(\alpha) $. It
1004  says that  says that
1005  for any $\delta\neq 0$ and $N \rightarrow \infty$,  for any $\delta\neq 0$ and $N \rightarrow \infty$,
1006  (\ref{eq:cfry0:prs0:06}) applies,  (\ref{eq:cfry0:prs0:06}) applies,
1007   where  $\zeta(\cdot)$ and B$(\cdot,\cdot)$   where  $\zeta(\cdot)$ and B$(\cdot,\cdot)$
1008  are the Riemann zeta--function and the Beta--function,  are the Riemann zeta--function and the Beta--function,
1009  respectively.  respectively.
1010    
1011  \begin{equation}  \begin{equation}
1012  \label{eq:cfry0:prs0:06}  \label{eq:cfry0:prs0:06}
1013  %\hspace{-8mm}  %\hspace{-8mm}
1014  {  {
1015  %\textstile  %\textstile
1016  %\small  %\small
1017  \frac{\delta+1}{2}  \frac{\delta+1}{2}
1018  }  }
1019  \int_0^1 \rho_N^{\delta} (\alpha) d \alpha =  \int_0^1 \rho_N^{\delta} (\alpha) d \alpha =
1020  \left\{\begin{array}{l}  \left\{\begin{array}{l}
1021      \infty{}, \hfill\mbox{if $ \delta \leq -1 $}\\      \infty{}, \hfill\mbox{if $ \delta \leq -1 $}\\
1022      \\      \\
1023   % \frac{6}{\delta^2 (\delta+1)\pi^2 } \left(2^{-\delta} +   % \frac{6}{\delta^2 (\delta+1)\pi^2 } \left(2^{-\delta} +
1024     \frac{3}{\delta^2 \pi^2 } \left(2^{-\delta} +     \frac{3}{\delta^2 \pi^2 } \left(2^{-\delta} +
1025     \delta 2^{\delta+2} {\rm B}(\!-\delta,\frac{1}{2}) \right)     \delta 2^{\delta+2} {\rm B}(\!-\delta,\frac{1}{2}) \right)
1026     N^{-2\delta}\left(1\! +\! o(1)\right), \\     N^{-2\delta}\left(1\! +\! o(1)\right), \\
1027     \hfill\mbox{if $-1\!<\!\delta\!<\!1, \delta\! \neq\! 0$ }\\     \hfill\mbox{if $-1\!<\!\delta\!<\!1, \delta\! \neq\! 0$ }\\
1028     \\     \\
1029  \frac{3}{\pi^2} N^{-2} \log N +  \frac{3}{\pi^2} N^{-2} \log N +
1030  O\left( N^{-2} \right),  O\left( N^{-2} \right),
1031  \hfill\mbox{if $\delta =1 $ }\\  \hfill\mbox{if $\delta =1 $ }\\
1032  \\  \\
1033  %\frac{2^{1-\delta}}{1+\delta}  %\frac{2^{1-\delta}}{1+\delta}
1034  2^{-\delta}  2^{-\delta}
1035  \frac{\zeta(\delta)}{ \zeta(\delta+1)}  \frac{\zeta(\delta)}{ \zeta(\delta+1)}
1036  N^{-\delta-1}+  N^{-\delta-1}+
1037  O\left( N^{-2\delta} \right),  O\left( N^{-2\delta} \right),
1038                   \hfill  \mbox{if $\delta >1$ }                   \hfill  \mbox{if $\delta >1$ }
1039                    \end{array}                    \end{array}
1040               \right.               \right.
1041  \end{equation}  \end{equation}
1042    
1043  In particular, the average of the approximation error $\rho_N  In particular, the average of the approximation error $\rho_N
1044  (\alpha)$ asymptotically equals  (\alpha)$ asymptotically equals
1045  \begin{equation}  \begin{equation}
1046  \label{eq:cfry0:prs0:07}  \label{eq:cfry0:prs0:07}
1047  \int_{0}^1 \rho_N(\alpha) d\alpha = \frac{3}{\pi^2} \frac{\log N}{N^2} +  \int_{0}^1 \rho_N(\alpha) d\alpha = \frac{3}{\pi^2} \frac{\log N}{N^2} +
1048  O\left(\frac{1}{N^2}\right),  O\left(\frac{1}{N^2}\right),
1049  \;\;\;\; N\rightarrow \infty \,.  \;\;\;\; N\rightarrow \infty \,.
1050  \end{equation}  \end{equation}
1051    
1052  Comparison of (\ref{eq:cfry0:prs0:07})  Comparison of (\ref{eq:cfry0:prs0:07})
1053  with (\ref{eq:cfry0:prs0:04}) shows that the  with (\ref{eq:cfry0:prs0:04}) shows that the
1054  asymptotic behavior of the average approximation error $\int  asymptotic behavior of the average approximation error $\int
1055  \rho_N(\alpha) d\alpha$  \rho_N(\alpha) d\alpha$
1056  resembles the behavior of the superior limit of $\rho_N(\alpha)$.  resembles the behavior of the superior limit of $\rho_N(\alpha)$.
1057  Even this limit  Even this limit
1058  decreases much faster than the maximum error $\max_{\alpha }  decreases much faster than the maximum error $\max_{\alpha }
1059  \rho_N(\alpha)$, see  \rho_N(\alpha)$, see
1060  (\ref{eq:cfry0:prs0:02}): for typical $\alpha$ the rate of decrease of  (\ref{eq:cfry0:prs0:02}): for typical $\alpha$ the rate of decrease of
1061  $\rho_N(\alpha)$, when $ N\rightarrow \infty ,$  $\rho_N(\alpha)$, when $ N\rightarrow \infty ,$
1062  is, roughly speaking,  $1/N^2$ rather than $1/N$, the error for the  is, roughly speaking,  $1/N^2$ rather than $1/N$, the error for the
1063  worst combination of $\alpha$ and $N$.  worst combination of $\alpha$ and $N$.
1064    
1065  These results show that there is a significant advantage to using the Farey series  These results show that there is a significant advantage to using the Farey series
1066  as the set from which to choose rational approximations, rather than  as the set from which to choose rational approximations, rather than
1067  more naively using only rational numbers with the maximum  more naively using only rational numbers with the maximum
1068  denominator $k_{MAX}$ (as is often done in practice).  denominator $k_{MAX}$ (as is often done in practice).
1069    
1070    
1071  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1072  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1073  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1074  \section[Integer Lattice Interpretation]  \section[Integer Lattice Interpretation]
1075          {Integer Lattice Interpretation Of The Farey Series}          {Integer Lattice Interpretation Of The Farey Series}
1076  %Section tag: ILI0  %Section tag: ILI0
1077    
1078  The Farey series has a convenient and intuitive graphical interpretation  The Farey series has a convenient and intuitive graphical interpretation
1079  involving the integer lattice\index{integer lattice}\index{lattice}%  involving the integer lattice\index{integer lattice}\index{lattice}%
1080  \index{Farey series!integer lattice interpretation}  \index{Farey series!integer lattice interpretation}
1081  (see Fig. \ref{fig:cfry0:ili0:00},  (see Fig. \ref{fig:cfry0:ili0:00},
1082  which illustrates this interpretation, but with $h$  which illustrates this interpretation, but with $h$
1083  also restricted).  also restricted).
1084  (By integer lattice, we mean the $\vworkrealset{}^2$ plane  (By integer lattice, we mean the $\vworkrealset{}^2$ plane
1085  with each point $(x,y)$, $x,y \in \vworkintset$, marked.)  with each point $(x,y)$, $x,y \in \vworkintset$, marked.)
1086  In such an interpretation, each rational number $h/k$ corresponds to  In such an interpretation, each rational number $h/k$ corresponds to
1087  a point $(k,h)$ which is $h$ units above and $k$ units  a point $(k,h)$ which is $h$ units above and $k$ units
1088  to the right of the origin.  to the right of the origin.
1089    
1090  \begin{figure}  \begin{figure}
1091  \centering  \centering
1092  \includegraphics[width=4.6in]{c_fry0/farey01a.eps}  \includegraphics[width=4.6in]{c_fry0/farey01a.eps}
1093  \caption{Graphical Interpretation Of Rational Numbers  \caption{Graphical Interpretation Of Rational Numbers
1094           $h/k$ That Can Be Formed With $h \leq h_{MAX}=3$, $k \leq k_{MAX}=5$}           $h/k$ That Can Be Formed With $h \leq h_{MAX}=3$, $k \leq k_{MAX}=5$}
1095  \label{fig:cfry0:ili0:00}  \label{fig:cfry0:ili0:00}
1096  \end{figure}  \end{figure}
1097    
1098  From the graphical interpretation suggested by Fig. \ref{fig:cfry0:ili0:00},  From the graphical interpretation suggested by Fig. \ref{fig:cfry0:ili0:00},
1099  the following properties are intuitively clear.  the following properties are intuitively clear.
1100    
1101  \begin{itemize}  \begin{itemize}
1102     \item The angle of a ray drawn from the origin to the point     \item The angle of a ray drawn from the origin to the point
1103           $(k,h)$ corresponding to the rational number $h/k$ is           $(k,h)$ corresponding to the rational number $h/k$ is
1104           $\theta = tan^{-1} \; h/k$.           $\theta = tan^{-1} \; h/k$.
1105    
1106     \item Any integer lattice point on a line from     \item Any integer lattice point on a line from
1107           the origin drawn at the angle $\theta$           the origin drawn at the angle $\theta$
1108           has the value $h/k = tan \; \theta$.  All points corresponding           has the value $h/k = tan \; \theta$.  All points corresponding
1109           to rational numbers with the same value will be on such a line,           to rational numbers with the same value will be on such a line,
1110           and thus form an equivalence class.           and thus form an equivalence class.
1111    
1112     \item A rational number $h/k$ is irreducible iff its corresponding     \item A rational number $h/k$ is irreducible iff its corresponding
1113           point $(k,h)$ is ``directly'' visible from the origin with           point $(k,h)$ is ``directly'' visible from the origin with
1114           no intervening points.           no intervening points.
1115    
1116     \item The Farey series of order $N$, $F_N$, can be     \item The Farey series of order $N$, $F_N$, can be
1117           formed graphically by starting with the           formed graphically by starting with the
1118                   set of integer lattice points                   set of integer lattice points
1119                   $(k,h): \; h \in \vworkintsetnonneg \wedge 1 \leq k \leq N$,                   $(k,h): \; h \in \vworkintsetnonneg \wedge 1 \leq k \leq N$,
1120                   then sweeping                   then sweeping
1121           a line extended from the origin, starting with           a line extended from the origin, starting with
1122           angle $\theta = 0$, through           angle $\theta = 0$, through
1123           $0 \leq \theta < \pi{}/2$, and recording           $0 \leq \theta < \pi{}/2$, and recording
1124           in order each point directly visible from           in order each point directly visible from
1125           the origin.\footnote{Note that Fig. \ref{fig:cfry0:ili0:00},           the origin.\footnote{Note that Fig. \ref{fig:cfry0:ili0:00},
1126           because it illustrates the case when $h$ is constrained           because it illustrates the case when $h$ is constrained
1127           as well, does not show integer lattice points for           as well, does not show integer lattice points for
1128           $h > h_{MAX}$.  In principle, if the integer lattice shown           $h > h_{MAX}$.  In principle, if the integer lattice shown
1129           in Fig. \ref{fig:cfry0:ili0:00} were extended indefinitely           in Fig. \ref{fig:cfry0:ili0:00} were extended indefinitely
1130           ``upward'', every positive irreducible rational number with           ``upward'', every positive irreducible rational number with
1131           $k \leq k_{MAX} = 5$ could be found graphically.}           $k \leq k_{MAX} = 5$ could be found graphically.}
1132  \end{itemize}  \end{itemize}
1133    
1134  Fig. \ref{fig:cfry0:chk0:01} illustrates the graphical construction method  Fig. \ref{fig:cfry0:chk0:01} illustrates the graphical construction method
1135  of $F_5$.  Note that only integer lattice points which are directly  of $F_5$.  Note that only integer lattice points which are directly
1136  visible from the origin (with no intervening points) are selected.  visible from the origin (with no intervening points) are selected.
1137  (Fig. \ref{fig:cfry0:chk0:01}, like Fig. \ref{fig:cfry0:ili0:00},  (Fig. \ref{fig:cfry0:chk0:01}, like Fig. \ref{fig:cfry0:ili0:00},
1138  shows the case of constrained $h$---the integer lattice should be  shows the case of constrained $h$---the integer lattice should be
1139  continued ``upward'' to construct the Farey series.)  continued ``upward'' to construct the Farey series.)
1140    
1141  \begin{figure}  \begin{figure}
1142  \centering  \centering
1143  \includegraphics[width=4.6in]{c_fry0/farey01b.eps}  \includegraphics[width=4.6in]{c_fry0/farey01b.eps}
1144  \caption{Graphical Interpretation Of Irreducible Rational Numbers  \caption{Graphical Interpretation Of Irreducible Rational Numbers
1145           $h/k$ That Can Be Formed With $h \leq h_{MAX}=3$, $k \leq k_{MAX}=5$}           $h/k$ That Can Be Formed With $h \leq h_{MAX}=3$, $k \leq k_{MAX}=5$}
1146  \label{fig:cfry0:chk0:01}  \label{fig:cfry0:chk0:01}
1147  \end{figure}  \end{figure}
1148    
1149    
1150  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1151  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1152  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1153  \section[Generating $F_{k_{MAX}, \overline{h_{MAX}}}$ In A Rectangular Region]  \section[Generating $F_{k_{MAX}, \overline{h_{MAX}}}$ In A Rectangular Region]
1154          {Generating \mbox{\boldmath $F_{k_{MAX}, \overline{h_{MAX}}}$}          {Generating \mbox{\boldmath $F_{k_{MAX}, \overline{h_{MAX}}}$}
1155           Over A Rectangular Region Of The Integer Lattice}           Over A Rectangular Region Of The Integer Lattice}
1156  %Section tag: CHK0  %Section tag: CHK0
1157  \label{cfry0:schk0}  \label{cfry0:schk0}
1158    
1159  \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$}  \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$}
1160  In practice, $F_N$ does not represent the set of  In practice, $F_N$ does not represent the set of
1161  rational numbers that may be used for rational approximation in an  rational numbers that may be used for rational approximation in an
1162  application; hence it isn't usually appropriate to choose a  application; hence it isn't usually appropriate to choose a
1163  rational number from $F_N$ strictly as  rational number from $F_N$ strictly as
1164  the theory of numbers defines it.    the theory of numbers defines it.  
1165  An actual application is parameterized not just by  An actual application is parameterized not just by
1166  $k_{MAX}$ (the maximum denominator that may be chosen, which is considered  $k_{MAX}$ (the maximum denominator that may be chosen, which is considered
1167  in the definition of the Farey series),  in the definition of the Farey series),
1168  but also by $h_{MAX}$ (the maximum numerator  but also by $h_{MAX}$ (the maximum numerator
1169  that may be chosen).  Typically, $h_{MAX}$ exists as a constraint  that may be chosen).  Typically, $h_{MAX}$ exists as a constraint
1170  because a machine multiplication instruction is limited in the size of the  because a machine multiplication instruction is limited in the size of the
1171  operands it can accomodate; and $k_{MAX}$ exists as a constraint because  operands it can accomodate; and $k_{MAX}$ exists as a constraint because
1172  a machine division instruction is limited in the size of the divisor  a machine division instruction is limited in the size of the divisor
1173  it can accomodate.  it can accomodate.
1174    
1175  In practice, the rational numbers that may be used for rational  In practice, the rational numbers that may be used for rational
1176  approximation represent a rectangular region of the integer  approximation represent a rectangular region of the integer
1177  lattice---all $(k,h):$ $h \leq h_{MAX} \wedge k \leq k_{MAX}$  lattice---all $(k,h):$ $h \leq h_{MAX} \wedge k \leq k_{MAX}$
1178  (Figs. \ref{fig:cfry0:ili0:00}, \ref{fig:cfry0:chk0:01}).  (Figs. \ref{fig:cfry0:ili0:00}, \ref{fig:cfry0:chk0:01}).
1179    
1180  Fig. \ref{fig:cfry0:ili0:00} supplies a graphical  Fig. \ref{fig:cfry0:ili0:00} supplies a graphical
1181  interpretation of all rational numbers  interpretation of all rational numbers
1182  that can be formed with constraints $h \leq h_{MAX} = 3$  that can be formed with constraints $h \leq h_{MAX} = 3$
1183  and $k \leq k_{MAX} = 5$.  Each point of the integer lattice  and $k \leq k_{MAX} = 5$.  Each point of the integer lattice
1184  shown in the figure is a rational number, not necessarily  shown in the figure is a rational number, not necessarily
1185  irreducible.  Because under this graphical interpretation  irreducible.  Because under this graphical interpretation
1186  a rational number is irreducible iff it can be reached  a rational number is irreducible iff it can be reached
1187  by a ray from the origin with no intervening rational numbers,  by a ray from the origin with no intervening rational numbers,
1188  it is clear that the complete ordered set of irreducible  it is clear that the complete ordered set of irreducible
1189  rational numbers that can be formed under the  rational numbers that can be formed under the
1190  constraints $h \leq h_{MAX}$ and $k \leq k_{MAX}$  constraints $h \leq h_{MAX}$ and $k \leq k_{MAX}$
1191  can be obtained graphically by sweeping a ray from  can be obtained graphically by sweeping a ray from
1192  the origin through the angles $0 \leq \theta < \pi/2$,  the origin through the angles $0 \leq \theta < \pi/2$,
1193  recording each point directly visible from the origin.  recording each point directly visible from the origin.
1194  This graphical construction process is illustrated  This graphical construction process is illustrated
1195  in Fig. \ref{fig:cfry0:chk0:01}.  in Fig. \ref{fig:cfry0:chk0:01}.
1196    
1197  From the graphical construction process shown in  From the graphical construction process shown in
1198  Fig. \ref{fig:cfry0:chk0:01}, it can be seen that the  Fig. \ref{fig:cfry0:chk0:01}, it can be seen that the
1199  set of irreducible rational numbers that can be formed  set of irreducible rational numbers that can be formed
1200  subject to the constraints  subject to the constraints
1201  $h \leq h_{MAX} \wedge k \leq k_{MAX}$ is:  $h \leq h_{MAX} \wedge k \leq k_{MAX}$ is:
1202    
1203  \begin{equation}  \begin{equation}
1204  \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},  \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},
1205            \frac{1}{3}, \frac{2}{5}, \frac{1}{2},            \frac{1}{3}, \frac{2}{5}, \frac{1}{2},
1206            \frac{3}{5},            \frac{3}{5},
1207            \frac{2}{3}, \frac{3}{4}, \frac{1}{1},            \frac{2}{3}, \frac{3}{4}, \frac{1}{1},
1208            \frac{3}{2}, \frac{2}{1}, \frac{3}{1} } \right\} .            \frac{3}{2}, \frac{2}{1}, \frac{3}{1} } \right\} .
1209  \end{equation}  \end{equation}
1210    
1211  We denote the ordered set of irreducible rational  We denote the ordered set of irreducible rational
1212  numbers that can be formed subject to the  numbers that can be formed subject to the
1213  constraints $h \leq h_{MAX} \wedge k \leq k_{MAX}$ as  constraints $h \leq h_{MAX} \wedge k \leq k_{MAX}$ as
1214  $F_{k_{MAX}, \overline{h_{MAX}}}$.\footnote{Notationally,  $F_{k_{MAX}, \overline{h_{MAX}}}$.\footnote{Notationally,
1215  in general,  in general,
1216  we use an overbar on the order of a Farey series to  we use an overbar on the order of a Farey series to
1217  denote that the terms are inverted and reversed in order.  denote that the terms are inverted and reversed in order.
1218  For example, $F_3 = \{ 0/1, 1/3, 1/2, \ldots \}$, but  For example, $F_3 = \{ 0/1, 1/3, 1/2, \ldots \}$, but
1219  $F_{\overline{3}}  = \{ \ldots , 2/1, 3/1 \}$.  Notation  $F_{\overline{3}}  = \{ \ldots , 2/1, 3/1 \}$.  Notation
1220  such as $F_{A, \overline{B}}$ is an extension of that convention.}  such as $F_{A, \overline{B}}$ is an extension of that convention.}
1221    
1222  There are three important questions to be asked about  There are three important questions to be asked about
1223  the series $F_{k_{MAX}, \overline{h_{MAX}}}$:  the series $F_{k_{MAX}, \overline{h_{MAX}}}$:
1224    
1225  \begin{itemize}  \begin{itemize}
1226  \item What are the smallest and largest rational numbers in  \item What are the smallest and largest rational numbers in
1227        $F_{k_{MAX}, \overline{h_{MAX}}}$?        $F_{k_{MAX}, \overline{h_{MAX}}}$?
1228        (This question is easy:  the smallest two rational numbers        (This question is easy:  the smallest two rational numbers
1229            in $F_{k_{MAX}, \overline{h_{MAX}}}$ are $0/1$            in $F_{k_{MAX}, \overline{h_{MAX}}}$ are $0/1$
1230            and $1/k_{MAX}$, and the largest rational number            and $1/k_{MAX}$, and the largest rational number
1231            is $h_{MAX}/1$.)            is $h_{MAX}/1$.)
1232    
1233  \item How do we construct $F_{k_{MAX}, \overline{h_{MAX}}}$?  \item How do we construct $F_{k_{MAX}, \overline{h_{MAX}}}$?
1234    
1235  \item If we desire to approximate a real number  \item If we desire to approximate a real number
1236        $r_I$, $r_{IMIN} \leq r_I \leq r_{IMAX}$,        $r_I$, $r_{IMIN} \leq r_I \leq r_{IMAX}$,
1237        using a rational number selected from        using a rational number selected from
1238            $F_{k_{MAX}, \overline{h_{MAX}}}$, how large might            $F_{k_{MAX}, \overline{h_{MAX}}}$, how large might
1239        the error $| h/k - r_I |$ be?        the error $| h/k - r_I |$ be?
1240  \end{itemize}  \end{itemize}
1241    
1242    
1243  \subsection[Construction Of $F_{k_{MAX},\overline{h_{MAX}}}$]  \subsection[Construction Of $F_{k_{MAX},\overline{h_{MAX}}}$]
1244             {Construction Of \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}}             {Construction Of \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}}
1245    
1246  \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$!construction of}  \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$!construction of}
1247  To construct $F_{k_{MAX}, \overline{h_{MAX}}}$, for  To construct $F_{k_{MAX}, \overline{h_{MAX}}}$, for
1248  $0 \leq \theta \leq \tan^{-1} (h_{MAX}/k_{MAX})$---the  $0 \leq \theta \leq \tan^{-1} (h_{MAX}/k_{MAX})$---the
1249  region of the series where $k_{MAX}$ is the dominant constraint,  region of the series where $k_{MAX}$ is the dominant constraint,
1250  i.e. below the ``corner point'' in Figs. \ref{fig:cfry0:ili0:00}  i.e. below the ``corner point'' in Figs. \ref{fig:cfry0:ili0:00}
1251  and \ref{fig:cfry0:chk0:01}---note  and \ref{fig:cfry0:chk0:01}---note
1252  that these terms are simply  that these terms are simply
1253  $F_{k_{MAX}}$ up to $h_{MAX}/k_{MAX}$ or its reduced  $F_{k_{MAX}}$ up to $h_{MAX}/k_{MAX}$ or its reduced
1254  equivalent.\footnote{If this is not intuitively clear,  equivalent.\footnote{If this is not intuitively clear,
1255  note in Figs. \ref{fig:cfry0:ili0:00} and \ref{fig:cfry0:chk0:01}  note in Figs. \ref{fig:cfry0:ili0:00} and \ref{fig:cfry0:chk0:01}
1256  that all of the terms of $F_{k_{MAX}}$---that is, all rational  that all of the terms of $F_{k_{MAX}}$---that is, all rational
1257  numbers, both reducible and irreducible, with $k \leq k_{MAX}$---are  numbers, both reducible and irreducible, with $k \leq k_{MAX}$---are
1258  available for selection  available for selection
1259  until the ``corner point'' is reached.}  until the ``corner point'' is reached.}
1260  To construct $F_{k_{MAX}, \overline{h_{MAX}}}$ for  To construct $F_{k_{MAX}, \overline{h_{MAX}}}$ for
1261  $\tan^{-1} (h_{MAX}/k_{MAX}) < \theta < \pi/2$---the  $\tan^{-1} (h_{MAX}/k_{MAX}) < \theta < \pi/2$---the
1262  region of the series where $h_{MAX}$ is the dominant constraint,  region of the series where $h_{MAX}$ is the dominant constraint,
1263  i.e. above the ``corner point'' in Figs. \ref{fig:cfry0:ili0:00}  i.e. above the ``corner point'' in Figs. \ref{fig:cfry0:ili0:00}
1264  and \ref{fig:cfry0:chk0:01}---note that by a graphical argument  and \ref{fig:cfry0:chk0:01}---note that by a graphical argument
1265  of symmetry, these terms are the reciprocals of ascending terms of $F_{h_{MAX}}$.  of symmetry, these terms are the reciprocals of ascending terms of $F_{h_{MAX}}$.
1266  For example, in Fig. \ref{fig:cfry0:chk0:01}, if the $h$- and $k$-  For example, in Fig. \ref{fig:cfry0:chk0:01}, if the $h$- and $k$-
1267  axes are transposed, it is easy to see that $3/1$ in the original integer lattice  axes are transposed, it is easy to see that $3/1$ in the original integer lattice
1268  would correspond to $1/3$ in the transposed integer lattice.  This argument of  would correspond to $1/3$ in the transposed integer lattice.  This argument of
1269  symmetry immediately suggests a procedure for constructing  symmetry immediately suggests a procedure for constructing
1270  $F_{k_{MAX},\overline{h_{MAX}}}$.  $F_{k_{MAX},\overline{h_{MAX}}}$.
1271    
1272  \begin{itemize}  \begin{itemize}
1273  \item Construct $F_{k_{MAX}}$ from $0/1$ up through $h_{MAX}/k_{MAX}$ or its  \item Construct $F_{k_{MAX}}$ from $0/1$ up through $h_{MAX}/k_{MAX}$ or its
1274        reduced equivalent.        reduced equivalent.
1275  \item Construct $F_{h_{MAX}}$ from $1/h_{MAX}$ up to $k_{MAX}/h_{MAX}$ or  \item Construct $F_{h_{MAX}}$ from $1/h_{MAX}$ up to $k_{MAX}/h_{MAX}$ or
1276        its reduced equivalent; then reverse the order of the        its reduced equivalent; then reverse the order of the
1277            terms and take the reciprocal of            terms and take the reciprocal of
1278        each term.        each term.
1279  \item Concatenate the results from the two steps above.  \item Concatenate the results from the two steps above.
1280  \end{itemize}  \end{itemize}
1281    
1282  \begin{vworkexamplestatement}  \begin{vworkexamplestatement}
1283  \label{ex:cfry0:schk:00}  \label{ex:cfry0:schk:00}
1284  Construct $F_{5,\overline{3}}$, the set of  Construct $F_{5,\overline{3}}$, the set of
1285  all irreducible rational numbers $h/k$  all irreducible rational numbers $h/k$
1286  that can be formed with $h \leq h_{MAX}=3$ and  that can be formed with $h \leq h_{MAX}=3$ and
1287  $k \leq k_{MAX}=5$.\footnote{Note that $F_{5,\overline{3}}$  $k \leq k_{MAX}=5$.\footnote{Note that $F_{5,\overline{3}}$
1288  is the series depicted in Fig. \ref{fig:cfry0:chk0:01}, and  is the series depicted in Fig. \ref{fig:cfry0:chk0:01}, and
1289  this example can be verified against the figure.}  this example can be verified against the figure.}
1290  \end{vworkexamplestatement}  \end{vworkexamplestatement}
1291  \begin{vworkexampleparsection}{Solution}  \begin{vworkexampleparsection}{Solution}
1292  (Using the method of construction presented above.)  (Using the method of construction presented above.)
1293  First, $F_5$ up through $h_{MAX}/k_{MAX} = 3/5$ or its reduced  First, $F_5$ up through $h_{MAX}/k_{MAX} = 3/5$ or its reduced
1294  equivalent should be constructed.  This series is  equivalent should be constructed.  This series is
1295    
1296  \begin{equation}  \begin{equation}
1297  \label{eq:cfry0:schk:ex00:eq00}  \label{eq:cfry0:schk:ex00:eq00}
1298  F_5 =  F_5 =
1299  \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},  \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},
1300            \frac{1}{3}, \frac{2}{5}, \frac{1}{2},            \frac{1}{3}, \frac{2}{5}, \frac{1}{2},
1301            \frac{3}{5}, \ldots{} } \right\} .            \frac{3}{5}, \ldots{} } \right\} .
1302  \end{equation}  \end{equation}
1303    
1304  Second, $F_3$ is constructed from $1/3$ up to $k_{MAX}/h_{MAX} = 5/3$ or  Second, $F_3$ is constructed from $1/3$ up to $k_{MAX}/h_{MAX} = 5/3$ or
1305  its reduced equivalent (not including the  its reduced equivalent (not including the
1306  final term, $5/3$).  This series is  final term, $5/3$).  This series is
1307    
1308  \begin{equation}  \begin{equation}
1309  \label{eq:cfry0:schk:ex00:eq01}  \label{eq:cfry0:schk:ex00:eq01}
1310  F_3 =  F_3 =
1311  \left\{ { \ldots , \frac{1}{3}, \frac{1}{2}, \frac{2}{3},  \left\{ { \ldots , \frac{1}{3}, \frac{1}{2}, \frac{2}{3},
1312            \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \ldots{} } \right\} .            \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \ldots{} } \right\} .
1313  \end{equation}  \end{equation}
1314    
1315  Third, the terms of $F_3$ are reversed in order, and the reciprocal of each term is  Third, the terms of $F_3$ are reversed in order, and the reciprocal of each term is
1316  calculated, yielding  calculated, yielding
1317    
1318  \begin{equation}  \begin{equation}
1319  \label{eq:cfry0:schk:ex00:eq02}  \label{eq:cfry0:schk:ex00:eq02}
1320  F_{\overline{3}} =  F_{\overline{3}} =
1321  \left\{ { \ldots{}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1},  \left\{ { \ldots{}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1},
1322            \frac{3}{2}, \frac{2}{1}, \frac{3}{1}  } \right\} .            \frac{3}{2}, \frac{2}{1}, \frac{3}{1}  } \right\} .
1323  \end{equation}  \end{equation}
1324    
1325  Finally, concatenating (\ref{eq:cfry0:schk:ex00:eq00})  Finally, concatenating (\ref{eq:cfry0:schk:ex00:eq00})
1326  and  and
1327  (\ref{eq:cfry0:schk:ex00:eq02}) yields $F_{5,\overline{3}}$, below.  (\ref{eq:cfry0:schk:ex00:eq02}) yields $F_{5,\overline{3}}$, below.
1328    
1329  \begin{equation}  \begin{equation}
1330  \label{eq:cfry0:schk:ex00:eq03}  \label{eq:cfry0:schk:ex00:eq03}
1331  F_{5,\overline{3}} =  F_{5,\overline{3}} =
1332  \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},  \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},
1333            \frac{1}{3}, \frac{2}{5}, \frac{1}{2},            \frac{1}{3}, \frac{2}{5}, \frac{1}{2},
1334            \frac{3}{5},            \frac{3}{5},
1335            \frac{2}{3}, \frac{3}{4}, \frac{1}{1},            \frac{2}{3}, \frac{3}{4}, \frac{1}{1},
1336            \frac{3}{2}, \frac{2}{1}, \frac{3}{1} } \right\}            \frac{3}{2}, \frac{2}{1}, \frac{3}{1} } \right\}
1337  \end{equation}  \end{equation}
1338    
1339  \end{vworkexampleparsection}  \end{vworkexampleparsection}
1340  \vworkexamplefooter{}  \vworkexamplefooter{}
1341    
1342  It is clear that Thm. \ref{thm:cfry0:sgfs0:01}  It is clear that Thm. \ref{thm:cfry0:sgfs0:01}
1343  and (\ref{eq:cfry0:sgfs0:thm:01:eq01}) through  and (\ref{eq:cfry0:sgfs0:thm:01:eq01}) through
1344  (\ref{eq:cfry0:sgfs0:thm:01:eq04}) can be used to construct  (\ref{eq:cfry0:sgfs0:thm:01:eq04}) can be used to construct
1345  $F_{k_{MAX}, \overline{h_{MAX}}}$.  However, such algorithms  $F_{k_{MAX}, \overline{h_{MAX}}}$.  However, such algorithms
1346  are not discussed because---even with refinements---they  are not discussed because---even with refinements---they
1347  can be no better than $O(N)$ and are not  can be no better than $O(N)$ and are not
1348  fruitful to develop.  Instead, an $O(log N)$  fruitful to develop.  Instead, an $O(log N)$
1349  algorithm is presented in  algorithm is presented in
1350  \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},  \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
1351  \emph{\ccfrzeroshorttitle{}}.  \emph{\ccfrzeroshorttitle{}}.
1352    
1353    
1354  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1355  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1356  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1357  \subsection[Distance Between Terms Of $F_{h_{MAX},k_{MAX}}$]  \subsection[Distance Between Terms Of $F_{h_{MAX},k_{MAX}}$]
1358             {Distance Between Terms Of \mbox{\boldmath $F_{h_{MAX},k_{MAX}}$}}             {Distance Between Terms Of \mbox{\boldmath $F_{h_{MAX},k_{MAX}}$}}
1359    
1360  \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$!distance between terms}  \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$!distance between terms}
1361  \index{Farey series!distance between terms}  \index{Farey series!distance between terms}
1362  The maximum \emph{distance} between terms of $F_{h_{MAX},k_{MAX}}$ also establishes  The maximum \emph{distance} between terms of $F_{h_{MAX},k_{MAX}}$ also establishes
1363  what we call the maximum \emph{placement error}, $|r_A - r_I|$, in choosing  what we call the maximum \emph{placement error}, $|r_A - r_I|$, in choosing
1364  $r_A = h/k$.  Specifically, the maximum distance is twice the maximum placement  $r_A = h/k$.  Specifically, the maximum distance is twice the maximum placement
1365  error.  Clearly, with a maximum distance specified, choosing $r_I = (x+y)/2$ for  error.  Clearly, with a maximum distance specified, choosing $r_I = (x+y)/2$ for
1366  two successive terms $x$ and $y$ separated by the maximum distance is  two successive terms $x$ and $y$ separated by the maximum distance is
1367  the most antagonistic  the most antagonistic
1368  choice of $r_I$ possible.  choice of $r_I$ possible.
1369  We use the two notions (maximum distance and maximum placement error)  We use the two notions (maximum distance and maximum placement error)
1370  interchangeably and don't bother to convert between them, as they are  interchangeably and don't bother to convert between them, as they are
1371  the same notion and differ only by a factor of two.  the same notion and differ only by a factor of two.
1372    
1373  It is clear from the earlier discussion of the Farey series that the maximum  It is clear from the earlier discussion of the Farey series that the maximum
1374  distance between terms in $F_{k_{MAX}}$ is $1/k_{MAX}$, and that this maximum  distance between terms in $F_{k_{MAX}}$ is $1/k_{MAX}$, and that this maximum
1375  distance occurs only adjacent to an integer.  It is also clear from the  distance occurs only adjacent to an integer.  It is also clear from the
1376  discussion of $F_{\overline{h_{MAX}}}$ that the maximum distance between terms  discussion of $F_{\overline{h_{MAX}}}$ that the maximum distance between terms
1377  is 1.  is 1.
1378    
1379  Thus, when we use $F_{k_{MAX}, \overline{h_{MAX}}}$ to approximate real numbers,  Thus, when we use $F_{k_{MAX}, \overline{h_{MAX}}}$ to approximate real numbers,
1380  in general the worst-case distance between terms is 1.  in general the worst-case distance between terms is 1.
1381    
1382  In practical applications when rational approximation is used,  In practical applications when rational approximation is used,
1383  the approximation tends to be used over a restricted interval  the approximation tends to be used over a restricted interval
1384  $[l \gg  0, r \ll h_{MAX}]$ rather than over the full range of the rational numbers that  $[l \gg  0, r \ll h_{MAX}]$ rather than over the full range of the rational numbers that
1385  can be formed, $[0, h_{MAX}]$.  This section develops novel upper bounds on  can be formed, $[0, h_{MAX}]$.  This section develops novel upper bounds on
1386  the distance between terms of $F_{k_{MAX}, \overline{h_{MAX}}}$ in an interval  the distance between terms of $F_{k_{MAX}, \overline{h_{MAX}}}$ in an interval
1387  $[l,r]$.  For simplicity, assume $l,r \in F_{k_{MAX}, \overline{h_{MAX}}}$.  $[l,r]$.  For simplicity, assume $l,r \in F_{k_{MAX}, \overline{h_{MAX}}}$.
1388    
1389  Three distinct cases are developed (Figure \ref{fig:cfry0:schk0:threecases}).  Three distinct cases are developed (Figure \ref{fig:cfry0:schk0:threecases}).
1390  The upper bound developed from Case III is always larger than the upper  The upper bound developed from Case III is always larger than the upper
1391  bound developed from Case II, which is always larger than the upper bound developed  bound developed from Case II, which is always larger than the upper bound developed
1392  from Case I; so if only the absolute maximum error over  from Case I; so if only the absolute maximum error over
1393  the interval $[l,r]$ is of interest, only the  the interval $[l,r]$ is of interest, only the
1394  highest-numbered case which applies needs to be evaluated.  However, some  highest-numbered case which applies needs to be evaluated.  However, some
1395  applications may have different error requirements in different regions  applications may have different error requirements in different regions
1396  of the interval $[l,r]$, and for these applications it may be beneficial  of the interval $[l,r]$, and for these applications it may be beneficial
1397  to analyze more than one case.  to analyze more than one case.
1398    
1399  \begin{figure}  \begin{figure}
1400  \centering  \centering
1401  \includegraphics[width=4.6in]{c_fry0/errreg01.eps}  \includegraphics[width=4.6in]{c_fry0/errreg01.eps}
1402  \caption{Three Cases For Bounding Distance Between Terms In  \caption{Three Cases For Bounding Distance Between Terms In
1403           $F_{k_{MAX}, \overline{h_{MAX}}}$}           $F_{k_{MAX}, \overline{h_{MAX}}}$}
1404  \label{fig:cfry0:schk0:threecases}  \label{fig:cfry0:schk0:threecases}
1405  \end{figure}  \end{figure}
1406    
1407    
1408  \subsubsection[Case I:  $r_I < h_{MAX}/k_{MAX}$]  \subsubsection[Case I:  $r_I < h_{MAX}/k_{MAX}$]
1409                {Case I:  \mbox{\boldmath $r_I < h_{MAX}/k_{MAX}$}}                {Case I:  \mbox{\boldmath $r_I < h_{MAX}/k_{MAX}$}}
1410    
1411  With $r_I < h_{MAX}/k_{MAX}$, $k \leq k_{MAX}$ is the dominant  With $r_I < h_{MAX}/k_{MAX}$, $k \leq k_{MAX}$ is the dominant
1412  constraint, and the neighbors available to $r_I$ are simply the  constraint, and the neighbors available to $r_I$ are simply the
1413  terms of $F_{k_{MAX}}$.  If $[l, r] \cap  [0, h_{MAX}/k_{MAX}]$  terms of $F_{k_{MAX}}$.  If $[l, r] \cap  [0, h_{MAX}/k_{MAX}]$
1414  includes an integer, clearly the maximum distance from $r_I$ to the  includes an integer, clearly the maximum distance from $r_I$ to the
1415  nearest available term of $F_{k_{MAX}, \overline{h_{MAX}}}$ is given  nearest available term of $F_{k_{MAX}, \overline{h_{MAX}}}$ is given
1416  by  by
1417    
1418  \begin{equation}  \begin{equation}
1419  \left|  \left|
1420  \frac{h}{k} - r_I  \frac{h}{k} - r_I
1421  \right|  \right|
1422  \leq  \leq
1423  \frac{1}{2 k_{MAX}} ,  \frac{1}{2 k_{MAX}} ,
1424  \end{equation}  \end{equation}
1425    
1426  which is the same result for the Farey series in general.  which is the same result for the Farey series in general.
1427    
1428  If $[l, r] \cap  [0, h_{MAX}/k_{MAX}]$ does  If $[l, r] \cap  [0, h_{MAX}/k_{MAX}]$ does
1429  not include an integer, it can be shown that the  not include an integer, it can be shown that the
1430  maximum distance between Farey terms is driven by the  maximum distance between Farey terms is driven by the
1431  rational number with the smallest denominator in the  rational number with the smallest denominator in the
1432  interval $[l, r]$.  interval $[l, r]$.
1433    
1434  For two consecutive terms $p/q$ and $p'/q'$ in $F_{k_{MAX}}$,  For two consecutive terms $p/q$ and $p'/q'$ in $F_{k_{MAX}}$,
1435  $p'q - pq' = 1$ (Thm. \ref{thm:cfry0:spfs:02}), so that  $p'q - pq' = 1$ (Thm. \ref{thm:cfry0:spfs:02}), so that
1436    
1437  \begin{equation}  \begin{equation}
1438  \frac{p'}{q'} - \frac{p}{q} =  \frac{p'}{q'} - \frac{p}{q} =
1439  \frac{p'q - pq'}{q q'} = \frac{1}{qq'} .  \frac{p'q - pq'}{q q'} = \frac{1}{qq'} .
1440  \end{equation}  \end{equation}
1441    
1442  By Thm. \ref{thm:cfry0:spfs:02ba}, $q+q' > k_{MAX}$, therefore  By Thm. \ref{thm:cfry0:spfs:02ba}, $q+q' > k_{MAX}$, therefore
1443    
1444  \begin{equation}  \begin{equation}
1445  \label{eq:cfry0:schk0:minqplacementupperbound}  \label{eq:cfry0:schk0:minqplacementupperbound}
1446  \frac{1}{q k_{MAX}} \leq  \frac{1}{q k_{MAX}} \leq
1447  \frac{1}{q q'} <  \frac{1}{q q'} <
1448  \frac{1}{q (k_{MAX}-q)}.  \frac{1}{q (k_{MAX}-q)}.
1449  \end{equation}  \end{equation}
1450    
1451  Let $q_{MIN}$ be the smallest denominator of any rational number  Let $q_{MIN}$ be the smallest denominator of any rational number
1452  $\in F_{k_{MAX}}$ in the interval $[l,r]$.  It is then easy to show  $\in F_{k_{MAX}}$ in the interval $[l,r]$.  It is then easy to show
1453  that for any consecutive denominators $q, q'$ which occur in  that for any consecutive denominators $q, q'$ which occur in
1454  $F_{k_{MAX}}$ in the interval $[l,r]$,  $F_{k_{MAX}}$ in the interval $[l,r]$,
1455    
1456  \begin{equation}  \begin{equation}
1457  \frac{1}{q q'} < \frac{1}{q_{MIN} \; max (q_{MIN}, k_{MAX} - q_{MIN})} .  \frac{1}{q q'} < \frac{1}{q_{MIN} \; max (q_{MIN}, k_{MAX} - q_{MIN})} .
1458  \end{equation}  \end{equation}
1459    
1460  Thus, the upper bound on the distance between consecutive terms of $F_{k_{MAX}}$  Thus, the upper bound on the distance between consecutive terms of $F_{k_{MAX}}$
1461  in an interval $[l,r]$ is tied to the minimum denominator of any  in an interval $[l,r]$ is tied to the minimum denominator of any
1462  rational number $\in F_{k_{MAX}}$ in $[l,r]$.  rational number $\in F_{k_{MAX}}$ in $[l,r]$.
1463    
1464  Note that clearly  Note that clearly
1465  $q_{MIN} \leq 1/(r-l)$, so for most practical intervals $[l,r]$,  $q_{MIN} \leq 1/(r-l)$, so for most practical intervals $[l,r]$,
1466  the search for $q_{MIN}$ would not be computationally expensive.  the search for $q_{MIN}$ would not be computationally expensive.
1467  However, applications could arise where an approximation is used  However, applications could arise where an approximation is used
1468  in an \emph{extremely} narrow interval, and having an algorithm available that  in an \emph{extremely} narrow interval, and having an algorithm available that
1469  is computationally viable for such cases is advantageous.  For example,  is computationally viable for such cases is advantageous.  For example,
1470  locating the rational number $\in F_{2^{20,000}}$ with the smallest denominator  locating the rational number $\in F_{2^{20,000}}$ with the smallest denominator
1471  in an interval of width $2^{-10,000}$ could be a serious computational  in an interval of width $2^{-10,000}$ could be a serious computational
1472  problem.  problem.
1473    
1474  To locate $q_{MIN}$ in $[l,r]$, note that at least one rational number  To locate $q_{MIN}$ in $[l,r]$, note that at least one rational number
1475  with $q_{MIN}$ as a denominator in $[l,r]$ is the best approximation  with $q_{MIN}$ as a denominator in $[l,r]$ is the best approximation
1476  of order $q_{MIN}$ to the midpoint of the interval,  of order $q_{MIN}$ to the midpoint of the interval,
1477  $(l+r)/2$.\footnote{Thanks to David M. Einstein \cite{bibref:i:davidmeinstein}  $(l+r)/2$.\footnote{Thanks to David M. Einstein \cite{bibref:i:davidmeinstein}
1478  and David Eppstein \cite{bibref:i:davideppstein}  and David Eppstein \cite{bibref:i:davideppstein}
1479  for this observation, contributed via the \texttt{sci.math} newsgroup  for this observation, contributed via the \texttt{sci.math} newsgroup
1480  \cite{bibref:n:scimathnewsgroup},  \cite{bibref:n:scimathnewsgroup},
1481  which is the linchpin of Algorithm \ref{alg:cfmindenominator}.}  which is the linchpin of Algorithm \ref{alg:cfmindenominator}.}
1482  By theorem (\cite{bibref:b:KhinchinClassic}, Theorem 15), every best approximation  By theorem (\cite{bibref:b:KhinchinClassic}, Theorem 15), every best approximation
1483  of a number is a convergent or intermediate fraction of the  of a number is a convergent or intermediate fraction of the
1484  continued fraction representation of the number.  We seek the  continued fraction representation of the number.  We seek the
1485  convergent or intermediate fraction of $(l+r)/2$ with the smallest  convergent or intermediate fraction of $(l+r)/2$ with the smallest
1486  denominator that is in the interval $[l,r]$.\footnote{Regrettably,  denominator that is in the interval $[l,r]$.\footnote{Regrettably,
1487  at this point the cart comes before the horse---the insight and  at this point the cart comes before the horse---the insight and
1488  algorithms which follow are based on continued fractions, which  algorithms which follow are based on continued fractions, which
1489  are not covered until \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},  are not covered until \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
1490  \emph{\ccfrzeroshorttitle{}}.  We apologize for the potential necessity  \emph{\ccfrzeroshorttitle{}}.  We apologize for the potential necessity
1491  of reading this work out of order.}  of reading this work out of order.}
1492    
1493  The convergents and intermediate fractions of $(l+r)/2$ are naturally  The convergents and intermediate fractions of $(l+r)/2$ are naturally
1494  arranged in order of increasing denominator.  However, it would be  arranged in order of increasing denominator.  However, it would be
1495  inefficient to test \emph{every} intermediate fraction  inefficient to test \emph{every} intermediate fraction
1496  for membership in $[l,r]$, as partial quotients $a_k$ are unlimited in  for membership in $[l,r]$, as partial quotients $a_k$ are unlimited in
1497  size and such an algorithm may not be $O(log \; k_{MAX})$.  Instead,  size and such an algorithm may not be $O(log \; k_{MAX})$.  Instead,
1498  since intermediate fractions are formed using the parameterized  since intermediate fractions are formed using the parameterized
1499  expression $(i p_k + p_{k-1})/(i q_k + q_{k-1})$,  expression $(i p_k + p_{k-1})/(i q_k + q_{k-1})$,
1500  and since intermediate fractions are ever-increasing  and since intermediate fractions are ever-increasing
1501  or ever-decreasing with respect to the parameter $i$, the  or ever-decreasing with respect to the parameter $i$, the
1502  smallest value of $i$ which will create an intermediate  smallest value of $i$ which will create an intermediate
1503  fraction potentially within $[l,r]$ can be directly  fraction potentially within $[l,r]$ can be directly
1504  calculated.  Only the intermediate fraction formed with  calculated.  Only the intermediate fraction formed with
1505  this calculated value of $i$ needs to be tested for membership in  this calculated value of $i$ needs to be tested for membership in
1506  $[l,r]$.  $[l,r]$.
1507    
1508  Let $l_N$ and $l_D$ be the numerator and denominator of $l$, and  Let $l_N$ and $l_D$ be the numerator and denominator of $l$, and
1509  let $r_N$ and $r_D$ be the numerator and denominator of $r$.  let $r_N$ and $r_D$ be the numerator and denominator of $r$.
1510  In the case of $k$ even; $s_k < l < (l+r)/2$ (otherwise $s_k$  In the case of $k$ even; $s_k < l < (l+r)/2$ (otherwise $s_k$
1511  would have been identified as $\in [l,r]$, see Algorithm  would have been identified as $\in [l,r]$, see Algorithm
1512  \ref{alg:cfmindenominator}); $s_{k+1} \geq (l+r)/2$;  \ref{alg:cfmindenominator}); $s_{k+1} \geq (l+r)/2$;
1513  with increasing $i$, $(i p_k + p_{k-1})/(i q_k + q_{k-1})$  with increasing $i$, $(i p_k + p_{k-1})/(i q_k + q_{k-1})$
1514  forms a decreasing sequence; and the inequality we seek to solve is  forms a decreasing sequence; and the inequality we seek to solve is
1515    
1516  \begin{equation}  \begin{equation}
1517  \label{eq:cfry0:schk0:ifselection01}  \label{eq:cfry0:schk0:ifselection01}
1518  \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \leq \frac{r_N}{r_D}.  \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \leq \frac{r_N}{r_D}.
1519  \end{equation}  \end{equation}
1520    
1521  Solving (\ref{eq:cfry0:schk0:ifselection01}), the smallest integral  Solving (\ref{eq:cfry0:schk0:ifselection01}), the smallest integral
1522  value of $i$ that will suffice is  value of $i$ that will suffice is
1523    
1524  \begin{equation}  \begin{equation}
1525  \label{eq:cfry0:schk0:ifselection02}  \label{eq:cfry0:schk0:ifselection02}
1526  i = \left\lceil {  i = \left\lceil {
1527  \frac{r_N q_{k-1} - r_D p_{k-1}}{r_D p_k - r_N q_k}  \frac{r_N q_{k-1} - r_D p_{k-1}}{r_D p_k - r_N q_k}
1528  } \right\rceil .  } \right\rceil .
1529  \end{equation}  \end{equation}
1530    
1531  Similarly, for $k$ odd, the sequence is increasing,  Similarly, for $k$ odd, the sequence is increasing,
1532  and the inequality and solution are  and the inequality and solution are
1533    
1534  \begin{equation}  \begin{equation}
1535  \label{eq:cfry0:schk0:ifselection03}  \label{eq:cfry0:schk0:ifselection03}
1536  \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \geq \frac{l_N}{l_D}  \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \geq \frac{l_N}{l_D}
1537  \to  \to
1538  i = \left\lceil {  i = \left\lceil {
1539  \frac{l_N q_{k-1} - l_D p_{k-1}}{l_D p_k - l_N q_k}  \frac{l_N q_{k-1} - l_D p_{k-1}}{l_D p_k - l_N q_k}
1540  } \right\rceil .  } \right\rceil .
1541  \end{equation}  \end{equation}
1542    
1543  (\ref{eq:cfry0:schk0:ifselection01}),  (\ref{eq:cfry0:schk0:ifselection01}),
1544  (\ref{eq:cfry0:schk0:ifselection02}),  (\ref{eq:cfry0:schk0:ifselection02}),
1545  and (\ref{eq:cfry0:schk0:ifselection03}) suggest the following continued fraction  and (\ref{eq:cfry0:schk0:ifselection03}) suggest the following continued fraction
1546  algorithm for finding  algorithm for finding
1547  a rational number with the smallest denominator in an  a rational number with the smallest denominator in an
1548  interval $[l,r]$.  interval $[l,r]$.
1549    
1550  \begin{vworkalgorithmstatement}\label{alg:cfmindenominator}\end{vworkalgorithmstatement}  \begin{vworkalgorithmstatement}\label{alg:cfmindenominator}\end{vworkalgorithmstatement}
1551  \begin{alglvl0}  \begin{alglvl0}
1552  \item Calculate all partial quotients $a_k$ and all convergents  \item Calculate all partial quotients $a_k$ and all convergents
1553        $s_k = p_k/q_k$ of the midpoint of the interval,        $s_k = p_k/q_k$ of the midpoint of the interval,
1554        $(l+r)/2$.        $(l+r)/2$.
1555    
1556  \item  For each convergent $s_k=p_k/q_k$, in order of increasing $k$:  \item  For each convergent $s_k=p_k/q_k$, in order of increasing $k$:
1557    
1558     \begin{alglvl1}     \begin{alglvl1}
1559    
1560     \item If $s_k = p_k/q_k \in [l,r]$, $s_k$ is a rational number with     \item If $s_k = p_k/q_k \in [l,r]$, $s_k$ is a rational number with
1561           the lowest denominator, STOP.           the lowest denominator, STOP.
1562    
1563     \item If $k$ is even,     \item If $k$ is even,
1564    
1565        \begin{alglvl2}        \begin{alglvl2}
1566    
1567        \item Calculate $i$ according to (\ref{eq:cfry0:schk0:ifselection02}).        \item Calculate $i$ according to (\ref{eq:cfry0:schk0:ifselection02}).
1568              If $i < a_{k+1}$ and the intermediate fraction              If $i < a_{k+1}$ and the intermediate fraction
1569              $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\geq$ $l$, this intermediate              $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\geq$ $l$, this intermediate
1570              fraction is              fraction is
1571              a rational number with the lowest denominator, STOP.              a rational number with the lowest denominator, STOP.
1572    
1573        \end{alglvl2}        \end{alglvl2}
1574    
1575     \item Else if $k$ is odd,     \item Else if $k$ is odd,
1576    
1577        \begin{alglvl2}        \begin{alglvl2}
1578    
1579        \item Calculate $i$ according to (\ref{eq:cfry0:schk0:ifselection03}).        \item Calculate $i$ according to (\ref{eq:cfry0:schk0:ifselection03}).
1580              If $i < a_{k+1}$ and the intermediate fraction              If $i < a_{k+1}$ and the intermediate fraction
1581              $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\leq$ $r$, this intermediate              $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\leq$ $r$, this intermediate
1582              fraction is              fraction is
1583              a rational number with the lowest denominator, STOP.              a rational number with the lowest denominator, STOP.
1584    
1585        \end{alglvl2}        \end{alglvl2}
1586    
1587     \end{alglvl1}     \end{alglvl1}
1588    
1589  \end{alglvl0}  \end{alglvl0}
1590    
1591  Algorithm \ref{alg:cfmindenominator} is approximately $O(log \; k_{MAX})$,  Algorithm \ref{alg:cfmindenominator} is approximately $O(log \; k_{MAX})$,
1592  since there are a fixed number of steps per convergent, and the maximum number  since there are a fixed number of steps per convergent, and the maximum number
1593  of convergents is $O(log \; k_{MAX})$.  Once a rational number with the smallest  of convergents is $O(log \; k_{MAX})$.  Once a rational number with the smallest
1594  denominator $q_{MIN}$ is located, (\ref{eq:cfry0:schk0:minqplacementupperbound})  denominator $q_{MIN}$ is located, (\ref{eq:cfry0:schk0:minqplacementupperbound})
1595  can be applied to bound $|r_A - r_I|$; namely,  can be applied to bound $|r_A - r_I|$; namely,
1596    
1597  \begin{equation}  \begin{equation}
1598  \label{eq:qminmaxplacementerror}  \label{eq:qminmaxplacementerror}
1599  \left| {\frac{h}{k} - r_I}  \right|  \left| {\frac{h}{k} - r_I}  \right|
1600  <  <
1601  \frac{1}{2q_{MIN} \; max(q_{MIN}, k_{MAX} - q_{MIN})} .  \frac{1}{2q_{MIN} \; max(q_{MIN}, k_{MAX} - q_{MIN})} .
1602  \end{equation}  \end{equation}
1603    
1604    
1605  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1606  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1607  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1608  \subsubsection[Case II:  $h_{MAX}/k_{MAX} < r_I < 1$]  \subsubsection[Case II:  $h_{MAX}/k_{MAX} < r_I < 1$]
1609                {Case II:  \mbox{\boldmath $h_{MAX}/k_{MAX} < r_I < 1$}}                {Case II:  \mbox{\boldmath $h_{MAX}/k_{MAX} < r_I < 1$}}
1610    
1611  If $h_{MAX}/k_{MAX} < r_I < 1$, a graphical argument  If $h_{MAX}/k_{MAX} < r_I < 1$, a graphical argument
1612  (Figure \ref{fig:cfry0:schk0:caseii}) can be used  (Figure \ref{fig:cfry0:schk0:caseii}) can be used
1613  to more tightly bound the maximum distance between terms of  to more tightly bound the maximum distance between terms of
1614  $F_{k_{MAX}, \overline{h_{MAX}}}$.  $F_{k_{MAX}, \overline{h_{MAX}}}$.
1615    
1616  \begin{figure}  \begin{figure}
1617  \centering  \centering
1618  \includegraphics[height=2.0in]{c_fry0/errcase2.eps}  \includegraphics[height=2.0in]{c_fry0/errcase2.eps}
1619  \caption{Graphical Interpretation Of Case II:  $h_{MAX}/k_{MAX} < r_I < 1$}  \caption{Graphical Interpretation Of Case II:  $h_{MAX}/k_{MAX} < r_I < 1$}
1620  \label{fig:cfry0:schk0:caseii}  \label{fig:cfry0:schk0:caseii}
1621  \end{figure}  \end{figure}
1622    
1623  In this case,  a formable term at or to the left\footnote{To the left on the  In this case,  a formable term at or to the left\footnote{To the left on the
1624  number line, but to the right in Figure \ref{fig:cfry0:schk0:caseii}.}  number line, but to the right in Figure \ref{fig:cfry0:schk0:caseii}.}
1625  of $r_I$ is represented by the point $(\lfloor h_{MAX}/r_I \rfloor + 1, h_{MAX} )$  of $r_I$ is represented by the point $(\lfloor h_{MAX}/r_I \rfloor + 1, h_{MAX} )$
1626  in the integer lattice,  in the integer lattice,
1627  and a formable term at or to the right of $r_I$ is  and a formable term at or to the right of $r_I$ is
1628  represented by the point $(\lfloor h_{MAX}/r_I \rfloor, h_{MAX} )$  represented by the point $(\lfloor h_{MAX}/r_I \rfloor, h_{MAX} )$
1629  in the integer lattice.  Thus, the maximum distance between  in the integer lattice.  Thus, the maximum distance between
1630  neighboring terms in $F_{k_{MAX}, \overline{h_{MAX}}}$  neighboring terms in $F_{k_{MAX}, \overline{h_{MAX}}}$
1631  is given by the difference of these two terms,  is given by the difference of these two terms,
1632    
1633  \begin{equation}  \begin{equation}
1634  \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}  \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}
1635  -  -
1636  \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor + 1}  \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor + 1}
1637  =  =
1638  \frac{h_{MAX}}{{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2  \frac{h_{MAX}}{{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2
1639  + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor},  + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor},
1640  \end{equation}  \end{equation}
1641    
1642  and the maximum distance from $r_I$ to a neighboring term is  and the maximum distance from $r_I$ to a neighboring term is
1643  given by  given by
1644    
1645  \begin{equation}  \begin{equation}
1646  \label{eq:cfry0:schk0:caseiimaxplacementerror}  \label{eq:cfry0:schk0:caseiimaxplacementerror}
1647  \left|  \left|
1648  \frac{h}{k} - r_I  \frac{h}{k} - r_I
1649  \right|  \right|
1650  \leq  \leq
1651  \frac{h_{MAX}}{2 \left( { {\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2  \frac{h_{MAX}}{2 \left( { {\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2
1652  + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor } \right) }.  + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor } \right) }.
1653  \end{equation}  \end{equation}
1654    
1655  Note that Case II will exist only if $h_{MAX}/k_{MAX} < 1$.  Note that Case II will exist only if $h_{MAX}/k_{MAX} < 1$.
1656    
1657    
1658  \subsubsection[Case III:  $1 < h_{MAX}/k_{MAX} < r_I$]  \subsubsection[Case III:  $1 < h_{MAX}/k_{MAX} < r_I$]
1659                {Case III:  \mbox{\boldmath $1 < h_{MAX}/k_{MAX} < r_I$}}                {Case III:  \mbox{\boldmath $1 < h_{MAX}/k_{MAX} < r_I$}}
1660    
1661  It can be established graphically, using the coordinate system of  It can be established graphically, using the coordinate system of
1662  Figure \ref{fig:cfry0:ili0:00}, Figure \ref{fig:cfry0:chk0:01},  Figure \ref{fig:cfry0:ili0:00}, Figure \ref{fig:cfry0:chk0:01},
1663  or Figure \ref{fig:cfry0:schk0:threecases},  or Figure \ref{fig:cfry0:schk0:threecases},
1664  that the line $h=r_I k$ intercepts the  that the line $h=r_I k$ intercepts the
1665  line $h=h_{MAX}$ at the point $(h_{MAX}/r_I, h_{MAX})$.  It is clear  line $h=h_{MAX}$ at the point $(h_{MAX}/r_I, h_{MAX})$.  It is clear
1666  from a graphical argument that all of the terms of the Farey series  from a graphical argument that all of the terms of the Farey series
1667  of order $\lfloor h_{MAX}/r_I \rfloor$ are available as neighbors  of order $\lfloor h_{MAX}/r_I \rfloor$ are available as neighbors
1668  of $r_I$.  Therefore,  of $r_I$.  Therefore,
1669    
1670  \begin{equation}  \begin{equation}
1671  \label{eq:cfry0:schk0:caseiiiplacementerror}  \label{eq:cfry0:schk0:caseiiiplacementerror}
1672  \left|  \left|
1673  \frac{h}{k} - r_I  \frac{h}{k} - r_I
1674  \right|  \right|
1675  \leq  \leq
1676  \frac{1}{2 \left\lfloor \frac{h_{MAX}}{r_I} \right\rfloor}.  \frac{1}{2 \left\lfloor \frac{h_{MAX}}{r_I} \right\rfloor}.
1677  \end{equation}  \end{equation}
1678    
1679    
1680  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1681  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1682  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1683  \section{Acknowledgements}  \section{Acknowledgements}
1684  %Section tag: ACK0  %Section tag: ACK0
1685    
1686  This chapter is the result of work on inexpensive microcontroller  This chapter is the result of work on inexpensive microcontroller
1687  arithmetic (and a paper) undertaken in 2000.  arithmetic (and a paper) undertaken in 2000.
1688  We would like to gratefully acknowledge the assistance  We would like to gratefully acknowledge the assistance
1689  of  of
1690  \index{Bachelis, Greg}      Greg Bachelis     \cite{bibref:i:gregbachelis},  \index{Bachelis, Greg}      Greg Bachelis     \cite{bibref:i:gregbachelis},
1691  \index{Berman, Robert}      Robert Berman     \cite{bibref:i:robertberman},  \index{Berman, Robert}      Robert Berman     \cite{bibref:i:robertberman},
1692  \index{Lin, Feng}           Feng Lin          \cite{bibref:i:fenglin},  \index{Lin, Feng}           Feng Lin          \cite{bibref:i:fenglin},
1693  \index{Sahinidis, Nick}     Nick Sahinidis    \cite{bibref:i:nicksahinidis},  \index{Sahinidis, Nick}     Nick Sahinidis    \cite{bibref:i:nicksahinidis},
1694  \index{Van Tuyl, Adam}      Adam Van Tuyl     \cite{bibref:i:adamvantuyl},  \index{Van Tuyl, Adam}      Adam Van Tuyl     \cite{bibref:i:adamvantuyl},
1695  \index{Schweiger, Carl}     Carl Schweiger    \cite{bibref:i:carlschweiger},  \index{Schweiger, Carl}     Carl Schweiger    \cite{bibref:i:carlschweiger},
1696  \index{Tindell, Ken}        Ken Tindell       \cite{bibref:i:kentindell},  \index{Tindell, Ken}        Ken Tindell       \cite{bibref:i:kentindell},
1697  \index{Vestal, Steve}       Steve Vestal      \cite{bibref:i:stevevestal},  \index{Vestal, Steve}       Steve Vestal      \cite{bibref:i:stevevestal},
1698  \index{Whitinger, Bob}      Bob Whitinger     \cite{bibref:i:bobwhitinger},  \index{Whitinger, Bob}      Bob Whitinger     \cite{bibref:i:bobwhitinger},
1699  and  and
1700  \index{Stewart, David B.}   David B. Stewart   \cite{bibref:i:davidbstewart}  \index{Stewart, David B.}   David B. Stewart   \cite{bibref:i:davidbstewart}
1701  in finding the areas of  in finding the areas of
1702  mathematics relevant to the rational number selection  mathematics relevant to the rational number selection
1703  problem.  We would also like to  problem.  We would also like to
1704  thank  thank
1705  \index{Bengtsson, Johan}    Johan Bengtsson    \cite{bibref:i:johanbengtsson},  \index{Bengtsson, Johan}    Johan Bengtsson    \cite{bibref:i:johanbengtsson},
1706  \index{Burke, Michael J.}   Michael J. Burke   \cite{bibref:i:michaeljburke},    \index{Burke, Michael J.}   Michael J. Burke   \cite{bibref:i:michaeljburke},  
1707  \index{Endicott, Mark}      Mark Endicott      \cite{bibref:i:markendicott},  \index{Endicott, Mark}      Mark Endicott      \cite{bibref:i:markendicott},
1708  \index{Eppstein, David}     David Eppstein     \cite{bibref:i:davideppstein},  \index{Eppstein, David}     David Eppstein     \cite{bibref:i:davideppstein},
1709  \index{Munteanu, Mircea}    Mircea Munteanu    \cite{bibref:i:mirceamunteanu},  \index{Munteanu, Mircea}    Mircea Munteanu    \cite{bibref:i:mirceamunteanu},
1710  \index{Gibson, Adam}        Adam Gibson        \cite{bibref:i:adamgibson},  \index{Gibson, Adam}        Adam Gibson        \cite{bibref:i:adamgibson},
1711  and \index{Virgil}          Virgil             \cite{bibref:i:virgil}  and \index{Virgil}          Virgil             \cite{bibref:i:virgil}
1712  (of the \index{sci.math.num-analysis@\texttt{sci.math.num-analysis} newsgroup}%  (of the \index{sci.math.num-analysis@\texttt{sci.math.num-analysis} newsgroup}%
1713  \texttt{sci.math.num-analysis} newsgroup  \texttt{sci.math.num-analysis} newsgroup
1714  \cite{bibref:n:scimathnumanalysis})  \cite{bibref:n:scimathnumanalysis})
1715  for insight into this problem;  for insight into this problem;
1716  \index{Stallings, Cliff}    Cliff Stallings    \cite{bibref:i:cliffstallings}  \index{Stallings, Cliff}    Cliff Stallings    \cite{bibref:i:cliffstallings}
1717  and  and
1718  \index{Kakos, Robert}       Robert Kakos       \cite{bibref:i:robertkakos}  \index{Kakos, Robert}       Robert Kakos       \cite{bibref:i:robertkakos}
1719  for support from Wayne State  for support from Wayne State
1720  University's College Of Engineering;  University's College Of Engineering;
1721  \index{Groen, Paulette}     Paulette Groen     \cite{bibref:i:paulettegroen}  \index{Groen, Paulette}     Paulette Groen     \cite{bibref:i:paulettegroen}
1722  and  and
1723  \index{Smith, Paula}        Paula Smith        \cite{bibref:i:paulasmith}  \index{Smith, Paula}        Paula Smith        \cite{bibref:i:paulasmith}
1724  for support from \index{Visteon}Visteon;  for support from \index{Visteon}Visteon;
1725  \index{Crosby, Bob}         Bob Crosby         \cite{bibref:i:bobcrosby}  \index{Crosby, Bob}         Bob Crosby         \cite{bibref:i:bobcrosby}
1726  for support  for support
1727  from \index{Texas Instruments}Texas Instruments;  from \index{Texas Instruments}Texas Instruments;
1728  \index{Zauner, Klaus-Peter} Klaus-Peter Zauner  \cite{bibref:i:klauspeterzauner},  \index{Zauner, Klaus-Peter} Klaus-Peter Zauner  \cite{bibref:i:klauspeterzauner},
1729  \index{Blome, Andrea}       Andrea Blome        \cite{bibref:i:andreablome},  \index{Blome, Andrea}       Andrea Blome        \cite{bibref:i:andreablome},
1730  \index{Smith, Una}          Una Smith           \cite{bibref:i:unasmith},  \index{Smith, Una}          Una Smith           \cite{bibref:i:unasmith},
1731  \index{Tinnefeld, Karsten}  Karsten Tinnefeld   \cite{bibref:i:karstentinnefeld},  \index{Tinnefeld, Karsten}  Karsten Tinnefeld   \cite{bibref:i:karstentinnefeld},
1732  and  and
1733  \index{Franke, Axel}        Axel Franke         \cite{bibref:i:axelfranke}  \index{Franke, Axel}        Axel Franke         \cite{bibref:i:axelfranke}
1734  for other tool  for other tool
1735  and logistical support; and the management  and logistical support; and the management
1736  team at Visteon for allowing us to pursue this  team at Visteon for allowing us to pursue this
1737  effort in the workplace.  effort in the workplace.
1738    
1739    
1740  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1741  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1742  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1743  \section{Exercises}  \section{Exercises}
1744  %Section tag: EXE0  %Section tag: EXE0
1745    
1746  \begin{vworkexercisestatement}  \begin{vworkexercisestatement}
1747  \label{exe:cfry0:sexe0:01}  \label{exe:cfry0:sexe0:01}
1748  Prove that Theorem \ref{thm:cfry0:spfs:01}  Prove that Theorem \ref{thm:cfry0:spfs:01}
1749  holds in the degenerate cases where $h=1$ and where $k=1$.  holds in the degenerate cases where $h=1$ and where $k=1$.
1750  \end{vworkexercisestatement}  \end{vworkexercisestatement}
1751  \vworkexercisefooter{}  \vworkexercisefooter{}
1752    
1753  \begin{vworkexercisestatement}  \begin{vworkexercisestatement}
1754  \label{exe:cfry0:sexe0:02}  \label{exe:cfry0:sexe0:02}
1755  Prove that Theorem \ref{thm:cfry0:spfs:01} holds $\forall i \in \vworkintset$  Prove that Theorem \ref{thm:cfry0:spfs:01} holds $\forall i \in \vworkintset$
1756  (rather than $\forall i \in \vworkintsetnonneg$) using  (rather than $\forall i \in \vworkintsetnonneg$) using
1757  the slightly amended notion of reducibility that $h/k$ is irreducible iff  the slightly amended notion of reducibility that $h/k$ is irreducible iff
1758  $\lfloor h \rfloor / k$ is irreducible.  $\lfloor h \rfloor / k$ is irreducible.
1759  \end{vworkexercisestatement}  \end{vworkexercisestatement}
1760  \vworkexercisefooter{}  \vworkexercisefooter{}
1761    
1762  \begin{vworkexercisestatement}  \begin{vworkexercisestatement}
1763  In Section \ref{cfry0:sgfs0} and Algorithm \ref{alg:cfry0:sgfs0:02}  In Section \ref{cfry0:sgfs0} and Algorithm \ref{alg:cfry0:sgfs0:02}
1764  it is stated that for $i \in \vworkintsetnonneg$,  it is stated that for $i \in \vworkintsetnonneg$,
1765  $(iN-1)/N$, $i/1$, and $(iN+1)/N$ are consecutive terms in the Farey series  $(iN-1)/N$, $i/1$, and $(iN+1)/N$ are consecutive terms in the Farey series
1766  or order $N$, $F_N$.  Prove that $(iN-1)/N$ and $(iN+1)/N$ are irreducible,  or order $N$, $F_N$.  Prove that $(iN-1)/N$ and $(iN+1)/N$ are irreducible,
1767  and the left and right Farey neighbors to $i/1$.  and the left and right Farey neighbors to $i/1$.
1768  \end{vworkexercisestatement}  \end{vworkexercisestatement}
1769  \vworkexercisefooter{}  \vworkexercisefooter{}
1770    
1771  \begin{vworkexercisestatement}  \begin{vworkexercisestatement}
1772  Prove that in $F_N$ the maximum distance between terms $1/N$ can occur  Prove that in $F_N$ the maximum distance between terms $1/N$ can occur
1773  only adjacent to an integer.  only adjacent to an integer.
1774  \end{vworkexercisestatement}  \end{vworkexercisestatement}
1775  \vworkexercisefooter{}  \vworkexercisefooter{}
1776    
1777    
1778  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1779    
1780  \noindent\begin{figure}[!b]  \noindent\begin{figure}[!b]
1781  \noindent\rule[-0.25in]{\textwidth}{1pt}  \noindent\rule[-0.25in]{\textwidth}{1pt}
1782  \begin{tiny}  \begin{tiny}
1783  \begin{verbatim}  \begin{verbatim}
1784  $RCSfile: c_fry0.tex,v $  $RCSfile: c_fry0.tex,v $
1785  $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_fry0/c_fry0.tex,v $  $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_fry0/c_fry0.tex,v $
1786  $Revision: 1.7 $  $Revision: 1.7 $
1787  $Author: dtashley $  $Author: dtashley $
1788  $Date: 2004/03/17 01:37:52 $  $Date: 2004/03/17 01:37:52 $
1789  \end{verbatim}  \end{verbatim}
1790  \end{tiny}  \end{tiny}
1791  \noindent\rule[0.25in]{\textwidth}{1pt}  \noindent\rule[0.25in]{\textwidth}{1pt}
1792  \end{figure}  \end{figure}
1793    
1794  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1795  % $Log: c_fry0.tex,v $  % $Log: c_fry0.tex,v $
1796  % Revision 1.7  2004/03/17 01:37:52  dtashley  % Revision 1.7  2004/03/17 01:37:52  dtashley
1797  % Edits.  % Edits.
1798  %  %
1799  % Revision 1.6  2004/03/12 11:20:03  dtashley  % Revision 1.6  2004/03/12 11:20:03  dtashley
1800  % Erroneous math mode command commented out to silence LaTeX warning.  % Erroneous math mode command commented out to silence LaTeX warning.
1801  %  %
1802  % Revision 1.5  2003/11/30 01:22:17  dtashley  % Revision 1.5  2003/11/30 01:22:17  dtashley
1803  % References changed to follow standard format.  % References changed to follow standard format.
1804  %  %
1805  % Revision 1.4  2002/08/22 00:33:33  dtashley  % Revision 1.4  2002/08/22 00:33:33  dtashley
1806  % Have made aesthetic changes in CFRY0 and CCFR0.  Checking in all before  % Have made aesthetic changes in CFRY0 and CCFR0.  Checking in all before
1807  % rebuild of book.  % rebuild of book.
1808  %  %
1809  % Revision 1.3  2001/07/11 18:42:05  dtashley  % Revision 1.3  2001/07/11 18:42:05  dtashley
1810  % Safety check-in.  Beginning work now on using GNU GMP in the tool set  % Safety check-in.  Beginning work now on using GNU GMP in the tool set
1811  % and must cease work on book temporarily.  % and must cease work on book temporarily.
1812  %  %
1813  % Revision 1.2  2001/07/01 19:37:42  dtashley  % Revision 1.2  2001/07/01 19:37:42  dtashley
1814  % Move out of binary mode for use with CVS.  % Move out of binary mode for use with CVS.
1815  %  %
1816  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1817  % $History: c_fry0.tex $  % $History: c_fry0.tex $
1818  %  %
1819  % *****************  Version 18  *****************  % *****************  Version 18  *****************
1820  % User: Dashley1     Date: 3/07/01    Time: 12:17a  % User: Dashley1     Date: 3/07/01    Time: 12:17a
1821  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1822  % Edits.  % Edits.
1823  %  %
1824  % *****************  Version 17  *****************  % *****************  Version 17  *****************
1825  % User: Dashley1     Date: 2/10/01    Time: 2:02a  % User: Dashley1     Date: 2/10/01    Time: 2:02a
1826  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1827  % Completion of Farey series chapter.  % Completion of Farey series chapter.
1828  %  %
1829  % *****************  Version 16  *****************  % *****************  Version 16  *****************
1830  % User: Dashley1     Date: 1/31/01    Time: 4:20p  % User: Dashley1     Date: 1/31/01    Time: 4:20p
1831  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1832  % Edits.  % Edits.
1833  %  %
1834  % *****************  Version 15  *****************  % *****************  Version 15  *****************
1835  % User: Dashley1     Date: 12/22/00   Time: 12:55a  % User: Dashley1     Date: 12/22/00   Time: 12:55a
1836  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1837  % Tcl automated method of build refined.  % Tcl automated method of build refined.
1838  %  %
1839  % *****************  Version 14  *****************  % *****************  Version 14  *****************
1840  % User: David T. Ashley Date: 8/19/00    Time: 5:03p  % User: David T. Ashley Date: 8/19/00    Time: 5:03p
1841  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1842  % Edits.  % Edits.
1843  %  %
1844  % *****************  Version 13  *****************  % *****************  Version 13  *****************
1845  % User: David T. Ashley Date: 8/13/00    Time: 3:17p  % User: David T. Ashley Date: 8/13/00    Time: 3:17p
1846  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1847  % Edits.  % Edits.
1848  %  %
1849  % *****************  Version 12  *****************  % *****************  Version 12  *****************
1850  % User: David T. Ashley Date: 8/12/00    Time: 9:45p  % User: David T. Ashley Date: 8/12/00    Time: 9:45p
1851  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1852  % Edits.  % Edits.
1853  %  %
1854  % *****************  Version 11  *****************  % *****************  Version 11  *****************
1855  % User: David T. Ashley Date: 8/06/00    Time: 8:50a  % User: David T. Ashley Date: 8/06/00    Time: 8:50a
1856  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1857  % Work on Prime Number and Farey Series chapters.  % Work on Prime Number and Farey Series chapters.
1858  %  %
1859  % *****************  Version 10  *****************  % *****************  Version 10  *****************
1860  % User: David T. Ashley Date: 8/05/00    Time: 1:31a  % User: David T. Ashley Date: 8/05/00    Time: 1:31a
1861  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1862  % Minor edit--test check-in.  % Minor edit--test check-in.
1863  %  %
1864  % *****************  Version 9  *****************  % *****************  Version 9  *****************
1865  % User: David T. Ashley Date: 8/02/00    Time: 11:21p  % User: David T. Ashley Date: 8/02/00    Time: 11:21p
1866  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1867  % Edits of Farey series chapter.  % Edits of Farey series chapter.
1868  %  %
1869  % *****************  Version 8  *****************  % *****************  Version 8  *****************
1870  % User: David T. Ashley Date: 7/29/00    Time: 11:50p  % User: David T. Ashley Date: 7/29/00    Time: 11:50p
1871  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1872  % Edits, addition of solutions manual volume.  % Edits, addition of solutions manual volume.
1873  %  %
1874  % *****************  Version 7  *****************  % *****************  Version 7  *****************
1875  % User: David T. Ashley Date: 7/24/00    Time: 6:59p  % User: David T. Ashley Date: 7/24/00    Time: 6:59p
1876  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1877  % Add'l work on Farey series chapter.  % Add'l work on Farey series chapter.
1878  %  %
1879  % *****************  Version 6  *****************  % *****************  Version 6  *****************
1880  % User: David T. Ashley Date: 7/22/00    Time: 3:24p  % User: David T. Ashley Date: 7/22/00    Time: 3:24p
1881  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1882  % Addition of opening quote from Hardy.  May want to eventually change  % Addition of opening quote from Hardy.  May want to eventually change
1883  % the quote to something less negative.  % the quote to something less negative.
1884  %  %
1885  % *****************  Version 5  *****************  % *****************  Version 5  *****************
1886  % User: David T. Ashley Date: 7/16/00    Time: 2:10p  % User: David T. Ashley Date: 7/16/00    Time: 2:10p
1887  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1888  % Edits.  % Edits.
1889  %  %
1890  % *****************  Version 4  *****************  % *****************  Version 4  *****************
1891  % User: David T. Ashley Date: 7/15/00    Time: 1:30p  % User: David T. Ashley Date: 7/15/00    Time: 1:30p
1892  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1893  % Edits of Farey series chapter.  % Edits of Farey series chapter.
1894  %  %
1895  % *****************  Version 3  *****************  % *****************  Version 3  *****************
1896  % User: Dashley1     Date: 7/13/00    Time: 7:14p  % User: Dashley1     Date: 7/13/00    Time: 7:14p
1897  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1898  % Edits for introduction to Farey series.  % Edits for introduction to Farey series.
1899  %  %
1900  % *****************  Version 2  *****************  % *****************  Version 2  *****************
1901  % User: David T. Ashley Date: 7/09/00    Time: 11:16p  % User: David T. Ashley Date: 7/09/00    Time: 11:16p
1902  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1903  % Addition of new chapters, enhancements to preface.  % Addition of new chapters, enhancements to preface.
1904  %  %
1905  % *****************  Version 1  *****************  % *****************  Version 1  *****************
1906  % User: David T. Ashley Date: 7/09/00    Time: 9:26p  % User: David T. Ashley Date: 7/09/00    Time: 9:26p
1907  % Created in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series  % Created in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series
1908  % Initial check-in.  % Initial check-in.
1909  %  %
1910  %End of file C_FRY0.TEX  %End of file C_FRY0.TEX

Legend:
Removed from v.4  
changed lines
  Added in v.140

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25