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);
 }

calkinwilf

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}.

 

capture

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.

Advertisements

2 thoughts on “Calkin-Wilf Fractals

  1. 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.

Comment on this article

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s