'''
This text file is a Python module.  It may be opened and read using any ordinary
text editor, but if you open it using Python's IDLE, it will become active.

IDLE comes with the Python download at www.python.org.

To run this module:
1.  Open this file in IDLE.
2.  Choose 'Run Module' from 'Run' in the menu bar, or
    type the F5 function key.

If you arrange this window and the Shell side by side, you will be able to
easily test the code you are studying as you read through the lesson.
'''
'''
M o d e l i n g   t h e   R a t i o n a l   N u m b e r s

                 - Michel Paul
                 
                    07.08.23

We have seen that we can use tuples to represent various kinds of
data structures such as Cartesian points or fractions.

However, when representing fractions, we might want to be able to
display them in typical fraction notation.

We could of course write a function such as display() where
display(1, 2) would return the string '1/2'.  

However, there is another way to approach this which, in the long run, is far,
far more useful for a whole lot of reasons.

Here is a small Rational number class:
'''
class Rational:
    def __init__(self, num, den): self.num, self.den = num, den
    def __repr__(self): return str(self.num) + '/' + str(self.den)

'''
This class will allow us to create Rational number objects.
The __init__ function 'initializes' a Rational number.
The __repr__ function 'represents' a Rational number.

For now that is all you need to know about this class.
Don't worry if you don't completely understand the code.
Just think of it as a way of organizing numerators and denominators into units.

We can now create Rational numbers:
'''
a = Rational(1, 2)
'''
Assuming that you have run this module,
if you now enter a at the prompt, you will get 1/2.

If you enter a.num at the prompt, you will get 1.
If you enter a.den, you will get 2.

Here is a function that will return the 'mediant' of two Rational numbers:
'''
def mediant(a, b): return Rational(a.num + b.num, a.den + b.den)
'''
The mediant of two fractions is a new fraction where
the numerator is the sum of the two original numerators, and
the denominator is the sum of the two original denominators.

The mediant of two fractions is not their mean, but it will be a value close to their mean.
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 remarkable way to
generate the set of all 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.

We begin with the sequence [0/1, 1/0] and successively insert mediants between consecutive
fractions.  Doing this will generate the following sequences:

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

(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'.)

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

Here is a function that will expand a list of fractions by inserting mediants:
'''
def expand(row):
	x = [row[0]]
	for i in range(1, len(row)): x += [mediant(row[i-1], row[i])] + [row[i]]
	return x
'''
Now we can create a rational number generator that will call call expand() over and over:
'''
def rationals():
    row = [Rational(0, 1), Rational(1, 0)]
    while True:
        yield row
        row = expand(row)

r = rationals()
'''
If you now enter r.next() at the prompt, you will get [0/1, 1/0] as a response.  After that,
each time you enter r.next() you will get the the expansion of the previous row.

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

Related to, and prior to, the Stern-Brocot tree are 'Farey' sequences.

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 do not exceed N.

Here are the first five Farey sequences:

F( 1 ):  [0/1, 1/1]
F( 2 ):  [0/1, 1/2, 1/1]
F( 3 ):  [0/1, 1/3, 1/2, 2/3, 1/1]
F( 4 ):  [0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1]
F( 5 ):  [0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 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.

We can easily derive a Farey sequence from a Stern-Brocot expansion:
'''
def farey(n):
    row = [Rational(0, 1), Rational(1, 1)]
    for i in range(n): row = expand(row)
    return [i for i in row if i.den <= n]
'''
You can now compute any Farey sequence.  If you enter farey(3) at the prompt, you will
get the third Farey sequence above.

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 p/q whose diameter is 1/q^2.

Ford circles for reduced fractions never overlap.
Circles for consecutive Farey values will always be tangent, and constructing
the circle for a mediant will always produce a new circle tangent to both parents!

The following code will let us see some Ford circles:
'''
from turtle import *

def frame():
    global unit; unit = window_height() - 50.0
    global origin; origin = -unit/2, -unit/2
    tracer(False)
    up(); goto(origin); down()
    for side in range(4): forward(unit); left(90)

def plot(num, den):
    diameter = unit/den**2
    up(); goto(origin); setheading(0); down()
    forward(unit*num/den)
    circle(diameter/2)

def fordcircles(fareyseq):
    frame()
    for f in fareyseq: plot(f.num, f.den)
    return fareyseq
'''
You can now plot the set of Ford circles that correspond to any Farey sequence.
Simply enter something like fordcircles(farey(6)) at the prompt.

This provids a wonderful way to visualize the rational numbers!

The two largest Ford circles correspond to the numbers 0/1 and 1/1.
The circle in the center corresponds to 1/2.  Circles for fractions with the same
denominator are the same size, and they mark off the unit in equal segments.

To bring this full "circle" (pun intended) we can also interpret the largest circle
as corresponding to 1/0, our friend 'infinity'.  Then the middle circle corresponds to 1/1,
and circles corresponding to reciprocal values will be of the same size.  This interpretation
lets us visualize all of the non-negative rationals; however, circles of the same denominator
no longer divide the unit into equal segments.

'''