Every Possible Fraction
December 9, 2014
When I saw this web page a few days ago, I knew it would make a great exercise, simple but fascinating. Starting with x = 1, every fraction in lowest terms is generated by x ′ = 1 / (n − y + 1), where n = ⌊ x ⌋ and y = x − n. The underlying math is known as the Stern-Brocot tree, and has been known since the ancient Greeks, who used terms of the Stern-Brocot tree to design the gear ratios in the Antikythera mechanism.
Your task is to write a program that generates the fractions in lowest terms. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 