The Dragon Curve, Folding a Path

Definition The Heighway dragon comes from a folding rule. Lay a long strip of paper flat and fold it in half by lifting its right end over onto its left end. Fold the folded strip in half in exactly the same way, and repeat until it has been folded $n$ times, where $n \ge 1$. Then unfold it, open every crease to a right angle and stand the strip on its long edge. Seen from above, the strip is a path of $2^n$ equal segments joined by $2^n - 1$ right-angle turns. As seen from the side of the strip that faced up at the start, each crease is a valley or a mountain, and the strip bends toward that side at every valley and away from it at every mountain. Travel along the path from the left end, which never moved, with the side that faced up at the start turned toward the right of the direction of travel. Then every valley is a right turn, written R, and every mountain is a left turn, written L. Standing the strip with that side turned to the left instead exchanges every R and L and draws the mirror image of the path, which is just as correct, and reading from the other end draws the same path traveled backward. The surprise is that the turns follow a short rule, so no folding is needed. Write $S_n$ for the list of turns after $n$ folds. The first list $S_1$ is the single letter R, and for every $n \ge 1$

where $\widetilde{S_n}$ means $S_n$ read backward with every R changed to L and every L changed to R. As $n$ grows, the paths, shrunk to a common size, approach a limiting curve, which is also called the Heighway dragon or simply the dragon curve. It is named after John Heighway, one of the physicists who studied it in the 1960s.

Definition A turn sequence describes a path made of segments of equal length in which every corner is a right angle. It lists the corners in the order the path meets them, writing R when the direction of travel turns a quarter turn clockwise and L when it turns a quarter turn counterclockwise. A path of $m$ segments has $m - 1$ turns. Once the first segment is drawn, the turn sequence fixes the rest of the path, so two paths with the same turn sequence differ only by a shift, a rotation and a change of segment length. Traveling a path from its other end lists its turns in reverse order with R and L exchanged, because a corner that turns clockwise on the way out turns counterclockwise on the way back. Reflecting a path in a mirror exchanges R and L without changing the order.

Definition Each list $S_{n+1}$ begins with $S_n$, so all the lists are beginnings of one infinite sequence $t_1 t_2 t_3 \ldots$ of letters R and L, called the regular paperfolding sequence. For every $n$ its first $2^n - 1$ terms are $S_n$. Its terms can also be found directly. Write a position $k \ge 1$ as $k = 2^a m$, with $a \ge 0$ a whole number and $m$ odd. Then the term $t_k$ is R when $m$ leaves remainder 1 on division by 4, and L when $m$ leaves remainder 3. Equivalently, the terms in the odd positions 1, 3, 5, and so on alternate R, L, R, L, and the terms in the even positions repeat the whole sequence, $t_{2k} = t_k$ for every $k$. On a strip folded $n + 1$ times, the creases in even positions are made by the first $n$ folds, which is why they repeat the creases of a strip folded $n$ times. The creases in odd positions are made by the last fold. They alternate because every earlier crease turns the strip over, so neighboring sections face opposite ways in the folded stack, while the last fold bends all of them in the same direction.

Definition Draw stage $n$ of the folding path with segments of length 1, starting at $(0, 0)$ along the positive $x$ direction. Unfolding the middle crease turns the second half of stage $n + 1$ a quarter turn counterclockwise about the end of the first half. So if stage $n$ ends at the point $(a, b)$, stage $n + 1$ ends where that quarter turn sends the starting point,

which is $\sqrt{2}$ times as far from the start. Stage $n$ therefore ends at distance $2^{n/2}$ from its start. Now shrink and turn each stage so that it runs from $(0, 0)$ to $(1, 0)$. Its $2^n$ segments then have length $2^{-n/2}$, and stage $n + 1$ comes from stage $n$ by replacing every segment by the two shorter sides of a right isosceles triangle built on that segment, with the right-angle corners placed alternately to the left and to the right of the path, starting on the left. If two consecutive stages are traced at constant speed over the same time, the two tracing points are never farther apart than half a segment of the earlier stage. These distances shrink by the factor $1/\sqrt{2}$ from stage to stage and add up to a finite total, so the paths approach a single limiting curve. This limit is the dragon curve, or Heighway dragon. It is made of two copies of itself, each shrunk by the factor $1/\sqrt{2}$. The first copy runs from $(0, 0)$ to $(\tfrac{1}{2}, \tfrac{1}{2})$ and the second from $(\tfrac{1}{2}, \tfrac{1}{2})$ to $(1, 0)$. The name dragon curve is sometimes used for a whole family of related curves, but the Heighway dragon is not the Lévy C curve. That curve uses the same triangles with every new corner on the same side of the path, and already at its second stage it goes straight on at its middle point instead of turning, so its turns cannot be written with R and L alone.