Stern-Brocot Tree and Ratios

 



Captions refer to the part-to-part ratio of blue to red units. A jigsaw group of units is made by copying, from the row above it, the two groups between which it will sit (reading left to right) and then by joining them together.  This operation is analogous to calculating the mediant of two fractions by adding numerators and adding denominators. The two upward lines from each group of units lead to its two ‘parent’ groups and darker lines lead to the more distant of the two parents. 

The Stern-Brocot tree generates simple fractions.  The aim is to show that the structure of the Stern-Brocot tree can be reproduced by repeated addition of units without reference to fractions.  In this way the concept ‘one divided by zero’ is obviated in the first row.

Achille Brocot was a watch-maker and the Stern-Brocot tree originated in the problem of how to find the best approximations to ideal gear ratios that were too big to manufacture. Hayes, 2000  

In a similar way, the Calkin Wilf tree can be interpreted as a process of converting part-to-part ratios into part-to-whole ratios and then treating the latter in turn as part-to-part ratios.  For example, 2 : 5 would generate 2 : (5 + 2) = 2 : 7 and (5 + 2) : 5 = 7 : 5. 





Comments

Post a Comment

Popular posts from this blog

Counting fractions

Given a list of fractions, I am looking for a way to identify the n th member of the list without needing to work out all the fractions before the n th one.  Also, given any fraction, I want to be able to say where it appears on the list. I am looking for reduced fractions, which means that  \( \frac{1}{2} \) will appear in my list but I will not see  \( \frac{2}{4} \), \( \frac{3}{6} \) or any others that can be reduced to simpler terms. There are methods to create lists of reduced fractions. In particular: The Stern-Brocot tree.  The Calkin Wilf sequence.  Kepler's method in Harmonices Mundi.  There are methods to locate fractions in these sequences.  Bates, Bunder and Tognetti   presented a method in 2010.   Cut the Knot also discussed binary encoding as a means of locating fractions.  A page on this blog proposes a method that is reasonably simple and intuitive and that yields insight into the structure of fractions.
Read more

Continued Fraction Triangle

Image
This post is about patterns in the calculation of a continued fraction and its reverse and in successive  truncations of a continued fraction. Table 1: calculation of continued fraction (row i) from integers 373 and 135 (row h) and calculation of convergents by successively truncating the continued fraction (upwards, rows g to a).  Column H row h is the greatest common divisor of 373 and 135. Table 2:  reverse continued fraction from Table 1 with successive convergents. DESCRIPTION OF TABLES 1 AND 2 Table 1 is a calculation of continued fraction (row i) from integers 373 and 135 (row h) and calculation of convergents by successively truncating the continued fraction by one term at a time (working upwards, rows g to a).  Column H row i is the greatest common divisor of 373 and 135.  The continued fraction can be interpreted as either [2; 1, 3, 4, 1, 1, 3], which represents  \( \frac{373}{135} \) or [0; 2, 1, 3, 4, 1, 1, 3], which is the inverse \( \frac{135}{373} \). Row g of Table 1 ca
Read more