While trawling Wikipedia for fun¹, I got onto the topic of countable infinities. Saw an article on proofs for the rational numbers being countably infinite, which lead to this article on Calkin-Wilf trees. It’s a tree of rational numbers as fractions, rooted at 1. The steps for generation are so simple you could explain it to a 7 year old.

Consider a fraction in its simplest terms, \(\frac{a}{b}\), as a node. Its two children are simply the fractions \(\frac{a}{a+b}\) and \(\frac{a+b}{b}\). You can prove that by doing this process forever over all nodes the numbers generated cover all the rationals, and that each node can be encoded in a distinct natural number (hence the rationals are countably infinite).

I made a cute little visualiser for it in Raylib which presents a number line. Each node is presented on the number line, with the bounds being the leftmost and rightmost node of the tree (provably the largest and smallest fraction made). It’s single threaded (so far) and does an admirable job at it. The green node represents the current node that is being used to generate two new nodes, these new nodes being highlighted in blue.

Check it out on my private git instance or on GitHub. To build you’ll need a C++ compiler and Raylib.