Date: __4/14/14______________

The following function, build_F, returns a twodimensional list, F, with N rows and M columns. The entry at F[i][j] is the tuple (i,j+1). Evaluate the following block to define the function and to use it to build a 10by10 table. Note that the entries in this table can be interpreted as all possible nonnegative fractions whose numerator, $n$, satisfies $0 \leq n < N$ and whose denominator, $d$, satisfies $0 < d \leq M$.
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10)] [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10)] [(2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10)] [(3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10)] [(4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10)] [(5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10)] [(6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (6, 9), (6, 10)] [(7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7), (7, 8), (7, 9), (7, 10)] [(8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (8, 9), (8, 10)] [(9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9), (9, 10)] [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10)] [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10)] [(2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10)] [(3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10)] [(4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10)] [(5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10)] [(6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (6, 9), (6, 10)] [(7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7), (7, 8), (7, 9), (7, 10)] [(8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (8, 9), (8, 10)] [(9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9), (9, 10)] 
Using upward sloping diagonals we can write the infinite version of this two dimensional array as an infinite one dimensional list. It would start as follows:
[(0,1), (1,1), (0,2), (2,1), (1,2), (0,3), (3,1), . . . ]
In the following block the function, build_F1d, returns the initial portion of this one dimensional list. Set N to 7 to see the same initial list. Then set N to 55 to see the list the "fractions" in the upper half of the preceding array.
[(0, 1), (1, 1), (0, 2), (2, 1), (1, 2), (0, 3), (3, 1)] [(0, 1), (1, 1), (0, 2), (2, 1), (1, 2), (0, 3), (3, 1)] 
The previous two blocks of code define a procedure for uniquely identifying every nonnegative fraction with a positive integer and vice versa. This shows that there is a onetoone corresponce between the nonnegative fractions and the positive integers. In other words, the nonnegative fractions are countably infinite.
To make this a formal bijection we really need two functions, NonNegFracToPosInt, and its inverse, PosIntToNonNegFrac. Given a nonnegative fraction NonNegFracToPosInt returns the corresponding positive integer. Given a positive interger PosIntToNonNegFrac returns the corresponding nonnegative fraction.
Exercise 1: Construct the functions, NonNegFracToPosInt and PosIntToNonNegFrac, which together define the bijection between the positive integers and the nonnegative fractions. Complete the definitions of the two functions and avoid using any loops.
Hint, the Triangular Numbers have come up several times during this semester.

1 Traceback (click to the left of this block for traceback) ... NameError: global name 'j' is not defined 1 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_6.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# * coding: utf8 *\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cHJpbnQgTm9uTmVnRnJhY1RvUG9zSW50KDAsMSksIFBvc0ludFRvTm9uTmVnRnJhYygxKQpwcmludCBOb25OZWdGcmFjVG9Qb3NJbnQoMCwzKSwgUG9zSW50VG9Ob25OZWdGcmFjKDYpCnByaW50IE5vbk5lZ0ZyYWNUb1Bvc0ludCgyLDIpLCBQb3NJbnRUb05vbk5lZ0ZyYWMoOCkKcHJpbnQgTm9uTmVnRnJhY1RvUG9zSW50KDksMSksIFBvc0ludFRvTm9uTmVnRnJhYyg0NikKcHJpbnQgTm9uTmVnRnJhY1RvUG9zSW50KDAsMTApLCBQb3NJbnRUb05vbk5lZ0ZyYWMoNTUp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in <module> File "/tmp/tmpKqB2Nv/___code___.py", line 3, in <module> print NonNegFracToPosInt(_sage_const_0 ,_sage_const_1 ), PosIntToNonNegFrac(_sage_const_1 ) File "/tmp/tmp42rPHX/___code___.py", line 16, in PosIntToNonNegFrac return (i,j) NameError: global name 'j' is not defined 
We say that two fractions $a/b$ and $c/d$ are equivalent if and only if $a\cdot d = c\cdot b$. It is straightforward to verify that this requirement defines an equivalence relation on the positive "fractions" as described above, namely all pairs of positive integers where the second integer is always nonzero.
Exercise 2. On a separate sheet of paper verify that this proposed relationship is an equivalence relationship because it satisfes the following three defining properties.
Exercise 3. On the printout from the first block, use pencil(s), pen(s), or highlighter(s), to circle or highlight each set of equivalent fractions containing more than 3 fractions. Hint, the first row is one such set, but many sets have less than 4 members (some only 1) and should not be hightlighted. Also write a short program which prints the same table, but prints the pair of integers in the conventional fraction form $p/q$. This version of the table should quickly confirm your hand drawn results.
0 0 0 0 0 0 0 0 0 0 1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10 2 1 2/3 1/2 2/5 1/3 2/7 1/4 2/9 1/5 3 3/2 1 3/4 3/5 1/2 3/7 3/8 1/3 3/10 4 2 4/3 1 4/5 2/3 4/7 1/2 4/9 2/5 5 5/2 5/3 5/4 1 5/6 5/7 5/8 5/9 1/2 6 3 2 3/2 6/5 1 6/7 3/4 2/3 3/5 7 7/2 7/3 7/4 7/5 7/6 1 7/8 7/9 7/10 8 4 8/3 2 8/5 4/3 8/7 1 8/9 4/5 9 9/2 3 9/4 9/5 3/2 9/7 9/8 1 9/10 0 0 0 0 0 0 0 0 0 0 1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10 2 1 2/3 1/2 2/5 1/3 2/7 1/4 2/9 1/5 3 3/2 1 3/4 3/5 1/2 3/7 3/8 1/3 3/10 4 2 4/3 1 4/5 2/3 4/7 1/2 4/9 2/5 5 5/2 5/3 5/4 1 5/6 5/7 5/8 5/9 1/2 6 3 2 3/2 6/5 1 6/7 3/4 2/3 3/5 7 7/2 7/3 7/4 7/5 7/6 1 7/8 7/9 7/10 8 4 8/3 2 8/5 4/3 8/7 1 8/9 4/5 9 9/2 3 9/4 9/5 3/2 9/7 9/8 1 9/10 
When a pair of integers is explicitly written in the conventional fraction form, $p/q$, Sage automatically "reduces the fraction to lowest terms," and this fraction becomes the conventional representative for the set of equivalent fractions. However the other equivalent fractions are absolutely essential for the arithmetic operations of addition, subtraction, multiplication, and division. So the more sophisticated mathematical view of the set of Rational Numbers, Q, is that Q is the set of equivalence classes of fractions, and that each equivalence class is conventionally represented by the fraction in the set which has been reduced to lowest terms. However, any fraction in the set can be used for arithmetic calculations. Given any member of a class, say 1234567890987654321 / 123451234598769876, how can we find the conventional representative? The answer is Euclid's algorithm.

Euclid's algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers. It is named after the Greek mathematician Euclid, who described it in Books VII and X of his Elements. The algorithm has many theoretical and practical applications. It is a key element of the RSA algorithm. It is used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences (Chinese remainder theorem) or multiplicative inverses of a finite field. It can also be used in the construction of continued fractions, in the Sturm chain method for finding real roots of a polynomial, and in several modern integer factorization algorithms. Finally, it is a basic tool for proving theorems in modern number theory, such as Lagrange's foursquare theorem and the fundamental theorem of arithmetic (unique factorization).
The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. In Sage the greatest common divisor is given by the function, gcd(a,b).
Consider the problem of determining the gcd(252,105). If we reduce the larger number by subtracting the smaller one from it, the gcd does not change (since it divides both terms it must divide the difference):
gcd(252,105) = gcd(252105,105) = gcd(147,105).
Subtract again:
gcd(147,105) = gcd(147105,105) = gcd(42,105).
Now 105 is no longer the smaller number. However, continuing in the same way, we reduce the larger number, now 105, by subtracting the smaller one from it, the gcd is unchanged:
gcd(42,105) = gcd(42,10542) = gcd(42,63).
The first number, 42, is still the smaller one, so again we use it to reduce the larger one:
gcd(42,63) = gcd(42,6342) = gcd(42,21),
and finally:
gcd(42,21) = gcd(4221,21) = gcd(21,21) = 21.
Of course, we can speed up the algorithm by dividing and using the remainder. Then the algorithm has the following steps.
252 = 2*105 + 42
105 = 2*42 + 21
42 = 2*21
Exercise 4. Complete the following function, which implements Euclid's Algorithm using the integer divide. Then test it by evaluating the subsequent block.

1 2 6 21 51 1 2 6 21 51 
The following function is a very straightforward translation of the recursive pseudocode function presented in the Wikipedia article on the Extended Euclidean Algorithm. This algorithm returns $x$ and $y$, the smallest (in absolute value) integer coefficients that satisfy Bezout's identity,
$x*a + y*b = r$
where $a$ and $b$ are given integers and $r$ is their gcd.

2 * 252 + 5 * 105 = 21 21 2 * 252 + 5 * 105 = 21 21 
7 * 1989 + 16 * 867 = 51 51 7 * 1989 + 16 * 867 = 51 51 
If the gcd of $a$ and $b$ is 1, then we say that $a$ and $b$ are coprime (or relatively prime). When $a$ and $b$ are coprime, then Bezout's identity provides some useful information. The identity becomes
$x*a+y*b = 1$,
which means that $x$ is the multiplicative inverse of $a$ mod $b$ and that $y$ is the multiplicative inverse of $b$ mod $a$. This is illustrated in the following block.
9 * 120 + 47 * 23 = 1 1080 mod 23 = 1 1081 mod 120 = 1 9 * 120 + 47 * 23 = 1 1080 mod 23 = 1 1081 mod 120 = 1 
The CalkinWilf Tree was introduced in a 2000 paper by Neil Calkin and Herbert Wilf. It is a binary tree with each node a fraction of the form $a/b$. The root node is $1/1$. For every node, $a/b$, the left child is $a/(a+b)$ and the right child is $(a+b)/b$. Using the same indexing functions that were introduced with the priority queue we can easily store the tree in a onedimensional list.

Exercise 5. Complete the function, Calkin_Wilf, that given $N$, returns a list of the first $N$ nodes CalkinWilf tree (viewed as a complete binary tree, filled in from toptobottom, lefttoright).

Traceback (click to the left of this block for traceback) ... IndexError: list index out of range Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_17.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# * coding: utf8 *\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cHJpbnQgQ2Fsa2luX1dpbGYoNykKcHJpbnQgQ2Fsa2luX1dpbGYoMTUp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in <module> File "/tmp/tmpqcw5zC/___code___.py", line 3, in <module> print Calkin_Wilf(_sage_const_7 ) File "/tmp/tmp7aptmR/___code___.py", line 8, in Calkin_Wilf a = numerator(tree[p]) IndexError: list index out of range 
The following function takes the list from the Calkin_Wilf function and displays it as a tree. Examine the tree carefully to make sure that it is correct.
Traceback (click to the left of this block for traceback) ... IndexError: list index out of range Traceback (most recent call last): while k < N: File "", line 1, in <module> File "/tmp/tmpwqzbKn/___code___.py", line 20, in <module> exec compile(u'CW_tree_display(_sage_const_31 ) File "", line 1, in <module> File "/tmp/tmpwqzbKn/___code___.py", line 4, in CW_tree_display CW = Calkin_Wilf(N) File "/tmp/tmp7aptmR/___code___.py", line 8, in Calkin_Wilf a = numerator(tree[p]) IndexError: list index out of range 
Exercise 6. Examine each row in the tree displayed above and answer the following two questions.

Exercise 7. In the block below list the first 31 numerators returned by your Calkin_Wilf routine. Then in the next line list the first 31 denominators. Is there a pattern connecting the list of numerators to the list of denominators? If so, briefly describe it.

Exercise 8. Complete the code for the recursive function, fusc, which is defined by the following properties:
Then evaluate the subsequent block. Hint, the first 6 values are: 0, 1, 1, 2, 1, 3.
Is there a connection between the sequence returned by the fusc function and the CalkinWilf tree? If so, describe it.

[0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6] [0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6] 
Exercise 9. Is every node in the CalkinWilf tree a fraction that has been reduced to lowest terms? If so, provide the outline of a proof. If not, search for a counterexample and indicate the extent of your search and the results.

Exercise 10. Does every positive rational number occur in the CalkinWilf tree? If you think so, provide the reason(s) that support this conclusion.
Based on your explorations in this and the previous exercise, what do you conclude about the claim that every rational number occurs exactly once in the CalkinWilf tree?

