 Larry Riddle, Agnes Scott College ## Representing the Heighway Dragon Curve Symbolically

#### Method 1

We consider the Heighway dragon curve as constructed using line segments starting with an initial horizontal segment. Let $$H_n$$ denote the $$n$$th iteration. It consists of $$2^n$$ segments and $$2^n-1$$ corners. To get the next iteration, $$H_{n+1}$$, each of the segments in $$H_n$$ is replaced by two segments at right angles, always alternating the new segments between left and right along the segments of the previous iteration. Each iteration can be represented symbolically by a sequence consisting of the letters R and L. One can imagine moving along the individual segments making up the curve starting at the left endpoint. A 90° corner is labeled R if the curve makes a right turn there, and is labeled L if the curve makes a left turn at that corner. The following image shows the symbolic coding for the first four iterations. This construction can also be described by the following IFS:

 $${f_1}({\bf{x}}) = \left[ {\begin{array}{*{20}{c}} {1/2} & { - 1/2} \\ {1/2} & {1/2} \\ \end{array}} \right]{\bf{x}}$$ scale by $$\frac{1}{{\sqrt 2 }}$$, rotate by 45° $${f_2}({\bf{x}}) = \left[ {\begin{array}{*{20}{c}} { - 1/2} & { - 1/2} \\ {1/2} & { - 1/2} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}{c}} 1 \\ 0 \\ \end{array}} \right]$$ scale by $$\frac{1}{{\sqrt 2 }}$$, rotate by 135°

Notice that in these four examples, the beginning of $$H_{n+1}$$ (shown in green) is the same sequence of letters as $$H_n$$, then followed by an R, which is then followed (in brown) by the sequence $$H_n$$ in reverse order with R and L interchanged. For example, the reverse of $$H_2$$ is LRR, which becomes RLL after interchanging R and L. These are the last 3 letters in $$H_3$$.

This recursive pattern holds for all iterations since $H_{n+1} = f_1(H_n) \cup f_2(H_n)$ as depicted in the following image: The first function in the iterated function system will just rotate $$H_n$$ by 45° (which becomes the green piece in the image above). This will not change the direction of the turn at each corner of $$H_n$$, so the first half of $$H_{n+1}$$ will have the same sequence of turns as $$H_n$$. The second function in the IFS will rotate $$H_n$$ by 135° (the brown piece) and then translate horizontally so that the tail of the brown piece joins the tail of the green piece. The two pieces then form a new corner that has a right turn of 90°, so an R must be added to the end of the sequence from $$H_n$$. But now the brown piece must be traversed backwards from that of the green piece which reverses the sequence of turns in $$H_n$$, and each original right turn in $$H_n$$ will now become a left turn, and vice versa. (The IFS will also scale each piece, but this will not affect the direction of each turn.)

In their 1970 paper, Knuth and Davis expressed this relationship (with slightly different notation) as $$H_{n+1} = H_nR\overline{H_n}$$ where for a sequence $$S$$, $$\overline{S}$$ denotes the sequence obtained from $$S$$ by writing it backwards and interchanging R and L.

Since $$H_4$$ = RRLRRLLRRRLLRLL, we know that $$H_5$$ must start with this sequence of turns and must end with $$H_4$$ backwards (i.e. LLRLLRRRLLRRLRR) but with R and L swapped (i.e. RRLRRLLLRRLLRLL), with an extra R added in the middle. So

$$H_5 = H_4R\overline{H_4}$$ = RRLRRLLRRRLLRLL R RRLRRLLLRRLLRLL

The image below shows $$H_5$$ with each segment colored either Red or bLue based on the sequence above. Following the curve starting at the black dot, each Red segment ends with a turn to the right, and each bLue segment ends with a turn to the left (the last segment is not part of the code, but is colored Red since in the next iteration there would be right turn at the end of this segment). Paying attention to the colors, can you trace the curve from end to end? The curve can be traversed from the left endpoint to the right endpoint in such a way that the curve intersects only at corners and never crosses itself. [Demonstration with $$H_8$$ and $$H_{12}$$]

#### Method 2

Building the code for higher order iterations can be done recursively using the algorithm described above. Fortunately there is another method that can give the code for $$H_n$$ directly. It is based on the following two observations.

Let the turns at the corners of $$H_n$$ be denoted by $$a_i$$ for $$1 \le i \le m$$ and let the turns at the corners of $$H_{n+1}$$ be denoted by $$b_i$$ for $$1 \le i \le 2m+1$$, where $$m=2^n-1$$.

1. The curve always starts with a right turn at the first corner, so $$b_1$$ = R. $$H_{n+1}$$ is obtained by replacing each of the segments in $$H_n$$ with two segments at right angles. These are the odd-numbered corners in $$H_{n+1}$$. Because the new segments are placed along the segments of $$H_n$$ while alternating between the left and right sides, the angles at the new corners alternating between R and L as illustrated in the figure below. Therefore the odd corners are alternately R, L, R, L, R, L, etc.

2. The even corner corresponding to $$b_{2k}$$ in iteration $$H_{n+1}$$ coincides with the corner corresponding to $$a_k$$ in $$H_n$$. The following image shows the four possible orientations for the segments in $$H_n$$ and $$H_{n+1}$$ at this common corner (the direction of the initial segment of $$H_n$$ might actually be horizontal or vertical in the downward direction, but this would not change the relative behavior of the other segments in the four figures.) The important observation is that in each case, $$H_n$$ and $$H_{n+1}$$ both turn in the same direction at this common corner. Therefore $$b_{2k}=a_k$$ for $$1 \le k \le m$$. We know, however, that $$H_{n+1}$$ begins with $$H_n$$ and therefore $$b_k = a_k$$. This means that $$b_{2k} = b_k$$ for $$1 \le k \le m$$.

These two observations provide an algorithm for how to generate the symbolic code for $$H_n$$. For example, here is how it could be done for $$H_4$$. Since $$2^4-1=15$$, there are 8 odd-numbered corners in $$H_4$$.

Write out four alternating pairs of R's and L's, leaving space between them Now fill space 2 with the value in position 1: Fill space 4 with the value in position 2: Fill space 6 with the value in position 3: Fill space 8 with the value in position 4: Fill space 10 with the value in position 5: Fill space 12 with the value in position 6: Fill space 14 with the value in position 7: This is a convenient method to do by hand for small values of $$n$$. For larger iterations, however, it is not difficult to write a short program to generate the code using the two observations above. [Python example]

Try it!
Iteration number (2 to 12)
n =

#### Method 3

The final method gives a way to calculate directly whether the $$r$$th turn is R or L. Write $$r = k2^m$$ where $$k$$ is an odd integer.
• If $$k \text{ mod } 4 = 1$$, then turn right (R)
• If $$k \text{ mod } 4 = 3$$, then turn left (L)
Here is why that works.

If $$r$$ is odd, then $$k=r$$ and $$m=0$$. Since the odd-numbered corners are alternately R, L, R, L, R, L, etc., the R's are in position 1, 5, 9, etc., while the L's are in position 3, 7, 11, etc. The R positions are congruent to 1 mod 4 and the L positions are congruent to 3 mod 4.

If $$r$$ is even where $$r = k2^m$$ and $$k$$ is odd, then by the second observation in method 2, the direction of the turn at corner $$r$$ is the same as the direction of the turn at corner $$k$$ because you can keep dividing the corner number by 2 without changing the direction of the turn. But $$k$$ is odd, so now the same argument as above applies to show that the direction of the turn at corner $$k$$ is determined by the value of $$k \text{ mod } 4$$.

For example, in $$H_{10}$$, which has 2047 corners, the direction at turn 2020 is R because $$2020=505 \cdot 2^2$$ and $$505 \text{ mod } 4 = 1$$.

If $$r$$ is expressed as a binary number, the following binary calculation gives an immediate answer about which way the curve turns: if $$((r \,\& \, -\!r) \lt \lt 1) \; \& \; r = 0$$, then the curve makes a right turn at corner $$r$$, otherwise it makes a left turn.

Here & is the bitwise AND operator and << is the bitwise left shift operator [Explanation]. With the example of r = 2020 given above, we would have (in binary)
 2020 = 11111100100 −2020 = 00000011100 2020 & −2020 = 00000000100 (2020 & −2020) << 1 = 00000001000 ((2020 & −2020) << 1) & 2020 = 00000000000

#### Taking it to the limit

The Heighway dragon is equal to $$\displaystyle \lim_{n \rightarrow \infty} H_n$$. Since each $$H_{n+1}$$ begins with $$H_n$$, it makes sense, as Knuth and Davis remark in their article, to express the Heighway dragon as the infinite sequence of R's and L's obtained as each finite sequence for $$H_n$$ is extended to the limit. Given any particular position in the infinite sequence, method 3 above can be used to determine whether the code in that position is R or L.

Try it!

Position r =

#### References

1. Donald Knuth and Chandler Davis, "Number Representatives and Dragon Curves," Journal of Recreational Mathematics, Vol. 3 (1970), 66-81 and 133-149. Reprinted in Selected Papers on Fun and Game by Donald Knuth, Center for the Study of Language and Information, Stanford University, 2010, pp571-614.
2. Martin Gardiner, "Mathematical Games", Scientific American, Vol. 216, No. 4 (April 1967), 118-120. Reprinted in Mathematical Magic Show, Knopt, New York, 1977.
3. Dragon Curve, Wikipedia