# Calkin-Wilf Fractals

Suppose we have two natural numbers $i,j$. Define a sequence $a_0 = i, a_1 = j$ and $a_n = |a_{n-1} - a_{n-2}|$. That is, we start with two initial values, and repeatedly subtract the smallest value from the largest value. Since $i,j \geq 0$, we know that $a_n \geq 0$ for all $n$.

Eventually, we will reach the cycle $\ldots 1, 1, 0, 1, 1, 0 \ldots$ no matter our choice of $i,j$ (to see why, consider the termination function $\mu(i,j)=i+j$ and the invariant that any term must be positive).

Define $\text{chainLength}(i,j) = \text{largest } n \text{ such that } a_n \notin \{1, 0\}$

We can now make pretty pictures. For each pixel $(x,y)$ color pixel by $\text{chainLength}(x,y)$ which can be calculated using a simple recursive procedure:

int chainLength(int x, int y){
if(x == y || x==0 || y==0)
return 0;
if(x>y)
return 1+chainLength(x-y,y);
else
return 1+chainLength(x,y-x);
} Generated using the DELTA library.

### Connection to Calkin-Wilf trees

The Calkin-Wilf tree is an infinite binary recursive tree, where the root node is defined as $1/1$, and every node $a/b$ has a left child $\dfrac{a+b}{b}$ and right child $\dfrac{a}{a+b}$. The Calkin-Wilf tree is useful because it allows us to define a bijection between the natural numbers and the rational numbers, which can be used to show that the rational numbers are a countably infinite set.

Notice that if a node $x/y$ is a left child, then $x>y$, and if it’s a right child then $y > x$. This allows us to determine the parent node of a given node.

If for a given node $x>y$ then we know it was the left child of its parent. So we know its parent is $(x-y) / y$. Similarly, if $y>x$, then its parent is $x/(y-x)$. Notice that at each step, we subtract the smaller number from the larger number, and we terminate the procedure when we reach the fraction $1/1$.

Going back to $a_n$, we could interpret a pixel $(x,y)$ as the rational number $x/y$. The recursive sequence $\text{chainLength}(x,y)$ would then be equivalent to the depth of the node $latex x/y$ in the Calkin-Wilf tree.

Keep in mind that the Calkin-Wilf tree only contains rational numbers in the lowest common term, so the node $2/2$ does not exist in the Calkin-Wilf tree. To circumvent this issue, we convert our input node to the equivalent rational number in lowest common terms.

## 2 thoughts on “Calkin-Wilf Fractals”

1. j2kun says:

This image reminds me of the patterns you see when you drive next to a farm field that arranges its crops in rows with stakes. As you drive by, if you look straight down the middle you see a big column where the gap between the rows is, and if you look off to the side a little bit you see fainter column, but still in a straight line formed by the gaps between stakes along various diagonals. Basically, the deeper in the Calkin-Wilf tree the angle of your gaze is, the fainter the column appears. Because only integer values are plotted, and because you’re driving by and it sort of blurs your vision, you see the same picture plotted in your post.

Whenever I drive by such a field, I feel compelled to tell everyone I’m driving with “Look! You can see the rationals! The rationals!” Sadly, I’ve never been able to find a video online that demonstrates this phenomenon, and my phone’s camera has too slow of a frame rate.

1. ssodelta says:

Really interesting observation. Thanks for sharing.