## Trees, Teeth, and Time: the mathematics of clock makingPull quote...David Austin
## IntroductionMathematics 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 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 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 Stern-Brocot tree To construct the Stern-Brocot tree, we will define the The mediant always lies between the two rational numbers that define it. To see this, we may identify a rational number (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 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 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
*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 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 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
## Sliding down the tree 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 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 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 With one more step to the left, we arrive at 4/7, which we may represent as How does this show that every positive rational appears in the tree? Suppose that we are looking for the rational Suppose that we never find Let's think about this geometrically. Since Remember that the area of the shaded parallelogram above is Its area must be a positive integer We now have a way to label positive rational numbers as finite strings of What happens if we allow ourselves to consider infinite strings of - 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, F. (You may remember that the Fibonacci sequence is the ubiquitous sequence defined by _{n-1}F = 0, _{0}F = 1, and _{1}F = _{n}F + _{n-1}F.) As it is well known that _{n-2}F/_{n}F converges to the golden ratio , one of mathematics' very special numbers, we have &phi = _{n-1}RLRLRLRLRLR .... A result of Euler implies that e = RL^{0} RLR^{2} LRL^{4} RLR^{6} LRL^{8}... Summarizing what we have seen, we can represent any real number
## 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
To illustrate, consider the case where
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 Consider the last step at which If Now
## Clock making and the Stern-Brocot treeSo 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 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 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 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 Recalling the additive property of the quantity
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.
This shows that if we approximate 23/191 by 2/17, the error will result in the wheel taking Brocot then continued:
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 Let's apply this thinking to Camus' problem of 720 / 525,949, whose corresponding string is: Let's begin sliding down the tree. The right column, labeled
As we descend the Stern-Brocot tree towards 720 / 525,949, we find the fraction 196 / 143,175, which may be factored as 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:
and began adding mediants:
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: 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
- 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
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
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
## SummaryI 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:- 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' 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.
I have benefitted enormously from the following two books, both of which are highly recommended. David Austin 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. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |