PlanetMath: Stern-Brocot tree

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (197)
Orphanage
Unclass'd
Unproven (498)
Corrections (22)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Stern-Brocot tree

(Definition)

If we start with irreducible fractions representing zero and infinity,

$\displaystyle \frac{0}{1}, \frac{1}{0},$

and then between adjacent fractions $\frac{m}{n}$ and $\frac{m'}{n'}$ we insert fraction $\frac{m+m'}{n+n'}$ , then we obtain

$\displaystyle \frac{0}{1}, \frac{1}{1}, \frac{1}{0}.$

Repeating the process, we get

$\displaystyle \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0},$

and then

$\displaystyle \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},$

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.

$\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}$

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

$\displaystyle L=\begin{bmatrix}1&1\\ 0&1 \end{bmatrix},\qquad R=\begin{bmatrix}1&0\\ 1&1 \end{bmatrix},$

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

$\displaystyle LRL=\begin{bmatrix}1&1\\ 0&1 \end{bmatrix}\begin{bmatrix}1&0\\ 1&... ...}\begin{bmatrix}1&1\\ 0&1 \end{bmatrix}=\begin{bmatrix}2&3\\ 1&2 \end{bmatrix},$

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 $\langle a_0;a_1,a_2,\dotsc\rangle$ corresponds to fraction whose path from the top is $R^{a_0}L^{a_1}R^{a_2}\dotsb$ with the last element removed. For example,

$\displaystyle \frac{5}{3}$	$\displaystyle =1+\frac{1}{1+\frac{1}{2}}=\langle 1;1,2\rangle=R^1L^1R^{2-1}=RLR,$
$\displaystyle \frac{4}{11}$	$\displaystyle =0+\frac{1}{2+\frac{1}{1+\frac{1}{3}}}=\langle 0;2,1,3\rangle=R^0L^2R^1L^{3-1}=LLRLL.$

The irrational numbers correspond to the infinite paths in the Stern-Brocot tree. For example, the golden mean $\phi=\langle 1;1,1,1,\dotsc\rangle$ corresponds to the infinite path $RLRLR\dotsb$ . In particular, the denominator of the fraction corresponding to the string $RLR\dotsb$ of length

is the

'th Fibonacci number.

References

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)

See Also: Farey sequence, continued fraction

Keywords:

mediant

Log in to rate this entry.
(view current ratings)

Cross-references: Fibonacci number, length, string, mean, infinite, irrational numbers, continued fractions, matrix product, parent, denominators, numerators, product, matrices, path, tree, Moritz Stern, iteration, adjacent fractions, infinity, fractions, irreducible
There are 2 references 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 5173 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

None.[ View all 3 ]

Discussion

forum policy

No messages.

Interact