Category Archives: Computer Science

Thue-Morse Navigating Turtles

Computer Science, Geometry, , , , ,

Here’s a simple rule to generate a pretty sequence of 1s and 0s: Start with the list 1 (just one digit) and repeatedly form a new list by flipping all the bits (1s become 0s and vice versa) and attaching this to the end: $$1 \to 10 \to 1001 \to 10010110 \to 1001011001101001 \to \cdots.$$ For example, to get from 1001 to the next sequence, we swap 1s and 0s to form 0110, and then we join these together to make 10010110. By continuing this process we can make our list longer and longer, and the limiting sequence $$1001011001101001011010011001011001101\cdots$$ is called the Thue-Morse Sequence.

What did I mean by calling this sequence “pretty”? Well, what does this sequence “look like”? One way to visualize it is with a turtle program. Imagine a turtle (let’s call him Leo) walking along the plane, and treat the digits of the Thue-Morse sequence as a list of instructions for the turtle as follows: When Leo sees the digit 1, he steps forward one foot; a 0 tells Leo to turn left by 60 degrees. What does Leo’s path look like? Here are the first 32 instructions he follows:

Turtle Program for the Thue-Morse Sequence
The turtle follows these instructions on the first 32 entries of the Thue-Morse sequence: {1: Step; 0: Turn 60}.

And here are snapshots of his path as he gets farther into the Thue-Morse sequence:

Turtle Program Trajectories for the Thue Morse Sequence: rule 1
Snapshots of the turtle's trajectories after 2^8, 2^10, 2^12, and 2^14 instructions, respectively.

Why did we pick these instructions? What if Leo turns 120 degrees instead of 60 degrees when he sees a 0?

Another Turtle Program for the Thue-Morse Sequence
The turtle follows the Thue-Morse sequence with a slightly different set of instructions: {1: Step; 0: Turn 120}. Shown here after 2^6, 2^8, 2^10, and 2^12 instructions, respectively.

If you zoom out and/or squint a little, these paths are roughly following a famous fractal called the Koch curve. And indeed, the more steps you draw, the closer the resemblance will become (as analyzed in these two papers: [MH2005] and [KZH2008]). But why stop here? What happens if we change the turtle’s instructions even more? I played around with some new rule sets, and these too show how the Koch curve seems innately “programmed” into the structure of the Thue-Morse sequence:

Other Turtle Programs for the Thue-Morse Sequence
Three more pretty examples of the Thue-Morse sequence's "turtle power." In all three cases, the trajectories converge to the Koch curve. Left: {1: (Turn 180, Step); 0: (Turn 60, Step)}, after 2^8 instructions. Middle: {1: (Turn 180, Step); 0: (Turn 120, Step)}, after 2^10 instructions. Right: {1: Turn 180; 0: (Turn 15, Step)}, after 2^10 instructions.

Here’s a final challenge: if the Koch curve and the Thue-Morse sequence are so intimately related, shouldn’t we be able to find some turtle program instructions that trace the Koch curve without “squinting”? Specifically, the Koch curve is usually constructed as the limit of the following sequence of paths, where each iteration is made by stitching together four copies of the previous curve:

The Koch Curve
The Koch curve is constructed as the limit of these paths, where each curve is formed from four (shrunken) copies of the previous curve.

Is there a set of turtle instructions whose path traces exactly these curves? In fact, there is! These instructions work: {1: (Step, Turn 60); 0: Turn 180}.

Voronoi Cells on a Plane

Computer Science, Geometry, , , ,

As a pilot of an (oversimplified) airplane, you may want to know how to communicate with the nearest control tower to receive information on local weather, air traffic, and so on. Each control tower has some region of the map that it “controls,” i.e., where it is closer than any other tower. An example is drawn below. These regions are known as the Voronoi regions (or Voronoi cells) of the points, and the whole diagram is the Voronoi decomposition determined by those points.

Example Voronoi decomposition
The Voronoi diagram of 20 randomly chosen points in a square

For a given set of points, we can imagine the corresponding Voronoi regions as follows: grow disks around the points at the same rate, stopping when they hit each other. A disk collides with other disks exactly when its center ceases to be closest, so these regions are indeed the Voronoi cells.

Generating Voronoi cells by growing circles
The Voronoi cells can be created by growing circles around the points.

Now let’s kick this into third gear—by which I mean the third dimension. In the animation above, suppose that the circles were moving downward over time, producing a cone below each point. By looking at these cones from above, we see exactly the Voronoi regions! Since cones are easy for computers to render, this provides a handy trick for quickly drawing Voronoi decompositions. In fact, this is how I drew all of these images!

Voronoi regions from cones
By placing identical, vertical cones under the points, one sees the corresponding Voronoi regions from directly above.

This construction is not only of theoretical value, but has also been put to good use packaging Ferrero Rocher chocolates:

Voronoi regions in Ferrero Rocher packaging
Voronoi regions in Ferrero Rocher packaging

Who knew these (delicious!) spherical candies were so mathematical?

A “Frac”ing Prime Generator

Computer Science, Number Theory, , ,

Last week we saw a few ways to (try to) generate prime numbers with simple formulas. I will now describe a much more puzzling (and recreational) method. The following numbers specify everything you need: $$\left(\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \right).$$ To run this “game,” the rules are as follows: Start with value \(v = 2\). At each step, find the first fraction \(f\) in the list so that \(v \cdot f\) is an integer, and replace the value \(v\) by this integer. Repeat indefinitely (or until no such \(f\) can be found). The beginning of the computation looks like this:

  1. Start with value \(v = 2\).
  2. The first fraction \(f\) in the list such that \(2\cdot f\) is an integer is \(f=15/2\), so the new value \(v\) is \(2 \cdot 15/2 = 15\).
  3. The first \(f\) in the list with \(15 \cdot f\) an integer is \(f=55/1\), so the new \(v\) is \(15 \cdot 55/1 = 825\).
  4. The first \(f\) with \(825 \cdot f\) an integer is \(29/33\), so set \(v = 825 \cdot 29/33 = 725\).

And so on.

Continuing as above, the list of values looks like 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, … .

But what does this have to do with primes? The list of fractions was carefully constructed so that many powers of 2 will appear, in exactly the following order: $$2^1, 2^2, 2^3, 2^5, 2^7, 2^{11}, 2^{13}, 2^{17}, \ldots .$$ Indeed, except for \(2^1\) (the starting value), any power of two obtained by this process will have a prime exponent, and all primes will appear in this way (in order)! This is a very special property of the chosen list of fractions, and different lists give rise to vastly different output sequences.

In fact, you can think of this procedure as a programming language, where the list of fractions and the starting value constitute your “program.” This language is called FRACTRAN, and both the language and the above prime-enumerating program were designed by John Conway. What else is this language capable of computing? Lots! FRACTRAN can compute anything that modern computers could—but much less efficiently. (In Theoretical Computer Science terminology, FRACTRAN is turing complete.) See the Wikipedia page for more information, as well as an explanation of why the above program works.

All Your Base (Jokes)

Computer Science, Number Theory, , , ,

There’s something unsatisfyingly arbitrary about the number 10. When we write numbers, e.g. 1729, our notation means that we have 1 thousand (\(10^3\)), 7 hundreds (\(10^2\)), 2 tens (\(10^1\)), and 9 ones (\(10^0\)), so the number 10 is ingrained in our very writing system. And it’s not just the Arabic numeral system: Roman numerals also organize themselves around powers of 10 (such as I=1, X=10, C=100, etc.). But why 10? (Other than the fact that we usually have 10 fingers and 10 toes [why not 20 instead?].)

Our “decimal” system centers around powers of 10, but there are other equally useful systems based on other numbers. For example, we could use sums of powers of 2, and instead of needing 10 digits (0,1,…,9) we can use just 2, namely 0 and 1. For example, the number 1101 in base 2 means \(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\), also known as 13 in base 10. This may seem inefficient, since we need more digits (or, more correctly, “bits” in the binary setting) to express the same value, but it has many benefits. Each bit has only 2 choices, and can therefore be represented by a pair of opposites such as “on/off” (e.g. in circuits) or the two magnetic polarities. The latter is how hard drive disks store information (in binary!), which is one reason this system is beloved by computer scientists. It also allows for jokes like this: “There are 10 types of people in the world: those that understand binary, and those that don’t.”

Another common base is Hexadecimal, using powers of 16 with digits 0,…,9,A,B,C,D,E,F. (A hexadecimal digit is sometimes called a “nibble”.) It is common to prefix a hexadecimal number with “0x”, so 0x3B7 means \(3 \cdot 16^2 + 11 \cdot 16 + 7 = 951\) in decimal. It also makes the phrase “I see 0xDEAD people” perfectly reasonable (how many is that?).

But there are more possibilities still! For example, the octal system uses powers of 8 and (octal) digits 0,…,7. With this we can prove Christmas and Halloween are really the same holiday: indeed, Dec 25 = Oct 31. And don’t miss the octal system’s cameo in Tom Lehrer’s New Math song.

The possibilities are endless! We can use base \(n\) for any positive integer \(n>1\) in similar ways, but we can also use negative \(n\) as well! (My favorite is base -4.) If you want to go ever further, think about what base \((1+\sqrt{5})/2\) (a.k.a. phinary) would look like! Or the related bases Fibonacci and NegaFibonacci!