So the generating formula creates the top-down left-right sequence of the Calkin-Wilf Tree, which is the binary tree sequence that Prof Baez has kindly noted for us. The general pattern for tree propagation is as follows :

![Pattern](http://aether.co.kr/wp-content/uploads/calkin-wilf1.jpg)

The left child is a fraction less than 1, and the right child is a fraction greater than 1.

So there is an elegant solution to the question whether this every rational in the sequence is reduced found on this [page](https://mathlesstraveled.com/2008/02/06/recounting-the-rationals-part-iv/).

It relies on the fact that the gcd(p,q) = gcd(p,p+q) = gcd(p,p-q) if p>q. Its easy to see why that is since they both have common factors which can be factored out again. But since each generation of children is created via adding the numerator to the denominator, every child will have the same gcd as their parent. And it just so happens that the ultimate ancestor of the whole tree happens to be one so the whole tree has a gcd of 1! See the graphic below:

![Unique](http://aether.co.kr/wp-content/uploads/calkin-wilf3.jpg)

The question of whether the sequence covers the whole positive rationals is also elegantly explained on this [page](https://mathlesstraveled.com/2008/01/24/recounting-the-rationals-part-iii/).

Since we know how to propagate down the tree we can also go back up the tree as long as we differentiate if the rational is > or < 1 i.e. p>q, or q>p. Remember that the left child had a sum in its denominator and is <1. So if q>p then we find its parent simply by subtracting the numerator from the denominator and keeping the numerator. So we can repeat this process until we hit the ultimate ancestor 1/1. So we have found that a random p/q will have a unique path up the binary tree and therefore all positive rationals are covered in the tree. Check out the graphic below:

![Path](http://aether.co.kr/wp-content/uploads/calkin-wilf2.jpg)

The most interesting pattern I found on this sequence is that the Calkin-Wilf tree is the bit reversal permutation of the Stern Brocot tree, which is binary search tree of the positive rationals. It is sort like doing a discrete Fourier transform on Stern Brocot ordered time domain into its frequency domain separating out the even and odd components (in this case p/q>1, p/q<1). It essentially permutes the Stern Brocot tree that is ordered by ordinary metric (in each row) into equivalence classes based on their p-adic distances. So a linear order of 1,2,3,4,5,6,7,8, would get reordered to (((1,5),(3,7)),((2,6),(4,8))). But the neat thing about this is that when we rearrange the Stern Brocot tree, for some reason beyond my comprehension, the denominator gets passed on to the next numbers numerator creating a kind of baton pass wave dance.

There are other nice patterns in this tree, one of which is that the maxima of each row is a Fibonacci number which always happens land on a certain path on the tree.

![Pattern](http://aether.co.kr/wp-content/uploads/calkin-wilf1.jpg)

The left child is a fraction less than 1, and the right child is a fraction greater than 1.

So there is an elegant solution to the question whether this every rational in the sequence is reduced found on this [page](https://mathlesstraveled.com/2008/02/06/recounting-the-rationals-part-iv/).

It relies on the fact that the gcd(p,q) = gcd(p,p+q) = gcd(p,p-q) if p>q. Its easy to see why that is since they both have common factors which can be factored out again. But since each generation of children is created via adding the numerator to the denominator, every child will have the same gcd as their parent. And it just so happens that the ultimate ancestor of the whole tree happens to be one so the whole tree has a gcd of 1! See the graphic below:

![Unique](http://aether.co.kr/wp-content/uploads/calkin-wilf3.jpg)

The question of whether the sequence covers the whole positive rationals is also elegantly explained on this [page](https://mathlesstraveled.com/2008/01/24/recounting-the-rationals-part-iii/).

Since we know how to propagate down the tree we can also go back up the tree as long as we differentiate if the rational is > or < 1 i.e. p>q, or q>p. Remember that the left child had a sum in its denominator and is <1. So if q>p then we find its parent simply by subtracting the numerator from the denominator and keeping the numerator. So we can repeat this process until we hit the ultimate ancestor 1/1. So we have found that a random p/q will have a unique path up the binary tree and therefore all positive rationals are covered in the tree. Check out the graphic below:

![Path](http://aether.co.kr/wp-content/uploads/calkin-wilf2.jpg)

The most interesting pattern I found on this sequence is that the Calkin-Wilf tree is the bit reversal permutation of the Stern Brocot tree, which is binary search tree of the positive rationals. It is sort like doing a discrete Fourier transform on Stern Brocot ordered time domain into its frequency domain separating out the even and odd components (in this case p/q>1, p/q<1). It essentially permutes the Stern Brocot tree that is ordered by ordinary metric (in each row) into equivalence classes based on their p-adic distances. So a linear order of 1,2,3,4,5,6,7,8, would get reordered to (((1,5),(3,7)),((2,6),(4,8))). But the neat thing about this is that when we rearrange the Stern Brocot tree, for some reason beyond my comprehension, the denominator gets passed on to the next numbers numerator creating a kind of baton pass wave dance.

There are other nice patterns in this tree, one of which is that the maxima of each row is a Fibonacci number which always happens land on a certain path on the tree.