Post without words #5, explained

If you stared for a while at the images in my previous post, you probably noticed some patterns, and maybe you even figured out some sort of rule or algorithm behind them. Commenter Yammatak expressed it as “You split it into 4 and put 2 copies of the original on the bottom with the colors inverted and 2 copies on the top but rotated 90 in opposite directions.” Like this:

Yammatak is right: iterating this process does generate exactly the images in my post. As I noted in my response to Yammatak’s comment, however, this is not how I made the images! I only noticed that they could be described using this simple rule after making them.

So, how did I make them? First, I started with the Prouhet-Thue-Morse sequence, which can be defined by

\begin{array}{rcl} T_0 & = & 0 \\ T_n & = & T_{n-1},\overline{T_{n-1}} \end{array}

where the comma denotes concatenation of sequences, and the overbar means to swap zero for one and vice versa. So,

\begin{array}{rcl} T_0 & = & 0 \\ T_1 & = & T_0,\overline{T_0} = 0,1 \\ T_2 & = & T_1,\overline{T_1} = 0,1,1,0 \\ T_3 & = & 0,1,1,0,1,0,0,1 \\ T_4 & = & 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0\end{array}

and so on. This is a really fascinating sequence that shows up all over the place—for more, see Matt Parker’s recent video, or, if you are more academically inclined, this paper by Allouche and Shallit.

In any case, replace each zero with a light blue square, and each 1 with a dark blue square:

Now, take the Hilbert space-filling curve:

and string out the Prouhet-Thue-Morse sequence along it, using light and dark blue squares in place of zeros and ones:

This works out really nicely because both the Prouhet-Thue-Morse sequence and the Hilbert curve naturally organize things in powers of 2. If you think about the recurrence for the Prouhet-Thue-Morse sequence, in terms of replicating and inverting, and the recurrence for the Hilbert curve, in terms of scaled and rotated copies, you can see why you end up with a simple rule like the one Yammatak explained. So in the end, I guess you could say this is a complicated way to describe a simple rule that generates a complicated image!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in pattern, pictures, posts without words, sequences, solutions and tagged , , , , , . Bookmark the permalink.

4 Responses to Post without words #5, explained

  1. Christophe says:

    Cool. I really like the idea. Simple an beautiful !

    Question. Do the L-system given by Yammatak is really the same as your process ? Is there a proof ?

    • Brent says:

      Yes, it is the same. The proof is simple (at least conceptually): the n+1st iteration of the Hilbert curve is formed from 4 copies of the nth iteration, where the first and fourth copies have been rotated by 90 degrees; couple this with the fact that T_{n+2} = T_n, \overline{T_n}, \overline{T_n}, T_n.

  2. Fergal Daly says:

    I remember as a kid (maybe teen, maybe before) seeing how far I could get through the PTM sequence. I never knew it had a name.

Comments are closed.