Trees, Teeth, and Time: the mathematics of clock making
Trees, Teeth, and Time: the mathematics of clock making
Introduction
Mathematics has long played an important role in timekeeping as
cultures created calendars to express their unique values. In this
article, we will look at an interesting mathematical construction, the
SternBrocot tree, that was created, in part, to help build
timepieces. As we'll see, the tree gives an
exceptionally elegant way to enumerate the positive rational numbers
and is a suprisingly useful tool for constructing clocks.
Moritz Stern, a German mathematician who succeeded Gauss at
the University of Göttingen first described the tree and
explained its relation to other topics in number theory in a
mathematics paper in 1858.
Stern's codiscoverer, Achille Brocot was born into an esteemed
family of clockmakers in 1817, and later held several patents on
his work. Our focus here, however, will be on his discovery of the
SternBrocot tree and its use in clock making.
Construction of SternBrocot tree
To construct the SternBrocot tree, we will define the
mediant of two rational numbers to be
The mediant always lies between the two rational numbers that
define it. To see this, we may identify a rational number
p/q with the point in the plane
(q, p).
With this convention, the slope of the line through the origin and
the point (q, p) is the rational number
p/q.
(Strictly speaking, the mediant depends not on rational numbers,
but rather on representations of rational numbers. For example, 2/3 =
4/6 but 2/3 5/7 is not the same as 4/6
5/7. We will typically represent
rational numbers as fractions p/q in simplest
termsthat is, where p and q have no common
factorsso that this should cause no confusion. The same point
applies to the definition of the point (q, p)
associated to a rational number.)
Notice that the operation of forming the mediant of
two rational numbers corresponds to vector addition.
This shows that the slope defined by the mediant lies between the
slopes defined by the two original rational numbers, which implies
that the mediant lies between the two rational numbers.
We will now construct the SternBrocot tree in steps beginning
with the two fractions 0/1 and 1/0. You may worry that 1/0 does not
define a rational number, but, as we'll see, it will be convenient for
us to think about this as representing infinity.
We continue the construction forming the next level by inserting
the mediant of any two consecutive rational numbers that are already
in the tree.
Notice that we have constructed a binary tree: when a rational
number r appears, it is the mediant of two rationals, one of
which is r's immediate predecessor, the other is
r's immediate successor. The mediant of r and its
predecessor is r's left child, while the mediant of
r and its successor is its right child.
A rational number appears in the tree only one time. This is
because the rationals added to the tree are always between
consecutive numbers that are already in the tree.
The rational numbers always appear in simplest
form. We'll explain this momentarily after introducing a useful
tool. Remembering our identification of rational numbers with points
in the plane, we see that two rationals define a parallelogram, as
shaded below.
It is wellknown that the area of this
parallelogram may found by
A(p/q, p'/q')
= qp'  q'p.
This quantity has some important features that are easy to check.
 If r_{1} and r_{2} are
rationals, then
A(r_{1},
r_{2})
is an integer.
 A(r, r) = 0.
 A satisfies an additive property:
A(r_{1}
r_{2},
r_{3}) = A(r_{1},
r_{3}) + A(r_{2},
r_{3})

A( sp / sq,
r_{2}) =
s A(p/q,
r_{2}).
We now claim that, if
r_{1} and r_{2} are consecutive
rational numbers at any step of the construction of the SternBrocot
tree, then
A(r_{1}, r_{2}) = 1.
It is certainly true at the beginning step, since we begin with
0/1 and 1/0.
Now suppose that it is true for r_{1} and
r_{2}, consecutive rationals at some step of the
construction. To form the next step, we add the mediant of
r_{1} and
r_{2} between them.
We may then check that
In the same way, we see that
We can now explain why rationals that appear in the tree are
expressed in simplest termsthat is, as ratios p/q
where p and q have no common factors. Suppose
instead that the rational
sp / sq
appears in the tree
with s > 1. Suppose that r is the rational
following sp / sq when it appears in the tree.
Then
A( sp / sq,
r) =
s A(p/q,
r) = 1. This is impossible if s > 1, which
implies that the
rationals appear in simplest terms.
Sliding down the tree
Every positive rational number appears in the SternBrocot
tree. As we come to understand this fact, we'll also see how to
navigate in the tree. Let's begin by asking, how, for example, we
would find 4/7. The construction begins with the fractions
0/1, 1/1, 1/0
We will begin at the fraction 1/1.
Since 0/1 < 4/7 < 1/1, we will
move left to the mediant of 0/1 and 1/1, which is 1/2. It will be
convenient to denote this move by L since it is a move to the
left child of 1/1.
Now we have 1/2 < 4/7 < 1/1 so we will move to 2/3, the right
child of 1/2. We denote this move as R so that our path from
1/1 is described by LR.
In the same way, we have 1/2 < 4/7 < 2/3 so we will move left to 3/5.
Our path from 1/1 is now LRL.
With one more step to the left, we arrive at 4/7, which we may
represent as LRLL.
How does this show that every positive rational appears in
the tree? Suppose that we are looking for the rational r.
At every step, r is bracketed by two rationals
p/q and p'/q'. If r is
equal to mediant of p/q and p'/q',
then we have found r. If not, move from the mediant to the
left if r is less than the mediant and right otherwise.
Suppose that we never find r so that this process
continues indefinitely. As this happens, the denominators of the
rationals p/q and p'/q' that
bracket r grow arbitrarily large.
Let's think about this geometrically. Since q and
q' grow arbitrarily large, the points (q,
p) and (q',
p') are eventually to the right of r. And since
p/q < r < p'/q', it follows that
r lies in the parallelogram as shown below.
Remember that the area of the shaded parallelogram above is
A(p/q, p'/q') = 1.
Consider now the area of the parallelogram defined by
p/q and r, shaded darkly below.
Its area must be a positive integer
A(p/q, r)
that is less than 1. Since
this is clearly impossible, r must have appeared somewhere
earlier in the tree.
We now have a way to label positive rational numbers as finite
strings of L's and R's. (We need a special symbol,
perhaps I, to denote 1/1.)
What happens if we allow ourselves to consider infinite strings of
L's and R's? Clearly, infinite strings correspond to
positive irrational numbers. If &alpha is a positive irrational
number, we may determine the corresponding string using the following
algorithm:
 Begin at r = 1/1 and let S be the empty string.
 If &alpha < r, replace r by its left child and
replace S by SL. Otherwise, replace r by its
right child and S by SR.
 Repeat step 2.
It is amusing to consider some obvious strings, for example,
S = RLRLRLRLRLR.... Notice that we begin at
1/1, move to 2/1, 3/2, 5/3, 8/5, .... Since we alternate right and
left moves, we always move to the mediant of the two preceeding terms
in the sequence. Alert readers will recognize these rationals as
ratios of consecutive Fibonacci numbers
F_{n}/F_{n1}. (You may remember
that the
Fibonacci sequence is the ubiquitous sequence defined by
F_{0} = 0,
F_{1} = 1,
and
F_{n} =
F_{n1} +
F_{n2}.) As it is well known that
F_{n}/F_{n1} converges to the
golden ratio , one of mathematics' very
special numbers, we have
&phi = RLRLRLRLRLR ....
A result of Euler implies that e, the
base of the natural logarithm, corresponds to the curious string:
e =
RL^{0}
RLR^{2}
LRL^{4}
RLR^{6}
LRL^{8}...
Summarizing what we have seen, we can represent any real number
x
by a string, either finite or infinite, of L's and R's.
By considering these strings as paths in the SternBrocot tree, we
obtain a sequence of rational numbers that converges to x.
Remembering that e is approximately 2.7182818... and that
e =
RL^{0}
RLR^{2}
LRL^{4}
RLR^{6}
LRL^{8}..., we obtain the following sequence that
converges to e.
R  2/1  2.0000000... 
RR  3/1  3.0000000... 
RRL  5/2  2.5000000... 
RRLR  8/3  2.6666666... 
RRLRR  11/4  2.7500000... 
RRLRRL  19/7  2.7142857... 
RRLRRLR  30/11  2.7272727... 
RRLRRLRL  49/18  2.7222222... 
RRLRRLRLL  68/25  2.7200000... 
RRLRRLRLLL  87/32  2.7187500... 
RRLRRLRLLLL  106/39  2.7179487... 
Rational approximations
The key to the use of the SternBrocot tree in clock making is
that the sequences obtained in this way are optimal in the following
sense. The rational numbers in the sequence approximate the real
number x to which they converge. Simply said, given any
rational approximation of x, the sequence typically contains
an element that is a better approximation and that has a smaller
numerator and denominator. Said with more precision,
If the rational number r is not in the SternBrocot sequence
that converges to x, then some element in the sequence, with
a numerator no larger than r's and a denominator no larger than
r's, lies between r and x.

To illustrate, consider the case where x = &phi
1.61803398875.... We may take p/q to be the
rational number 1.618 = 809/500. Here is the first part of the
sequence produced by the SternBrocot tree.
R  2/1  1.0000000... 
RL  3/2  2.0000000... 
RLR  5/3  1.5000000... 
RLRL  8/5  1.6666667... 
RLRLR  13/8  1.6000000... 
RLRLRL  21/13  1.6250000... 
RLRLRLR  34/21  1.6153846... 
RLRLRLRL  55/34  1.6190476... 
RLRLRLRLR  89/55  1.6176471... 
RLRLRLRLRL  144/89  1.6181818... 
RLRLRLRLRLR  233/144  1.6179775... 
RLRLRLRLRLRL  377/233  1.6180556... 
RLRLRLRLRLRLR  610/377  1.6180258... 
RLRLRLRLRLRLRL  987/610  1.6180371... 
RLRLRLRLRLRLRLR  1597/987  1.6180328... 
Notice that 610/377, which is approximately 1.6180258,
has a smaller denominator and numerator than
809/500 and is a better approximation.
To see why this property holds, consider the process by which we
create the sequence that converges to x. At every step, we
have consecutive rationals
p/q and p'/q'
that bracket x. Since r is
a rational different from x, eventually r is not
bracketed by these two rational numbers.
Consider the last step at
which r is bracketed by
p/q and p'/q'.
If p''/q'' is the next mediant obtained in the
process, then it must lie between r and x.
Now
r will be found in the SternBrocot tree under
p''/q'', which means that the numerator of
r is no larger than p'' and the denominator is no
larger than q''. Thus,
p''/q'' is closer to x than r is
and the numerator and denominator are no larger than r's.
Clock making and the SternBrocot tree
So why would a clock maker be interested in this tree?
If you open up a clock, you'll probably see something like what I did
when I pried open a cheap travel clock.
Clocks typically have a source of energysuch as a spring, a
suspended weight, or a batterythat turns a shaft at a fixed rate.
If the clock has, say, a minute hand and an hour hand, then some
mechanism is needed to speed or slow the motion of the shaft as it is
transferred to the hands.
Gears are used to slow the motion of the shaft. In the
figure below, the smaller green gear, with 20 teeth, drives the larger
blue gear, with 60 teeth. (In the language of clock making, the
smaller gear is called a pinion while the larger one is a
wheel.)
As the green pinion advances by one tooth, so
does the blue wheel. Therefore, one revolution of the green pinion
produces 20/60 or 1/3 of a revolution of the blue wheel. The angular
speed of the green pinion has been slowed by a factor of 20/60 = 1/3.
If we want a shaft that rotates once a second to drive a
minute hand, we could use a pinion and wheel whose ratio of teeth is
1/60. But we have another option. The figure below illustrates a
gear train; the green pinion turns the blue wheel slowing the
speed by a factor 1/6. However, the blue wheel turns the red pinion
at the same rate, and this pinion, with 10 teeth, turns the gray
wheel, with 100 teeth thus slowing the speed by another factor of
1/10. Therefore, the ratio of the speed of the green pinion to the gray
wheel is 1/6 1/10 = 1/60.
Any number of stages can be added, at least in theory. For
instance, we could mount another pinion on the gray wheel and have
it drive yet another wheel.
To illustrate the use of this thinking, imagine that we have a
shaft that rotates once per minute and we wish to drive an hour hand,
which rotates once every 12 hours. The ratio of these speeds is
1/720. We could use a single pinion with one tooth to drive a wheel
with 720 teeth or a pinion with 10 teeth driving a wheel with 7200
teeth. Surely, the larger gears would be unyieldy. Instead,
we could use a threestage gear train noting that
1/720 = 1/(10
89) =
1/10
1/8
1/9
The key here is that we can factor 720. Here's another
example suggested by Camus in the eighteenth century: Suppose we
place a pinion on a shaft that rotates once every hour and ask to
drive a wheel that rotates once in a mean tropical year, which is 365
days, 5 hours, 49 minutes. Converting both periods to minutes, we see
that we need the ratio 720 /
525,949. The problem here is that the denominator 525,949 is prime so
we cannot factor it. To obtain this ratio exactly, we cannot use
gears with a smaller number of teeth. It is likewise impossible to
find a multistage gear train to obtain this ratio.
Brocot illustrated how to use the SternBrocot tree to obtain
excellent approximations of the desired ratio in cases like this. As
we slide down the tree toward 720 / 525,949, the rationals we meet
along the way will give good approximations with relatively small
numerators and denominators.
We'll come back to this problem after describing another
observation Brocot made that allows us to compute the error in such an
approximation. To illustrate his method, Brocot considered a similar
situation in which it is desired that a shaft that rotates every 23
minutes turns a wheel that rotates every 191 minutes. We therefore
seek the ratio 23/191. Since both 23 and 191 are prime, we cannot
realize this ratio with a multistage gear train. Instead, we will
use the SternBrocot tree to approximate this ratio and to understand
the error in the approximation.
Suppose we are approximating
23/191 with p/q. Imagine constructing a pinion
with p teeth on the shaft and letting it
turn a wheel with q teeth. The pinion makes a revolution
every 23 minutes. This means that the wheel makes a revolution
every 23q/p minutes. The error is therefore
Recalling the additive property of the quantity A,
we may easily compute A(p/q, 23/191) as we
descend the tree. Since 23/191
is between 1/8 and 1/9, Brocot began by making a table like this:
p  q  A 
1  9  +16 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
1  8  7 
He now added a row for the mediant. Notice how each entry in the
new row is obtained by adding the corresponding entries in the other rows.
p  q  A 
1  9  +16 
2  17  +9 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
1  8  7 
This shows that if we approximate 23/191 by 2/17, the error will
result in the wheel taking A(2/17, 23/191) / p = 9/2 = 4.5
too many minutes to rotate.
Brocot then continued:
p  q  A 
1  9  +16 
2  17  +9 
3  25  +2 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
1  8  7 

p  q  A 
1  9  +16 
2  17  +9 
3  25  +2 
...  ...  ... 
...  ...  ... 
...  ...  ... 
...  ...  ... 
4  33  5 
1  8  7 

p  q  A 
1  9  +16 
2  17  +9 
3  25  +2 
...  ...  ... 
...  ...  ... 
...  ...  ... 
7  58  3 
4  33  5 
1  8  7 

p  q  A 
1  9  +16 
2  17  +9 
3  25  +2 
...  ...  ... 
...  ...  ... 
10  83  1 
7  58  3 
4  33  5 
1  8  7 

p  q  A 
1  9  +16 
2  17  +9 
3  25  +2 
13  108  +1 
...  ...  ... 
10  83  1 
7  58  3 
4  33  5 
1  8  7 

p  q  A 
1  9  +16 
2  17  +9 
3  25  +2 
13  108  +1 
23  191  0 
10  83  1 
7  58  3 
4  33  5 
1  8  7 

Among other things, this shows that we can approximate 23/191 with
13/108, which results in the wheel being late to complete its rotation
by 1/13^{th} of a minute.
Let's apply this thinking to Camus' problem of
720 / 525,949, whose corresponding string is:
L^{730}
R^{2}
L^{15}
R
L^{6}
R^{2}.
Let's begin sliding down the tree. The right column, labeled
A, will record
A(p/q, 720 / 525949). In this table, the
mediants appear in the order in which we encounter them.
 p  q  A 
 0  1  720 
 1  0  525,949 
 1  1  525,229 
L  1  2  524,509 
L  ...  ...  ... 
L  1  730  349 
L  1  731  371 
R  2  1461  22 
R  3  2191  327 
L  5  3652  305 
L  7  5113  283 
L  ...  ...  ... 
L  29  21184  41 
L  31  22645  19 
L  33  24106  3 
R  64  46751  16 
L  97  70857  13 
L  130  94963  10 
L  163  119069  7 
L  196  143175  4 
L  229  167281  1 
L  262  191387  2 
R  491  358668  1 
R  720  525949  0 
As we descend the SternBrocot tree towards
720 / 525,949, we find the fraction 196 / 143,175, which may be factored as
196 / 143,175 =
2/3
2/25
7/23
7/83
We can therefore construct a fourstage gear train, turned by the
hour wheel, in which the last wheel completes a rotation in
4/196 minutes less than a tropical mean year.
This is just a little over a second too fast. Not a bad approximation
at all! (Actually, a tropical mean year is nearly 15 seconds less than
525,949 minutes. However, once we've taken aim at a target, we'd
like to hit it, even if the target's not where it should be.)
Why did we look at the approximation 196 / 143,175? Because we
could factor the numerator and denominator with relatively small
factors. I found this by factoring the numerator and denominators of
all the terms in the sequence and noting which had desirable
factorizations. However, Brocot also constructed a "table of factors
of all useful numbers" where a useful number was,
of course, one that had relatively small factors. Had Brocot
performed the search we just did, he would have recognized 196 /
143,175 as a good choice since both the numerator and denominator
are candidates for his table.
Are you bothered that our clock is a second fast over the course
of a tropical mean year? Brocot showed us how to do better still. Up
to this point, we have slid down the tree to our desired ratio of 720
/ 525,949. We could, however, keep moving down the tree to obtain
closer approximations.
Brocot would have begun with a table like this:
p  q  A 
491  358668  1 
...  ...  ... 
720  525949  0 
and began adding mediants:
p  q  A 
491  358688  1 
1211  884637  1 
1931  1410586  1 
2651  1936535  1 
3371  2462484  1 
4091  2988433  1 
4811  3514382  1 
5531  4040331  1 
...  ...  ... 
720  525949  0 
Here, we are sliding down the tree below the ratio we seek, but
the mediants are continually better approximations. In this way, you
would find a threestage gear train with the ratios:
23/218
71/527
107/1111
=
174,731 / 127,638,346
that is too slow by 1 / 127,638,346 of a minute (roughly two
millionths of a second) over the course of a year.
The Euclidean algorithm and continued fractions
We've seen Brocot's motivation for discovering the SternBrocot
tree. Stern's interests were more mathematical. For instance,
the tree is intimately related to the Euclidean algorithm. This
algorithm finds the greatest common divisor of two positive integers
m and n by performing the following:
 If m > n, replace m by m 
n. Otherwise, replace n by n  m.
 If n = 0, then m is the greatest common
divisor. Otherwise, repeat from the beginning.
To see how this works, let m = 52 and n = 12.
We have
m  n 
52  12 
40  12 
28  12 
16  12 
4  12 
4  8 
4  4 
4  0 
This shows that the greatest common divisor is 4. Now
consider beginning with 12/52 and seeking approximations in the
SternBrocot tree using the sign changes of
A(p/q, 12/52) as a guide for when to change
direction.
 p  q  A 
 0  1  12 
 1  0  52 
 1  1  40 
L  1  2  28 
L  1  3  16 
L  1  4  4 
L  1  5  8 
R  2  9  4 
R  3  13  0 
Notice how the right column may be interpreted as a form of the
Euclidean algorithm.
It is well known that the Euclidean algorithm and continued
fractions are intimately related so it is no surprise that the
SternBrocot representation of a rational number is related to its
continued fraction. In particular, the rational corresponding to
R^{a0}
L^{a1}
R^{a2}
...
L^{an1}
is represented as the continued fraction
Summary
I learned about the "mathematical side" of the SternBrocot tree
some time ago from the superb book of Graham, Knuth, and Patashnik
listed in the references. Since the Euclidean algorithm and continued
fractions are close relatives of the tree, it is clear that we are
walking on fertile ground. I suppose that this represents Stern's
side of the tree, the side that appreciates the tree for its
mathematical elegance and its relation to other important ideas in
number theory.
It was only recently that I learned from Brian Hayes' equally good
book how Brocot found and used the tree to which he lent his name.
This story interested me, as it clearly did Hayes as well, since it
demonstrates the many faces of mathematical ideas; how they may appear
in different places and be both beautiful and useful at the same time.
References
I have benefitted enormously from the following two books, both of
which are highly recommended.
 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete
Mathematics: A Foundation for Computer Science, Second Edition.
AddisonWesley. 1994.
This presents the "mathematical side" of the SternBrocot tree
and its relationship to other aspects of number theory.
 Brian Hayes, "On the Teeth of Wheels" in Group Theory in the
Bedroom, and Other
Mathematical Diversions. Hill and Wang. 2008.
This essay may be read online at
http://www.americanscientist.org/issues/pub/ontheteethofwheels/
It was Hayes' diligent scholarship that brought Brocot's
contribution to my attention. I found the next references by
following in Hayes' footsteps.
 A. Brocot, Calcul des rouages par approximation, Nouvelle
méthode. Revue chronomeétrique, 3, 1861.
18694.
Brocot's paper is interesting for the insight it gives into his
thinking.
 C. Camus, A Treatise on the Teeth of Wheels, Demonstrating
the Best Forms Which Can Be GIven to Them for the Purposes of
Machinery; Such as Millwork and Clockwork, and the Art of Finding
Their Numbers. Translated from the French by John Isaac
Hawkins. M. Taylor. 1842.
 H.E. Merritt, Gear Trains: Including a Brocot Table of
Decimal Equivalents and a Table of Factors of All Useful Numbers up to
200,000. Pitnam and Sons. 1947.
 M.A. Stern. Ueber eine zahlentheoretische
Funktion. Journal für die reine und angewandte
Mathematik, 55, 1858. 193220.