Generating the Rational Numbers

572 days ago by mpaul

Here is a function that will return the 'mediant' of two fractions:
def mediant(a, b): n = numerator(a) + numerator(b) d = denominator(a) + denominator(b) return n/d 
       

The mediant of two fractions is a new fraction
whose numerator is the sum of the numerators, and
whose denominator is the sum of the denominators.
a = 2/7 b = 5/11 mediant(a, b) 
       

The mediant of two fractions is not their mean, but it will be a value close to their mean. 
mediant(a, b).n(digits = 15) 
       
(a+b)/2.0 
       

The mediant is, in fact, a kind of average. For example, batting averages are mediants.

The mediant has some fascinating properties. One is that it provides a way to generate the rational numbers. 
By successively inserting mediants between 0/1 and 1/1 we can generate all proper fractions in lowest terms and in order:
[0/1, 1/1] 
       
[0/1, mediant(0/1, 1/1), 1/1] 
       
[0, mediant(0, 1/2), 1/2, mediant(1/2, 1), 1] 
       

Here is a function that will do the work for us of expanding a list of rationals by inserting mediants:
def expand(row): expanded = [row[0]] for (a, b) in zip(row[:-1], row[1:]): expanded += [mediant(a, b), b] return expanded 
       
def expand(row): expanded = [row[0]] for (a, b) in zip(row[:-1], row[1:]): expanded.append(mediant(a, b)) expanded.append(b) return expanded 
       
rationals = [0, 1] 
       
rationals = [0, 1] for i in range(5): rationals rationals = expand(rationals) 
       
 
       

John Farey was a British geologist who in 1816 noticed an interesting property regarding sequences containing all of the proper fractions in order whose denominators are less than or equal to some number n.

Here are the first five Farey sequences:

F( 1 ): [\frac{0}{1}, \frac{1}{1}]
F( 2 ): [\frac{0}{1}, \frac{1}{2}, \frac{1}{1}]
F( 3 ): [\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}]
F( 4 ): [\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}]
F( 5 ): [\frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}]

Farey noticed that for any three consecutive terms in one of these sequences the middle term is always the mediant of the outer two.  

Related to Farey sequences are Ford circles.  In 1938 Lester Ford found a way to visualize Farey sequences by corresponding a unique circle to each rational number p/q:

On a number line draw a circle at \frac{p}{q} whose diameter is \frac{1}{q^2}. 

Ford circles for reduced fractions never overlap. 
Circles for consecutive Farey values will always be tangent, and constructing the Ford circle for a mediant will always produce a new circle tangent to both parents.
def fordcircle(n): r = 0.5/denominator(n)^2 return circle((n, r), radius = r) def circles(L): show(sum([fordcircle(n) for n in L]), aspect_ratio = 1) def rational_number_generator(): R = [0/1, 1/1] while True: circles(R) yield R R = expand(R) r = rational_number_generator() 
       

Each evaluation of r.next() will yield the next iteration of rationals and their associated Ford circles:
r.next() 
       
r.next() 
       
r.next() 
       
r.next() 
       
r.next() 
       

It is interesting that by inserting mediants between consecutive fractions we generate the rational numbers in lowest terms and in order!

If we begin our original sequence with [\frac{0}{1}, \frac{1}{0}] and successively insert mediants, this will generate the following sequences:

[\frac{0}{1}, \frac{1}{0}]
[\frac{0}{1}, \frac{1}{1}, \frac{1}{0}]
[\frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0}]
[\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0}]
[\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{5}{3}, \frac{2}{1}, \frac{5}{2}, \frac{3}{1}, \frac{4}{1}, \frac{1}{0}]
...

If continued indefinitely, this process will generate ALL the non-negative rational numbers! 

This is called the 'Stern-Brocot tree', because it was discovered independently by Moritz Stern, a German mathematician in 1858, and Achille Brocot, a French clockmaker in 1860.

Of course, we don't normally accept 1/0 as a valid number, but in using it for this purpose, it works very nicely as 'infinity'.
 
       
def mediants(L): return [mediant(f, g) for (f, g) in zip(L[:-1], L[1:])] def opposites(L): return [-f for f in L] def reciprocals(L): return [1/f for f in L if numerator(f) > 0] def lineplot(f, color = 'blue'): x, y = denominator(f), numerator(f) return line([(-x, -y), (x, y)], rgbcolor = color, aspect_ratio = 1, axes = False) def lineplots(L, c): return sum([lineplot(f, color = c) for f in L]) def random_color(): return random(), random(), random() def rationals(): Q = [0/1, 1/1] while True: M = mediants(Q) oppQ, invQ = opposites(Q), reciprocals(Q) oppM, invM = opposites(M), reciprocals(M) oppinvQ, oppinvM = opposites(reciprocals(Q)), opposites(reciprocals(M)) show(sum([lineplots(L, random_color()) for L in [Q, M, oppQ, oppM, invQ, invM, oppinvQ, oppinvM]])) Q = sorted(Q+M) yield Q Q = rationals() 
       
next(Q) 
       
 
       

We are familiar with using a number line to visualize numbers and their relationships, but fractions are two-part data structures.

If we use a coordinate plane, we can think of the vertical axis as the 'numerator' axis and the horizontal axis as the 'denominator' axis.

A line segment drawn from (0, 0) to (4, 3) would has a slope of \frac{3}{4}.

The following set of functions will generate and plot increasingly large lists of the rationals.