Trees, Teeth, and Time: The mathematics of clock making
Posted December 2008.
Brocot illustrated how to use the Stern-Brocot tree to obtain excellent approximations of the desired ratio...
David Austin
Grand Valley State University
david at merganser.math.gvsu.edu
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 Stern-Brocot 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 surprisingly 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 co-discoverer, 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 Stern-Brocot tree and its use in clock making.
Construction of the Stern-Brocot tree
To construct the Stern-Brocot 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 terms--that is, where p and q have no common factors--so 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 Stern-Brocot 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 well-known 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 r1 and r2 are rationals, then A(r1, r2) is an integer.
- A(r, r) = 0.
- A satisfies an additive property: A(r1 r2, r3) = A(r1, r3) + A(r2, r3)
- A( sp / sq, r2) = s A(p/q, r2).
We now claim that, if r1 and r2 are consecutive rational numbers at any step of the construction of the Stern-Brocot tree, then
A(r1, r2) = 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 r1 and r2, consecutive rationals at some step of the construction. To form the next step, we add the mediant of r1 and r2 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 terms--that 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 Stern-Brocot 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 α 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 α < 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 Fn/Fn-1. (You may remember that the Fibonacci sequence is the ubiquitous sequence defined by F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2.) As it is well known that Fn/Fn-1 converges to the golden ratio 
, one of mathematics' very special numbers, we have φ = RLRLRLRLRLR ....
A result of Euler implies that e, the base of the natural logarithm, corresponds to the curious string:
e = RL0 RLR2 LRL4 RLR6 LRL8...
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 Stern-Brocot tree, we obtain a sequence of rational numbers that converges to x. Remembering that e is approximately 2.7182818... and that e = RL0 RLR2 LRL4 RLR6 LRL8..., 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 Stern-Brocot 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 Stern-Brocot 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 = φ 
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 Stern-Brocot tree.
| R |
2/1 |
2.0000000... |
| RL |
3/2 |
1.5000000... |
| RLR |
5/3 |
1.6666666... |
| RLRL |
8/5 |
1.6000000... |
| RLRLR |
13/8 |
1.6250000... |
| RLRLRL |
21/13 |
1.6153846... |
| RLRLRLR |
34/21 |
1.6190476... |
| RLRLRLRL |
55/34 |
1.6176471... |
| RLRLRLRLR |
89/55 |
1.6181818... |
| RLRLRLRLRL |
144/89 |
1.6179775... |
| RLRLRLRLRLR |
233/144 |
1.6180556... |
| RLRLRLRLRLRL |
377/233 |
1.6180258... |
| RLRLRLRLRLRLR |
610/377 |
1.6180371... |
| RLRLRLRLRLRLRL |
987/610 |
1.6180328... |
| RLRLRLRLRLRLRLR |
1597/987 |
1.6180344... |
Notice that 610/377, which is approximately 1.6180371, 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 Stern-Brocot tree under p''/q'', which means that the numerator of r is no smaller than p'' and the denominator is no smaller 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 Stern-Brocot 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 energy--such as a spring, a suspended weight, or a battery--that 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 and so the angular speed of the blue wheel is 1/3 that of the green pinion.
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 three-stage 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 multi-stage gear train to obtain this ratio.
Brocot illustrated how to use the Stern-Brocot 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 multi-stage gear train. Instead, we will use the Stern-Brocot 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/13th of a minute.
Let's apply this thinking to Camus' problem of 720 / 525,949, whose corresponding string is: L730 R2 L15 R L6 R2.
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 Stern-Brocot 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 four-stage 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 three-stage 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 Stern-Brocot 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 Stern-Brocot 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 Stern-Brocot representation of a rational number is related to its continued fraction. In particular, the rational corresponding to Ra0 La1 Ra2 ... Lan-1 is represented as the continued fraction
Summary
I learned about the "mathematical side" of the Stern-Brocot 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. Addison-Wesley. 1994.
This presents the "mathematical side" of the Stern-Brocot 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/on-the-teeth-of-wheels/
It was Hayes' diligent scholarship that brought Brocot's contribution to my attention. I found the next references by following in Hayes's footsteps.
- A. Brocot, Calcul des rouages par approximation, Nouvelle méthode. Revue chronomeétrique, 3, 1861. 186-94.
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 Mill-work and Clock-work, 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. 193-220.
David Austin
Grand Valley State University
david at merganser.math.gvsu.edu
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.
