The Thue-Morse Sequence

28 Oct 2018

Making things even

When I was little I liked (had a compulsion1) to make certain things symmetrically even: if I accidentally brushed my face with my left hand, I might purposefully brush it with my right.

Sometimes left then right wasn’t enough: the right touch had been more recent! As the mental weight of each touch decayed with time, the right touch remained always a little stronger. The fix to this inequity was to tap, brush, or nibble again; this time first right, then left.

Left, then Right; then Right, then Left.


But that wasn’t quite even either! Repeating the opposite pattern helped a bit:


And to address the unfairness of that pattern:


and so on. When I try tapping out this sequence on my desk now I can double the length two more times before having trouble and I think I used to take it further.

Years after I stopped doing this I discovered an entry in the Online Encyclopedia of Integer Sequences by typing it out as ones and zeros: it was the Thue-Morse Sequence! I remember being pretty excited that the thing I had come up with on my own was shared (and a wee bit disappointed that I didn’t get to publish it myself).

More recently it occurred to me to Google for the sequence. Sriharsha Bangaru’s writeup is the best thing I found, covering lots of interesting bits: formalisms, connection to the Koch curve, and its application to equal partitioning. But I found a lot of other posts too. It turns out a lot of people know, and I think have independently discovered, this sequence.

The comments sections of this LiveJournal post and this fun Youtube video by Matt Parker have more reactions like “oh that thing, I thought it was just me!” Here are a few mentions from around the web.

So what?

So I share a mental quirk with some other people. It’s pretty cool that a bunch of humans felt something and wrote it down so they could share it on the internet, but that doesn’t distinguish it from the rest of the human canon about feelings we share like “love” and “ennui” and “don’t you hate it when the toast falls butter side-down.”

It’s the terrific specificity of this shared experience that makes it special. Finding out you share knowledge of a (literally and figuratively) transcendental number you discovered on your own feels more dramatic than finding out other people also have dreams about their teeth falling out. I know more terms in this sequence than I do digits of pi or e. To this day, it feels like my sequence – I taught an embedded device to blink it as a Hello World program last month – but also like a universal truth of the universe.

It’s cool to know something that felt so intensely personal, so singular, is shared by others. It’s like knowing a secret handshake that no one taught you. Like being a mutant and discovering the X-Men, or a wizard raised by muggles discovering Hogwarts, it’s a small piece of that kind of happiness of not being alone. Thanks internet :)

  1. A compulsion is the inexplicable need to perform a repetitive behavior. An obsession is a recurring thought or fear, which might be about what could happen if a compulsion is not observed. For a diagnosis of Obsessive-Compulsive Disorder you look for both. I worked at a psychiatry lab on the imaging side for long enough to know I’m not qualified to say much about a diagnosis like OCD, but it seems important to mention it because many of the people who post online about this sequence identify this way. If you, like I did as a child, feel a compulsion for symmetry, this does not mean you have OCD. ↩︎