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).
The nthFarey 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:
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. 385-386 (1816).
(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
1
2
1
2
3
3
1
2
3
3
4
5
5
4
Denominator Tree
1
1
0
2
1
3
3
2
1
4
5
5
4
3
3
2
1
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/1
1/2
2/1
1/3
2/3
3/2
3/1
1/4
2/5
3/5
3/4
4/3
5/3
5/2
4/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.
(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!
Moshe Newman is credited
with the discovery of a very nice alternate definition of this rational sequence,
namely:
uo = 0 and
un+1 = f (un )
where
f (x) = 1 / (1 + 2 ë x û - x )
When this sequence is displayed as
a binary tree, each 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/1
1/2
2/1
1/3
3/2
2/3
3/1
1/4
4/3
3/5
5/2
2/5
5/3
3/4
4/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 Mathematik,
55:193-220.
C. Giuli and R. Giuli
"A primer on Stern's Diatomic Sequence" (1979; some errors) Fibonacci Quarterly,
17:2 (1979) 103-108, 246-248, 318-320.
(2005-10-25) Pick's Formula (or Pick's Theorem)
The surface area of a planar lattice polygon is I + ½ B
- 1, where:
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 ½
Applications :
A consequence of Pick's theorem is that the area of any grid polygon is
a rational number (in fact, it's a fraction whose denominator is at most 2).
Therefore, three grid points cannot form an equilateral triangle.
Otherwise, the side s of such an equilateral trinagle would
be the square root of an integer N (by the Pythagorean theorem)
and its area would be irrational (namely, N Ö3/4)
which contradicts the above remark.
