Programming

The Fraction Tree It is possible to build a fraction tree in the following way. Starting with L = 1, on the Lth level of the tree, perform the following steps. 1. Place the fraction 0 1 on the left and 1 0 on the right. 2. Perform the following action L times, between each pair of fractions a1 b1 and a2 b2 on this level, insert the fraction a1+a2 b1+b2 . 3. Index the fractions on this level by starting 0 1 with index 0 and going up to 2L. 4. For each odd index 2i+ 1, your parent index on the line above is 2b i 2 c+ 1. All even indices are discarded from the tree. 1 1 1 2 1 3 1 4 2 5 2 3 3 5 3 4 2 1 3 2 4 3 5 3 3 1 5 2 4 1 It can be proved that every possible fraction eventually appears once and only once in this tree. Input to your program will be a “large” fraction M/N where M and N are large. (You may use the java.BigInteger package if you want.) Output from your program will be the first fraction a b in the tree such that a b ≈ q M N in the following sense: a b must be the first fraction in the tree such that |N a2 − M b2 | < b The output will be two lines, a and then b.