Dave Computes Fibonacci Paths

Recall that a Fibonacci word is formed by concatenating the previous two words in the sequence. We'll start with the one-letter words S and T. We concatenate S + T to get the word ST. We concatenate the last two words T and ST to get TST. We concatenate the last two words ST and TST to get STTST, and so on. As you can see, the lengths of the Fibonacci words are themselves Fibonacci numbers.

S

T

ST

TST

STTST

TSTSTTST

STTSTTSTSTTST

TSTSTTSTSTTSTTSTSTTST

STTSTTSTSTTSTTSTSTTSTSTTSTTSTSTTST

TSTSTTSTSTTSTTSTSTTSTSTTSTTSTSTTSTTSTSTTSTSTTSTTSTSTTST

...

Let's look at the word of length 8:  TSTSTTST. If T stands for TURN, and S stands for STRAIGHT, we can think of these as directions for drawing the following path.

It should be clear S marks places where the path continued straight, while T marks places where the path turned 90 degrees. When T occurs on an odd step (as on steps 1, 3, and 5), the path turns left. When T occurs on an even step (as on step 6), the path turns right. Here's the Fibonacci word of length 55.

TSTSTTSTSTTSTTSTSTTSTSTTSTTSTSTTSTTSTSTTSTSTTSTTSTSTTST

And here's the path generated for this word.

Here's the path for the Fibonacci word of length 1597.

And here's the path for the Fibonacci word of length 121,393.

This is the well known Fibonacci Word Fractal. In the remainder of this post, I'll show other paths I generated by altering the rules.

Here's the path for the 8-letter Fibonacci word again, but this time, turning 120 degrees left or right (instead of 90). We can see that, on step 6, the path meets up with its starting point.

And here's the path for the 34-letter Fibonacci word using 120 degree turns. As you can see from the overlapping numbers, some vertices are visited more than once.

The path for a 55-letter word revisits edges as well as vertices. And sometimes the same vertex is visited with both S and T. In the path for an 89-letter word (below), we can see that sometimes the path encloses both triangles and 9-sided figures (like the one near the center of the image).

Here's the path for the 10,946-letter Fibonacci word.

And here it is again, with all similarly oriented regions shaded.

We can see there's a lot going on in this pattern. Here it is again, colored to show larger structures.

These structures are reminiscent of the ones we saw in a pattern shown in a previous post, and reproduced below.

It turns out, these two aperiodic patterns are intimately related. Recall from that previous post that we learned to construct the "intestinal" pattern above by using Fibonacci triangles joined at vertices--the bold lines in the left image below. The right image shows the complement of that pattern, with bold and thin lines exchanged. And we recognize those bold lines as a portion of the paths created above by Fibonacci words with 120-degree turns.

If we generate a path using 72-degree turns, we get the following (length 10,946):

Now let's start messing with the rules. Suppose we continue straight at T and turn 120 degrees at S, as in the following path of length 8:

For a 10,946-letter Fibonacci word, this new rule generates the following path.

Notice that the path forms a sort of isometric grid, with lines doubled. For example, look at the lines oriented down-and-right. From left to right, we see 1 line, then 2 lines, then 1 line, then 2, then 2, etc., generating the sequence 1212212122121--another Fibonacci word! We see the same effect in the other two directions.

Let's try another rule. Here we go straight on an odd S or even T, and we turn 120 degrees to the right on an even S or odd T.

Here's the path we get for a 6,765-letter Fibonacci word.

Here's another rule. This time, we turn right 120 degrees on any S, go straight on an odd T, and turn left 120 degrees on an even T, as shown here.

Here's the path for a 6,765-letter Fibonacci word.

Back to 90-degree turns. Recall that the Fibonacci word fractal is constructed by turning on T (with the direction depending on whether we're on an odd or even step) and going straight on S. If we turn on S instead of T, we get the following variation on the Fibonacci word fractal (after 1597 steps).

Here is another path using 90-degree turns.

right on odd T and even S (10,946 steps)