Today I’d like to continue my exposition of the paper “Recounting the Rationals”, which I introduced in a previous post. Recall that our goal is to come up with a “nice” list of the positive rational numbers — where by a “nice” list we mean one which:
- is easy to describe,
- includes every rational number,
- exactly once,
- in lowest terms,
- at a finite index.
Sounds like a pretty tall order! But it’s possible, as Calkin and Wilf show. So, without further ado… did you know that fractions grow on trees? Sure they do! Here’s one:
This is a tree of fractions defined by the following simple rules:
- The fraction at the top (the “root”) of the tree is 1/1.
- Each fraction in the tree has two “children” (that is, fractions underneath it connected by “branches”): to the left is ; to the right is .
For example, starting at the top of the tree, we have , so rule 2 says that the left child should be , and the right child should be . Likewise, the children of are and , and so on.
Pretty simple, right? The picture above only shows the first four levels of the tree, but it’s clear how to continue extending the tree downwards as far as you’d like (for example, the first two rationals on the next level are 1/5 and 5/4). Now, guess what?
- Every positive rational number occurs somewhere in this tree.
- There are no duplicates: each rational occurs exactly once.
- Every rational in the tree is in lowest terms.
- If you list out the rationals in this tree in order by level (that is, 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4…), the denominator of each rational in the list is equal to the numerator of the next.
- The nth integer in the list of denominators (1, 2, 1, 3, 2, 3, 1, 4, 3, 5, …) is the number of hyperbinary representations of n, that is, the number of ways to write n as a sum of powers of two, where at most two copies of each power of two are allowed.
Wow! What an amazing tree. And all that just from those two simple rules! It should be clear that this is an answer to our original goal: just listing the rationals in the tree level-by-level gives us a list of the positive rationals with all the properties we were hoping for. But there’s a lot more interesting stuff here as well. Next time I’ll start talking about why each of these properties is true — but in the meantime, you may want to try figuring some of them out for yourself! They are all consequences of the two simple rules we used to define the tree.
(Hint for #1, #2, and #3: rule 2 tells us how to move down the tree, but with a little cleverness, you should be able to figure out how to move up the tree as well. For example, assuming that 43/19 occurs somewhere in the tree, rule 2 tells us that 43/62 and 62/19 are below it; but can you figure out what fraction must be above it?)