|
|
|
|
Stern-Brocot tree
|
(Definition)
|
|
|
If we start with irreducible fractions representing zero and infinity, \begin{equation*} \frac{0}{1}, \frac{1}{0}, \end{equation*}and then between adjacent fractions $\frac{m}{n}$ and $\frac{m'}{n'}$ we insert fraction $\frac{m+m'}{n+n'}$ , then we obtain \begin{equation*} \frac{0}{1}, \frac{1}{1}, \frac{1}{0}. \end{equation*}Repeating the process, we get \begin{equation*} \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0},
\end{equation*}and then \begin{equation*} \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0}, \end{equation*}and so forth. It can be proven that every irreducible fraction appears at some iteration and no fraction ever appears twice [1]. The process can be represented graphically by means of so-called Stern-Brocot tree, named after its discoverers, Moritz Stern and Achille Brocot.
If we specify position of a fraction in the tree as a path consisting of L(eft) an R(ight) moves along the tree starting from the top (fraction $\frac{1}{1}$ ), and also define matrices \begin{equation*} L=\begin{bmatrix} 1&1\\0&1 \end{bmatrix},\qquad R=\begin{bmatrix} 1&0\\1&1 \end{bmatrix}, \end{equation*}then product of the matrices corresponding to the path is matrix $\left[\begin{smallmatrix}n&n'\\m&m'\end{smallmatrix}\right]$ whose entries are numerators and denominators of parent fractions. For example, the path leading to fraction $\frac{3}{5}$ is LRL. The corresponding matrix product is \begin{equation*} LRL=\begin{bmatrix} 1&1\\0&1 \end{bmatrix}\begin{bmatrix} 1&0\\1&1 \end{bmatrix}\begin{bmatrix} 1&1\\0&1 \end{bmatrix}=\begin{bmatrix} 2&3\\1&2 \end{bmatrix}, \end{equation*}and the parents of $\frac{3}{5}$ are $\frac{1}{2}$ and $\frac{2}{3}$ .
Continued fractions and Stern-Brocot tree are closely related. A continued fraction
 corresponds to fraction whose path from the top is
 with the last element removed. For example,
The irrational numbers correspond to the infinite paths in the Stern-Brocot tree. For example, the golden mean
 corresponds to the infinite path
 . In particular, the denominator of the fraction corresponding to the string  of length $n$ is the $n$ 'th Fibonacci number.
- 1
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.
Concrete Mathematics.
Addison-Wesley, 1998.
Zbl 0836.00001.
|
"Stern-Brocot tree" is owned by bbukh.
|
|
(view preamble | get metadata)
Cross-references: Fibonacci number, length, string, mean, infinite, irrational numbers, element, continued fractions, matrix product, parent, denominators, numerators, product, matrices, path, tree, Moritz Stern, iteration, adjacent fractions, infinity, fractions, irreducible
There is 1 reference to this entry.
This is version 6 of Stern-Brocot tree, born on 2003-06-14, modified 2006-07-01.
Object id is 4361, canonical name is SternBrocotTree.
Accessed 6701 times total.
Classification:
| AMS MSC: | 11A55 (Number theory :: Elementary number theory :: Continued fractions) | | | 11A05 (Number theory :: Elementary number theory :: Multiplicative structure; Euclidean algorithm; greatest common divisors) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle \begin{xy}*!C\xybox{\xymatrix@C=0.4em{ \frac{0}{1}\ar@{.}[d] & & ... ...ar@{.}+<0em,-5ex>\ar@{-}+<0.5em,-5ex>&\frac{1}{0}\ar@{.}+<0em,-5ex> }} \end{xy}$](http://images.planetmath.org:8080/cache/objects/4361/js/img1.png "$\displaystyle \begin{xy}*!C\xybox{\xymatrix@C=0.4em{ \frac{0}{1}\ar@{.}[d] & & ... ...ar@{.}+<0em,-5ex>\ar@{-}+<0.5em,-5ex>&\frac{1}{0}\ar@{.}+<0em,-5ex> }} \end{xy}$")
