Inspired


This image is a visual representation of using the Stern-Brocot tree to approximate real numbers.

The Stern-Brocot tree is a way to list all of the positive fractions, once and only once, in lowest terms. Quite a feat. It starts with the "fractions" 0/1 (a true fraction, 0) and 1/0 (not a fraction or even a number, but it works in this context) as bookends (in light gray, below). The first actual row has the fraction 1/1 (shown in green) in between the bookends. In each subsequent row, new fractions are placed between each pair in the row above. The new numerator is the sum of the numerators of the parent fractions and the denominator is the sum of the denominators of the parents (note: this is not the correct way to add fractions). The new fractions are called the mediants of the parents. For example, the 1/2 (in red) comes from adding the 0 from the left bookend + 1 from 1/1, and the 2 comes from 1 from the left bookend + 1 from 1/1. Likewise, 2/1 (in blue) comes from adding 1 + 1 in the numerator and 1 + 0 in the denominator.


Another use for the tree is finding fractions that approximate irrational numbers. The process is to march down the rows of the table, finding the two fractions that bracket the number of interest. As you go further and further down the table, the approximation becomes better and better. For example, consider Φ, which is approximately 1.618. Φ is larger than 1, so in the first row, it is bracketed by 1/1 and 1/0 (which acts like infinity). Then, find the mediant of 1/1 and 1/0, which is 2/1. Compare the mediant with the target number: Φ is smaller than 2, so 2/1 becomes the new higher fraction (and 1/1 stays the lower fraction). The mediant of 1/1 and 2/1 is 3/2, in the third row of the table. Comparing Φ with 3/2, Φ is larger, so 3/2 is the new lower fraction and 2/1 stays the higher fraction. Lather, rinse, repeat for as long as you like. The process is illustrated below, where the red arrow shows about where Φ is, relative to the right half of the tree.


So what does this have to do with the image at the top of the page? At each step of the process, the new mediant is either smaller than or larger than the target number (if the number is irrational). Color a pixel black if the mediant is smaller and white if larger, and you have a column of black or white pixels. Use more columns for more numbers and you have an image. That's what I did for Inspired. The image is centered horizontally on Φ and each row of pixels represents another step in the process (for the image, I started with the bottom row and moved up, instead of moving down as in these examples). The spires in the image come from fractions in the range of the numbers considered. Those with smaller denominators (in lowest terms) will lead to larger spires, where the process stops earlier.