# Thue-Morse-igami

Here’s a simple origami experiment to try. Start with a long strip of paper with different colors on the two sides—e.g., Orange (O) on one side, Indigo (I) on the other. Now fold the strip in quarters to form a flat “S-shape” as illustrated here (creases are drawn slightly rounded for ease of viewing):

As you look through the four layers from top to bottom, write down the colors you encounter, in order: the first layer shows Indigo (I), the second layer has Orange (O), and so on. The full order is IOOI, which looks suspiciously like the start of the Thue-Morse sequence. (This sequence was introduced last week.)

To continue the experiment, treat this figure as a single strip and fold the same flat S-shape again. There will be 16 layers down the middle:

Sure enough, the order of colors encountered is IOOI OIIO OIIO IOOI, which is the first 16 digits of the Thue-Morse sequence. This pattern will continue forever (or at least until the paper gets too thick to fold): every time you fold another S-shape, you quadruple the number of digits of the Thue-Morse sequence (can you see why?). Try to fold a third iteration! It looks like this (click for larger image):

But wait, there’s more! Now that we have these creased strips, what happens when we unfold them? Specifically, follow the existing creases and lay out the strips so that each crease makes a 90-degree angle. What shapes do we get? Surprisingly, they exactly fill triangular grids of squares:

Can you figure out why this pattern continues?

There are quite a few beautifully symmetric dates that present themselves this month, including 11/1/11, 11/02/2011, 11/05/2011 (use a mirror!), 11/11/11, and 11/22/11. In honor of this phenomenon, I want to say a few words about palindromes, which are simply things that read the same backwards as forwards. A few famous examples include “racecar,” “Never odd or even,” “I prefer pi”, “Dr. Awkward”, “Aibohphobia” (which means fear of palindromes [I didn’t make this up!]), “Go hang a salami; I’m a lasagna hog!”, or if you read by word instead of by letter, “Blessed are they that believe that they are blessed.”

If we consider digits instead of letters or words, then numbers such as 676, 100020001, and 12345678987654321 are palindromes. These are in fact quite special palindromes, as they are all squares of integers: $$26^2 = 676$$, $$111111111^2 = 12345678987654321$$, and $$10001^2 = 100020001$$. Are there infinitely many palindromic squares? Yes: the last example above hints that $$10\ldots01^2 = 10\ldots020\ldots01$$ for however many 0s you put in the middle. By contrast, if we ask for $$n^5$$ to be palindromic (or any higher power), then no solutions are currently known!

You might ask for other types of palindromic numbers, such as palindromic primes. A few examples include 7 (this is a palindrome!), 101, 19391, and 1000000008000000001. Are there infinitely many? We don’t know. But the largest palindromic prime currently known is $$10^{200000} + 47960506974 \cdot 10^{99995} + 1$$, according to Wikipedia.

For one more game, here’s a way to make palindromes out of non-palindromes. Start with a non-palindrome, like 86, and keep adding it to its reversal until you get a palindrome: e.g., 86+68 = 154, 154+451 = 605, and 605+506 = 1111, which is a palindrome. How quickly will this terminate? Well, try starting with 89 and see how long it takes! (Answer: it finally stops at a 13-digit palindrome.) But surely it always terminates eventually, right? Surprisingly, the answer to this question is currently unknown. In fact, it is unknown if the sequence starting at 196 ever finds a palindrome!

Finally, if you still want more to think about, try repeating this entire discussion in another base, e.g. base 2. Good luck!