home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2017   Gérard P. Michon, Ph.D.


Articles previously on this page:



(2005-10-25)   Ford Circles

Ford circles are named after Lester R. Ford, Sr. (1886-1967) who introduced the concept in 1938  (American Mathematical Monthly, volume 45, 9, pp. 586-601).  The famous Ford-Fulkerson optimisation algorithm (1956) is named after his son, Lester Randolph Ford Jr.  (1927-2017).

The Ford circle of the rational number  p/q  (expressed in lowest terms) is the circle of  diameter  1/q2  tangent from above to the x-axis at point p/q.

Ford circles of irrational numbers are of radius 0 and reduce to a single point.  The line  y = 1  is sometimes considered to be a degenerate Ford circle of infinite radius associated with  ¥  (unsigned infinity).

Remarkably, two Ford circles never overlap.  The Ford circles associated with two irreducible fractions  a/b  and  c/d  are  tangent  to each other if, and only if, ad  and  bc  are consecutive integers.  The largest Ford circle between such tangent Ford circles is associated with the  mediant  fraction  (a+c) / (b+d).

 Come back later, we're
 still working on this one...

Rational numbers and Ford Circles (9:42)  by  Norman J. Wildberger   (2009-03-12)

(2005-10-25)   Farey Series

The  nth  Farey series  is the increasing sequence of all the rational numbers  (irreducible fractions)  between 0 and 1 whose denominators are n or less.  For example, the sixth  Farey series  is:

0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1

Each term of a Farey series is the mediant of the two terms that surround it  (the three corresponding Ford circles are thus pairwise tangent).

In 1816, the geologist John Farey, Sen. (1766-1826) published this remark in a short letter to the  Philosophical Magazine, entitled "On a curious Property of vulgar Fractions".  This attracted the attention of Augustin Cauchy, who supplied a proof in  Exercises de mathématiques (1816).  Cauchy is responsible for the enduring attribution of these finite sequences to Farey.  In 1802 (14 years before Farey and Cauchy) Charles Haros had studied the 99th Farey series, in a paper about the approximation of decimal fractions by common fractions.

Some Farey series appear in the  Stern-Brocot tree,  introduced next.

Charles H. Haros was employed as a mathematician at the "Bureau du Cadastre de Paris" from October 1794 to March 1802.  He later worked as a calculator for the "Bureau des Longitudes" (he is listed as a contributor to the "Connaissance des Temps" ephemrides for the year 1805).
"On a Curious Property of Vulgar Fractions"   John Farey
The Philosophical Magazine and Journal, 47, 3, pp. 385386  (1816).
Farey Sums and Ford Circles (14:21)  by  Francis Bonahon   (Numberphile, 2015-06-09)

(2005-10-28)   Stern-Brocot Tree
A binary tree containing a  single  occurrence of every positive rational.

Let's label each node of a binary tree with a triplet of integers so that the left and right offsprings of a node labeled (x,y,z) are respectively labeled (x,x+y,y) and (y,y+z,z).  The label of the root determines the labels assigned to all the nodes.

Let's call   numerator tree  the tree so labeled whose root bears the label (0,1,1).  Call  denominator tree  the one whose root is labeled (1,1,0).

Numerator Tree
0 1 1
Denominator Tree
1 1 0

We use a graphical representation, where each offspring is assigned a box half the size of its parent's.  In each box, only the middle integer of the "label" is shown.  The other two values are simply found at the top of each bounding vertical line.  (In the middle of an ascendant's box, except for a leftmost or rightmost node.)

The Stern-Brocot tree is the binary tree whose nodes are labeled with the rational number p/q, where p (resp. q) is the middle integer in the label of the corresponding node of the above numerator tree  (resp. denominator tree).  Remarkably, all rational numbers are thus obtained  in irreducible form.

Stern-Brocot Tree
1/42/53/53/4 4/35/35/24/1

The rational numbers which appear in the left half of the tree are between 0 and 1.  A Farey series is obtained when the numbers in the first half of a line are interspersed with the numbers sitting at the top of the box boundaries.  For example, the fourth Farey series is obtained from the last line shown above:

0, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1

Any positive rational appears once and only once in the Stern-Brocot tree, at a location determined by its  continued fraction expansion (CFE)...

To reach the positive rational whose CFE is  [q0,q1,q2...qn]  go q0 steps right, q1 steps left, q2 steps right, and so forth alternately...  then  go back one step  (either that, or perform only qn-1 steps in the last stage).

The Stern-Brocot tree was discovered (at least) twice:

  • In 1858 by  Moritz Stern  (Über eine zahlentheoretische Funktion. Crelle's Journal  55:193-220).
    Moritz Abraham Stern (1807-1894) is credited with noticing the genius of his student Bernhard Riemann (1826-1866) early on at Göttingen.  Stern was also one of the main teachers of Richard Dedekind (1831-1916) who was Gauss's last student (receiving his doctorate in 1852).  In 1858, Stern was appointed to succeed Gauss (1777-1855) as professor ordinarius of mathematics at Göttingen University.  He was the first jewish Ordinarius in a German university.
  • In 1861, by  Achille Brocot  (Calcul des rouages par approximation, nouvelle méthode. Revue Chronométrique  3:186-194). 
    Achille Brocot (1817-1878)  was a famous innovative clockmaker, who stumbled upon the Stern-Brocot tree while computing optimal gear ratios.

"Arbre de Stern-Brocot"  by Jean-Paul Davalan   |   Numberphile:  Infinite Fractions by Matt Parker.

(2005-10-29)   Eisenstein-Stern Diatomic Sequence   (A002487)
Also known as Dijkstra's "fusc" function, the sequence of the so-called "Stern numbers" forms a recursively defined integer sequence :
 b(0) = 0 ,   b(1) = 1 ,   b(2n) = b(n),   b(2n+1) = b(n) + b(n+1)


In 1982, Edsger Wybe Dijkstra (1930-2002) called the sequence of Stern numbers "fusc" because it possesses a curious obfuscated property:  If the sum of two indices, n and m, is a power of 2, then b(n) and b(m) are  coprime.

The number of ways to express  n  as a sum of powers of  2  without using more than two equal terms turns out to be  b (n+1).  (This provides an obscure alternate way to define Stern numbers.)

The sequence of the ratios of two consecutive Stern numbers  un = b(n) / b(n+1)  runs through all nonnegative rational numbers (in reduced form) just once! 

0, 1,1/2, 2, 1/3, 3/2, 2/3, 3,1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, ...

Moshe Newman  is credited with the discovery of a very nice alternate definition of this rational sequence, namely:   uo = 0   and   un+1f (u)   where

f (x)  =  1 / (1 + 2 ë x û - x )

When this sequence is displayed as a binary treeeach level  features the same fractions as in the Stern-Brocot tree, but at different locations:  The respective positions [0 = leftmost] of a given fraction are mirror images in binary numeration.

Calkin-Wilf Tree
1/44/33/55/2 2/55/33/44/1

In this tree, the left child of   a / b   is   a / (a+b) ,  the right child is   (a+b) / b.  Thus, if the parent fraction is in  lowest terms, so are both offsprings...

References and History :

  • Gotthold M. Eisenstein (1823-1852)
    "Eine neue Gattung zahlentheoretischer Funktionen [...]" (1850)
    Verhandlungen der Königlich Preussischen Akademie der Wissenschaften zu Berlin 
  • Moritz A. Stern (1807-1894)
    "Über eine zahlentheoretische Funktion" (1858)
    Journal für die reine und angewandte Mathematik55:193-220. 
  • C. Giuli  and  R. Giuli
    "A primer on Stern's Diatomic Sequence" (1979; some errors)
    Fibonacci Quarterly17:2 (1979) 103-108, 246-248, 318-320. 
  • Neil J. Calkin   and   Herbert S. Wilf
    "Recounting the Rationals" [ pdf,  July 6, 1999 ]
    The American Mathematical Monthly,  107 (April 2000) 360-363. 
  • Igor Urbiha
    "Tree of fractions and Dijkstra's fusc function" (March 27, 2002)
    Seminar on Number Theory and Algebra, University of Zagreb. 
  • Jeremy Gibbons, David Lester and Richard Bird
    "Enumerating the Rationals" [ pdf ]

Stern numbers  (mistakenly called Stern-Brocot numbers)  by  Matt Parker  (Numberphile, Dec. 2014).

(2005-10-25)   Pick's Formula (or Pick's Theorem)
The surface area of a planar lattice polygon is  I + ½ B - 1,  where:
  • I   is the number of lattice points in the polygon's interior.
  • B  is the number of lattice points on the polygon's boundary  (i.e.,  at the vertices or on the edges).

This result is due to Georg Pick (1852-1949) who published it in 1899  ("Geometrisches zur Zahlenlehre"  Sitzungber. Lotos, Naturwissen Zeitschrift  Prague, 19, pp. 311-319).  Pick was instrumental in the appointment of Albert Einstein to the German University of Prague and became a close friend of Einstein's during his stay in Prague  (1911-1913).

Pick's theorem became famous in 1969, when it appeared in the third edition of the popular book  Mathematical Snapshots  which Hugo Steinhaus (1887-1972) had first published in 1938...

Lattice points  (which Pick called  reticular points)  are points whose coordinates are integers.  A lattice polygon is a polygon whose vertices are lattice points.  In the plane, a lattice polygon may be dissected into lattice triangles which have no lattice points (besides their vertices) inside of them or on their borders.  Therefore, Pick's formula for the area of a lattice polygon is a consequence of the following (surprising) special case:

A lattice triangle which has no lattice points besides its vertices
(i.e., inside of it, or on its edges)  has a surface area of  ½

Proving Pick's Theorem  by  Kelsey Houston-Edwards  (PBS Infinite Series, 2017-03-16).

visits since Dec. 6, 2000
 (c) Copyright 2000-2017, Gerard P. Michon, Ph.D.