# On the Boundary of the Harter-Heighway dragon curve

H. A. Verrill<EMAIL_ADDRESS>
###### Abstract.

In this article we apply an L-system to prove a recurrence formula for the
length of the boundary of iterands $\mathcal{C}_{n}$ of the well known Harter-
Heighway dragon curve, a space filling curve with fractal boundary. This leads
to finding formulas for related sequences of certain binary strings and
ternary matrices. This proves some long standing conjectures for the
recurrence relation for the number of terms in the boundary of the dragon
curve, first stated in unpublished work Daykin and Tucker from 1975 [3].

##  1\. Introduction

This article proves some results about two sequences, which count the number
of components on the left and right sides of the iterands of the Harter-
Heighway dragon. The sequences appear in [7] as sequences A227036 and A203175,
but formulas given there are conjectural. We provide proofs of the formulas,
which give the sequences in terms of generating function, appearing in [8].

The Harter-Heighway dragon curve, also known as the Heighway dragon, or the
dragon curve was discovered in 1967 by John Heighway and William Harter [9],
[5, 1.5]. It is a fascinating curve, since it is plane-filling and has a
fractal boundary. There are many variations on this curve. See e.g., [4], [2].
This curve, which we refer to as $\mathcal{C}_{\infty}$, is given as the limit
of a sequence of curves, $\mathcal{C}_{n}$ for non-negative integers $n$. The
curve $\mathcal{C}_{n}$ is formed of $2^{n}$ equal length line segments, which
we also will refer to as the edges, of $\mathcal{C}_{n}$, with a $90^{\circ}$
angle between each edge. The curves can be described in various ways, as
follows.

###  1.1. Construction (A): paper folding

The Harter-Heighway curve was first obtained by repeatedly folding a strip of
paper in half $n$ times, and then opening out all the folds to have angle
$90^{\circ}$. The first few cases are shown in Figure 1.

AAB+AB++A-B

Figure 1. Iterates $\mathcal{C}_{0}$ to $\mathcal{C}_{6}$ of Heighway’s dragon
curve.

###  1.2. Construction (B): alternating triangles

The dragon curve may be described by setting $\mathcal{C}_{0}$ to be a unit
line. Then $\mathcal{C}_{n}$ is obtained from $\mathcal{C}_{n-1}$ as follows.
Place right angle isosceles triangles on each edge of $\mathcal{C}_{n-1}$,
with hypotenuse along the edge, with the triangles on alternating sides of the
curve. Then remove the edges of the original curve, as shown in Figure 1,
where $\mathcal{C}_{n-1}$ is shown in gray, under $\mathcal{C}_{n}$ in black,
so the triangles are formed with two black sides, and a gray hypotenuse.

###  1.3. Construction (C): L-systems

Another method of describing the curves $\mathcal{C}_{n}$ is by the use of
turtle geometry [1] and L-systems [6]. This is the method used in this
article.

An L-system $\mathcal{L}=(\Omega,A,P)$ is a rewriting system, defined to be a
triple, consisting of an alphabet of symbols, $\Omega$; a starting symbol
$A\in\Omega^{*}$, called an axiom; and a function
$P:\Omega\rightarrow\Omega^{*}$, from $\Omega$ to the set $\Omega^{*}$ of of
finite length words with letters in $\Omega$. This induces a function
$P:\Omega^{*}\rightarrow\Omega^{*}$; each letter $x$ of a word in $\Omega^{*}$
is replaced by $P(x)$. In the case of the Heighway dragon, we have
$\Omega=\\{A,B,+,-\\}$, the axiom is $A$, and the function is given by

$P(A)=A+B,P(B)=A-B,P(+)=+,P(-)=-.$

The curve $\mathcal{C}_{n}$ is defined to be the path corresponding to the
word $P^{n}(A)$, by following the letters of $P^{n}(A)$ as instructions for
building a curve according to a turtle geometry construction [1], with the
symbols of $\Omega$ interpreted as

$A$ | make a horizontal unit move
---|---
$B$ | make a vertical unit move
$+$ | turn $90^{\circ}$ clockwise (no move)
$-$ | turn $90^{\circ}$ counterclockwise (no move)

For example, labels in $\Omega$ are drawn on $\mathcal{C}_{n}$ for $n=0,1,2$
in Figure 1.

###  1.4. The L-system for the boundary of $\mathcal{C}_{n}$.

In [10], it is shown that the boundary of the curve $\mathcal{C}_{n}$, or more
accurately, the boundary of a polyomino $\mathcal{S}_{n}$ containing
$\mathcal{C}_{n}$, can be described by an L-system. The polyomino
$\mathcal{S}_{n}$ is defined to be the union of a collection of squares, each
having diagonal one edge of $\mathcal{C}_{n}$, as shown in Figure 2.

The L-system $\mathcal{L}_{1}=(\Omega_{1},Rr,P_{1})$ for the boundary of
$\mathcal{S}_{n}$ is given by taking
$\Omega=\\{{\texttt{R}},{\texttt{r}},{\texttt{L}},{\texttt{l}},{\texttt{S}},{\texttt{s}}\\}$,
with $P_{1}$ given by

(1)
${\texttt{R}}\mapsto{\texttt{R}}{\texttt{r}},\rule{28.45274pt}{0.0pt}{\texttt{r}}\mapsto{\texttt{S}},\rule{28.45274pt}{0.0pt}{\texttt{L}}\mapsto{\texttt{S}},\rule{28.45274pt}{0.0pt}{\texttt{l}}\mapsto{\texttt{L}}{\texttt{l}},\rule{28.45274pt}{0.0pt}{\texttt{S}}\mapsto{\texttt{R}}{\texttt{l}},\rule{28.45274pt}{0.0pt}{\texttt{s}}\mapsto{\texttt{L}}{\texttt{r}}.$

We consider an element $(x,y)$ of $\mathbb{Z}^{2}$ to be even or odd according
to whether the parity of $x+y$ is even or odd. Each symbol of $\Omega_{1}$
corresponds to a path element in the turtle geometry sense, which consists of
(1) starting from a point $(x,y)\in\mathbb{Z}^{2}$, a diagonal movement of
length $1/\sqrt{2}$, continuing in an already specified direction, (2) no
turn, or a turn of $90^{\circ}$ left or right (3) another diagonal movement of
length $1/\sqrt{2}$, resulting in the path which ends at one of the eight
neighbouring points of $\mathbf{Z}^{2}$, i.e., $(x+\epsilon,y+\delta)$ for
$\epsilon,\delta\in\\{-1,0,1\\}$, not both zero. Additional positional
information gives the parity of the starting vertex. The symbols of
$\Omega_{1}$ correspond to two halves of an edge of $\mathcal{S}_{n}$, rather
than straight line edge segments in the case of $\mathcal{C}_{n}$ and letters
in $\Omega$. The direction of turn, or lack of turn, for each symbol, and the
starting parities, are as follows:

R | right turn in the middle of the path, starting point even
---|---
r | right turn in the middle of the path, starting point odd
L | left turn in the middle of the path, starting point even
l | left turn in the middle of the path, starting point odd
S | no turn in the middle of the path, starting point even
s | no turn in the middle of the path, starting point odd

Figure 2 illustrates the relationship between $\mathcal{C}_{n}$ and
$\mathcal{S}_{n}$. In the figure, in passing from $\mathcal{C}_{n}$ to
$\mathcal{S}_{n+1}$, the unit lengths are drawn scaled down by a factor of
$\sqrt{2}$, and the unit grid rotates by $45^{\circ}$ counterclockwise. The
starting point is always $(0,0)$, which is even. The parity of the vertices of
the grid through which $\mathcal{C}_{n}$ and the boundary of $\mathcal{S}_{n}$
passes are marked by black and white dots for even and odd vertices
respectively. For example, the left boundary of $\mathcal{S}_{4}$ is described
by the word RrSRlRrLl.

RLRrSRlRrSRrSRlRrLrRrSRlRrLl Figure 2. Iterates of the boundary of
$\mathcal{S}_{n}$, for $n=0$ to $5$ and $8$. The left boundary is in blue, the
right boundary is in red, and the curve $\mathcal{C}_{n}$ is in gray. The red
and blue curves together form the boundary of the polyomino $\mathcal{S}_{n}$.

In [10] it is shown that this construction produces a self-avoiding
description of the boundary of $\mathcal{S}_{n}$. Thus the number of edges of
$\mathcal{S}_{n}$ is equal to the number of letters in
$P^{n}({\texttt{R}}{\texttt{r}})$. We also write $||w||$ to mean the number of
letters in $w$ for $w$ a word with letters in some alphabet.

The L-system $\mathcal{L}_{1}$ gives a sequence of words
$P^{n}({\texttt{R}}{\texttt{r}})$ describing the complete boundary of
$\mathcal{S}_{n}$. However, since $\mathcal{C}_{n}$ is a curve with different
start and end points, it is considered to have two sides, a left and right
side. So we also consider the curves defined by the L-systems
$\mathcal{L}_{L}=(\Omega_{1},{\texttt{R}},P_{1})$ and
$\mathcal{L}_{R}=(\Omega_{1},{\texttt{L}},P_{1})$, which describe the left and
right boundaries of $\mathcal{S}_{n}$ respectively.

In this paper we consider the boundary of the curves to be the boundary of the
polyomino, $\mathcal{S}_{n}$. In the limit as $n$ tends to infinity, the
shapes $\mathcal{S}_{n}$ and $\mathcal{C}_{n}$ are the same. However, the
actual unit length of the boundary is different for these two curves. The
difference between the two boundaries can be observed in Figure 2, where the
gray curve is $\mathcal{C}_{n}$, and the red curve the boundary of
$\mathcal{S}_{n}$.

##  2\. The left side of the Heighway dragon $\mathcal{C}_{n}$

Given the L-system description of the boundary (1), we can prove the following
result, which has been a long standing conjecture on the length of the
boundary of the Heighway dragon, a sequence starting $2,4,8,16,28,\dots$, [7,
A227036].

######  Theorem 1.

The length of the boundary of the Heighway dragon curve $\mathcal{C}_{n}$,
that is, the number of horizontal and vertical line segments on the left side
of the curve $\mathcal{C}_{n}$, is equal to the coefficients of the expansion
of the Taylor series about $x=0$ of

(2)
$\frac{2(1+x^{2})}{(1-x)(1-x-2x^{3})}=\sum_{n=0}^{\infty}a_{n}x^{n}=2+4x+8x^{2}+16x^{3}+28x^{4}+48x^{5}+84x^{6}+\cdots.$

###### Proof.

For ${\texttt{w}}\in\Omega_{1}^{*}$ and $\texttt{X}\in\Omega_{1}$ let
$a_{\texttt{X}}$ denote the number of times X occurs in w. Set

$v({\texttt{w}}):=(a_{{\texttt{R}}},a_{{\texttt{r}}},a_{{\texttt{L}}},a_{\l},a_{{\texttt{S}}}),$

which gives a count of the number of times each letter of $\Omega_{1}$ occurs
in w. Note that we do not include $a_{{\texttt{s}}}$ since it is not in the
image of any element of $\Omega_{1}$ under the action of $P_{1}$, where
$P_{1}$ is the map corresponding to the L-system for the boundary of the
polyomino containing the Harter-Heighway dragon curve, as in 1. Define a
matrix $M$, with columns $v(P(\texttt{X}))$ for
${\texttt{X}}={\texttt{R}},{\texttt{r}},{\texttt{L}},\l,{\texttt{S}},{\texttt{s}}$,
so that

$v(P({\texttt{w}}))=Mv({\texttt{w}}).$

We have

(3) $M=\begin{pmatrix}1&0&0&0&1\\\ 1&0&0&0&0\\\ 0&0&0&1&0\\\ 0&0&0&1&1\\\
0&1&1&0&0\end{pmatrix}.$

Note that the left side of $\mathcal{S}_{0}$ corresponds to the word R, as
illustrated in Figure 2. Since $M(v({\texttt{w}}))$ counts the occurrences of
each letter in $P({\texttt{w}})$, we have that the components of
$M^{n}(v({\texttt{R}}))$ count the number of occurrences of each letter of
$\Omega_{1}$. The total number of edges of the left boundary of
$\mathcal{P}_{n}$ is thus given by the sum of these components, i.e., since
$v({\texttt{R}})=(1,0,0,0,0)$, the value

$(1,1,1,1,1)M^{n}(1,0,0,0,0)^{T}.$

Examining the relationship between the curve $\mathcal{C}_{n}$ and the
polyomino $\mathcal{S}_{n}$, shown in Figure 2, we see that we have a
correspondence:

segment in left side of $\mathcal{S}_{n}$ |  |  A or B segment in left side boundary of $\mathcal{C}_{n}$
---|---|---
R or r | $\rightarrow$ | $1$
S or s | $\rightarrow$ | $2$
L or l | $\rightarrow$ |  $3$.

Therefore, given that our L-system gives us the matrix $M:=M_{P_{1}}$ in (3),
we must have that the number of A and B segments comprising the left boundary
of $\mathcal{C}_{n}$ is given by

$b_{n}:=(1,1,3,3,2)M_{P_{1}}^{n}(1,0,0,0,0)^{T}.$

We compute that the first few terms of this sequence are $1,2,4,8,16,28$. The
characteristic polynomial of $M$ is

$x^{5}-2x^{4}+x^{3}-2x^{2}+2x=x(x-1)(x^{3}-x^{2}-2).$

So we have

(4)
$\begin{array}[]{ll}0&=(1,1,3,3,2)(M^{5+n}-2M^{4+n}+M^{3+n}-2M^{2+n}+2M^{n+1})(1,0,0,0,0)^{T}\\\
&=b_{n+5}-2b_{n+4}+b_{n+3}-2b_{n+2}+2b_{n+1}\end{array}$

from which we obtain, for $n\geq 5$ the relationship

(5) $b_{n}=2b_{n-1}-b_{n-2}+2b_{n-3}-2b_{n-4}.$

Now we turn to the Taylor series. With the $a_{n}$ as in (14), and $a_{n}=0$
for $n<0$, we have

$\displaystyle 2(1+x^{2})$
$\displaystyle=\sum_{n=0}^{\infty}a_{n}(1-x)(1-x-2x^{3})x^{n}$
$\displaystyle=\sum_{n=0}^{\infty}a_{n}(2x^{4}-2x^{3}+x^{2}-2x+1)x^{n}$
$\displaystyle=\sum_{n=4}^{\infty}(2a_{n-4}-2a_{n-3}+a_{n-2}-2a_{n-1}+a_{n})x^{n}.$

Therefore, equating coefficients of $x^{n}$, we have

$\displaystyle 2$ $\displaystyle=a_{0}(n=0)$ $\displaystyle 0$
$\displaystyle=-2a_{0}+a_{1}(n=1)$ $\displaystyle 2$
$\displaystyle=a_{0}-2a_{1}+a_{2}(n=2)$ $\displaystyle 0$
$\displaystyle=2a_{n-4}-2a_{n-3}+a_{n-2}-2a_{n-1}+a_{n}(n\geq 3).$

So, we have that the $a_{n}$ satisfy a recurrence relation,

(6) $a_{n}=2a_{n-1}-a_{n-2}+2a_{n-3}-2a_{n-4}$

with the initial terms given by

$\displaystyle a_{n}$ $\displaystyle=0\text{ for }n<0$ $\displaystyle a_{0}$
$\displaystyle=2$ $\displaystyle a_{1}$ $\displaystyle=4$ $\displaystyle
a_{2}$ $\displaystyle=8$ $\displaystyle a_{3}$ $\displaystyle=16$

Comparing equations (5) and (6) we see that the the two sequences satisfy the
same recurrence relation. Also the first few terms are the same, up to an
offset, with $a_{n}=b_{n+1}$. Therefore, the two sequences are equal (up to
the offset). ∎

##  3\. Right side boundary of $\mathcal{S}_{n}$ and A203175.

In this section we discuss the number of edges of the right side boundary of
$\mathcal{S}_{n}$, and find that this is the same as the sequence [7,
A203175]. In [7, A203175], this sequence has several conjectured descriptions,
which with our L-system $(\Omega_{1},{\texttt{R}},P_{1})$ from Section 1.4 can
now be proved. We will consider each description in turn, and show that in
each case we have the same recurrence relation satisfied, and the same first
few terms, so the sequences are the same.

###  3.1. Right side boundary of $\mathcal{S}_{n}$

In the notation of Section 1.3, the right side of the boundary of the
polyomino $\mathcal{S}_{n}$ is described by the word
$P_{1}^{n}({\texttt{L}})$, for $n\geq 0$. We define a sequence

(7) $a_{n}=|P_{1}^{n}({\texttt{L}})|,$

which by [10] counts the length of the right side of the boundary of
$\mathcal{S}_{n}$. The first few words $P_{1}^{n}({\texttt{L}})$ are
${\texttt{L}},{\texttt{S}},{\texttt{R}}{\texttt{l}},{\texttt{R}}{\texttt{r}}{\texttt{L}}{\texttt{r}},{\texttt{R}}{\texttt{r}}{\texttt{S}}{\texttt{S}}{\texttt{L}}{\texttt{l}},{\texttt{R}}{\texttt{r}}{\texttt{S}}{\texttt{R}}{\texttt{l}}{\texttt{R}}\l{\texttt{S}}{\texttt{L}}{\texttt{l}}$,
corresponding to the red (lower) sides of the polyominos in Figure 2. So the
first few terms of the sequence $a_{n}$ are

(8) $1,1,2,4,6,10.$

######  Theorem 2.

The length of the right side boundary of the polyomino $\mathcal{S}_{n}$,
containing the Harter-Heighway dragon curve $\mathcal{C}_{n}$ is given by the
sequence $a_{n}$ with

(9) $\begin{array}[]{ll}&a_{n}=a_{n-1}+2a_{n-3}\text{ for }n\geq 4\\\
&a_{0}=1,\>\>a_{1}=1,\>\>a_{2}=2.\end{array}$

###### Proof.

As in the proof of Theorem 1, there is a matrix $M$, given by (3) such that
$M^{n}(v({\texttt{L}}))$ counts the number of each kind of right boundary unit
of $\mathcal{S}_{n}$. Since $v({\texttt{L}})=(0,0,1,0,0)$, the total number of
right edges is

(10) $a_{n}=(1,1,1,1,1)M^{n}(0,0,1,0,0)^{T}.$

Note that $P_{1}$ in (1) is invariant under switching
${\texttt{L}}\leftrightarrow{\texttt{r}}$,
${\texttt{R}}\leftrightarrow{\texttt{l}}$ (in domain and image), which
corresponds to conjugating $M$ by the permutation matrix

(11) $P=\begin{pmatrix}0&0&0&1&0\\\ 0&0&1&0&0\\\ 0&1&0&0&0\\\ 1&0&0&0&0\\\
0&0&0&0&1\end{pmatrix},$

i.e., $PMP=M$, and so we also have

$\displaystyle|P_{1}^{n}({\texttt{r}})|$
$\displaystyle=(1,1,1,1,1)M^{n}(0,1,0,0,0)^{T}=(1,1,1,1,1)PM^{n}P(0,1,0,0,0)^{T}$
$\displaystyle=(1,1,1,1,1)M^{n}(0,0,1,0,0)^{T}=a_{n}=|P_{1}^{n}({\texttt{L}})|.$

So we can write

$a_{n}=|P_{1}^{n}({\texttt{L}})|+|P_{1}^{n}({\texttt{r}})|=(1,1,1,1,1)M^{n}(0,1,1,0,0)^{T}.$

Now notice that

$M^{3}-M^{2}-2I=\begin{pmatrix}-1&0&0&1&0\\\ 0&-1&1&0&0\\\ 0&1&-1&0&0\\\
1&0&0&-1&0\\\ 0&0&0&0&0\end{pmatrix},$

and that $(0,1,1,0,0)=v({\texttt{r}})+v({\texttt{L}})$ is in the kernel of
this matrix. Thus

(12) $(1,1,1,1,1)M^{n}(M^{3}-M^{2}-2I)(0,1,1,0,0)^{T}=0,$

from which we obtain

(13) $a_{n}-a_{n-1}-2a_{n-3}=0.$

Together with the first few terms, given in (8), we obtain the recurrence
relation (9). ∎

###  3.2. Generating function

For integers $n\geq 1$, let $b_{n}$ be the coefficients of the Taylor series
expansion of $x(1+x^{2})/(1-x-2x^{3})$, which is the generating function for
these coefficients, and is taken from [8] and [7, A203175]. By definition we
have,

(14)
$\frac{x(1+x^{2})}{1-x-2x^{3}}=\sum_{n=1}^{\infty}b_{n}x^{n}=x+x^{2}+2x^{3}+4x^{4}+6x^{5}+10x^{6}+18x^{7}+\cdots.$

######  Theorem 3.

The coefficients $b_{n}$ of the Taylor series expansion of
$x(1+x^{2})/(1-x-2x^{3})$ satisfy

(15) $\begin{array}[]{ll}&b_{n}=b_{n-1}+2b_{n-3}\text{ for }n\geq 4\\\
&b_{1}=1,\>\>b_{2}=1,\>\>b_{3}=2.\end{array}$

###### Proof.

Multiplying both sides of (14) by $(1-x-2x^{3})$, we have

$\displaystyle x+x^{3}$
$\displaystyle=\sum_{n=0}^{\infty}b_{n}(1-x-2x^{3})x^{n}$
$\displaystyle=\sum_{n=0}^{\infty}b_{n}(1-x-2x^{3})x^{n}$
$\displaystyle=\sum_{n=4}^{\infty}(b_{n}-b_{n-1}-2b_{n-3})x^{n}.$

Therefore, by comparing coefficients of $x^{n}$, we see that the $b_{n}$
satisfy the given recurrence relation. The initial terms are taken from the
expansion in (14). ∎

###  3.3. Binary sequences without certain runs of zeros

We now consider binary sequences without runs of zeros of length $1$ mod $3$,
following the definition of Milan Janjic in the entry [7, A203175].

######  Definition 1.

$S_{n}$ is the set of binary sequences of length $n$ with no run of zeros of
length $1$ mod $3$. Let

$c_{n}:=|S_{n}|.$

Note that here the length of a run of zeros means the maximum length of any
substring of zeros, not the possible lengths of substrings of zeros, for for
example $00000\in S_{5}$. For example, $S_{n}$ and $c_{n}$ for $1$ to $5$ are
shown in the Table 1.

$\begin{array}[]{|l|lllll|}\hline\cr n&1&2&3&4&5\\\ c_{n}&1&2&4&6&10\\\
\hline\cr&1(C)&11(E)&111(E)&1111(E)&11111(E)\\\ &&&&&11100(B)\\\
\cline{5-6}\cr&&&&1100(B)&11001(D)\\\ &&&&&11000(A)\\\ \cline{4-6}\cr
S_{n}&&&100(B)&1001(D)&10011(E)\\\ \cline{5-6}\cr&&&&1000(A)&10001(C)\\\
\cline{3-6}\cr&&00(B)&001(D)&0011(E)&00111(E)\\\ &&&&&00100(B)\\\
\cline{4-6}\cr&&&000(A)&0001(C)&00011(E)\\\ &&&&&00000(B)\\\
\hline\cr\end{array}$
Table 1. Elements of $S_{n}$ for $n=1,\dots,5$, arranged according to the
appending rules in Table 3. Each sequence is followed by its type in brackets,
according to Table 2.

######  Definition 2.

We define six types of sequences, as in Table 2.

name | description | example
---|---|---
A |  sequences ending in a string of $0<m\equiv 0\mod 3$ zeros | $1011000$
B |  sequences ending in a string of $0<m\equiv 2\mod 3$ zeros | $10100000$
C |  sequences ending in a string of $0<m\equiv 0\mod 3$ zeros, followed by 1 | $10001$
D |  sequences ending in a string of $0<m\equiv 2\mod 3$ zeros, followed by 1 | $001$
E | sequences ending in 11 | $100111$
Table 2. Types of elements of $S_{n}$.

Now we define rules for building sequences of length $n+1$ from sequences of
length $n$, as in Table 3.

A | add $1$ to get a sequence of type C
---|---
B | add $0$ to get a sequence of type A
| or add $1$ to get a sequence of type D
C | add $1$ to get a sequence of type E
| or remove the last $1$ and add $00$ to get a sequence of type B
D | add $1$ to get a sequence of type E
E | add $1$ to get a sequence of type E
| or remove the last $1$, and add $00$ to get a sequence of type B
Table 3. how to transform elements of $S_{n}$ to elements of $S_{n+1}$.

We denote the power set of $S_{n+1}$ by $\mathcal{P}(S_{n+1})$. The rules in
Table 3. can be used to define a function as follows, where $\mathbf{v}$
denotes a binary sequence of length $n$, and $\mathbf{w}$ denotes a binary
sequence of length $n-2$.

(16) $\begin{array}[]{ll}f_{n}:S_{n}&\rightarrow\mathcal{P}(S_{n+1})\\\
\mathbf{v}&\mapsto\begin{cases}\\{\mathbf{v}1\\}&\text{ if }\mathbf{v}\text{
has type A (image type C)}\\\ \\{\mathbf{v}0,\mathbf{v}1\\}&\text{ if
}\mathbf{v}\text{ has type B (image types A, D)}\\\
\\{\mathbf{w}011,\mathbf{w}000\\}&\text{ if }\text{ if
}\mathbf{v}=\mathbf{w}01\text{ has type C (image types E, B)}\\\
\\{\mathbf{v}1\\}&\text{ if }\mathbf{v}\text{ has type D (image type E)}\\\
\\{\mathbf{w}111,\mathbf{w}100\\}&\text{ if }\mathbf{v}=\mathbf{w}11\text{ has
type E (image types E, B)}\\\ \end{cases}\end{array}$

######  Lemma 1.

We have a disjoint union

$S_{n+1}=\bigcup_{\mathbf{v}\in S_{n}}f_{n}(\mathbf{v})$

and

$|S_{n+1}|=\sum_{\mathbf{v}\in S_{n}}|f_{n}(\mathbf{v})|.$

###### Proof.

We must show that each element $\mathbf{x}\in S_{n+1}$ is contained in exactly
one of the sets of the form $f_{n}(\mathbf{v})$ for some $\mathbf{v}\in
S_{n}$. First we prove existence of some $\mathbf{v}$ with $\mathbf{x}\in
f_{n}(\mathbf{v})$.

Suppose that $\mathbf{x}=\mathbf{v}1$. Then $\mathbf{v}$ must be in $S_{n}$,
and can have any type, and we have $\mathbf{x}\in f_{n}(\mathbf{v})$, since we
can always add $1$ to any element of $S_{n}$ to obtain an element of
$S_{n+1}$. In other words, if $\mathbf{x}$ ends in a $1$, we can always remove
it to obtain an element of $S_{n}$.

Suppose that $\mathbf{x}=\mathbf{v}0$. Then either $\mathbf{v}$ ends in a
string of zeros of length $1$ or $2$ mod $3$.

  1. (1)

In the case that $\mathbf{v}$ ends in a string of $3k+2$ zeros (for some
$k\in\mathbb{Z}$), $\mathbf{v}\in S_{n}$ has type B, and $\mathbf{x}\in
f_{n}(\mathbf{v})$. I.e., $\mathbf{v}$ is obtained from $\mathbf{x}$ precisely
by removing the last $0$ from $\mathbf{x}$.

  2. (2)

If $\mathbf{v}$ ends in a string of $3k+1$ zeros, for example if
$\mathbf{x}=100$, then $\mathbf{v}\not\in S_{n}$. In this case, we have that
$\mathbf{x}$ ends in at least two zeros. Either these are immediately preceded
by a $1$ or a $0$. Suppose we have $\mathbf{x}=\mathbf{y}100$ for some word
$\mathbf{y}$. Then $\mathbf{x}\in f_{n}(\mathbf{y}11)$, where $\mathbf{y}11$
has type E. E.g., $00100\in f_{n}(0011)$.

  3. (3)

If we are the the case where $\mathbf{x}=\mathbf{y}000$, then $\mathbf{x}\in
f_{n}(\mathbf{y}01)$, where $\mathbf{y}01$ has type C. E.g., $001100000\in
f_{n}(00110001)$.

Now we must show that $\mathbf{x}$ is in $f_{n}(\mathbf{v})$ for some unique
$\mathbf{v}\in S_{n}$.

  1. (1)

For the case that $\mathbf{x}$ ends in $1$, this is because we only obtain
elements of $S_{n+1}$ in $f_{n}({\texttt{v}})$ by adding $1$ to the end of
elements of $S_{n}$.

  2. (2)

In the case that $\mathbf{x}$ ends in a zero, considering the definition, and
(16), $\mathbf{x}$ must be in $f_{n}(\mathbf{v})$ for some $\mathbf{v}$ of
type B, C, or E, corresponding to $\mathbf{x}$ having type A, B, B
respectively.

  3. (3)

In the case where $\mathbf{x}$ has type A, ending in $3k$ zeros, we can only
obtain $\mathbf{x}$ from an element of $S_{n}$ by removing the last $0$, to
obtain an element of type B. So this gives a unique element $\mathbf{v}$ with
$\mathbf{x}\in f_{n}(\mathbf{v})$.

  4. (4)

In the case where $\mathbf{x}$ has type B, and ends in at least two zeros, in
which case $\mathbf{v}$ is obtained uniquely from $\mathbf{x}$ by removing the
last two zeros and replacing with $1$, resulting in a uniquely defined element
either of type C or E.

Thus we obtain the stated equalities. ∎

######  Theorem 4.

The sequence $c_{n}=|S_{n}|$ satisfies a recurrence relation

(17) $\begin{array}[]{l}c_{n}=c_{n-1}+2c_{n-3}\text{ for }n\geq 4\\\
c_{1}=1,\>c_{2}=2,\>c_{3}=4\end{array}$

###### Proof.

We can rewrite the map in (16) as follows:

$\displaystyle A$ $\displaystyle\mapsto C$ $\displaystyle B$
$\displaystyle\mapsto AD$ $\displaystyle C$ $\displaystyle\mapsto EB$
$\displaystyle D$ $\displaystyle\mapsto E$ $\displaystyle E$
$\displaystyle\mapsto EB$

By Lemma 1, any element of $S_{n}$ is obtained uniquely from some element of
$S_{n-1}$. Define a transition matrix

(18) $M=\begin{pmatrix}0&1&0&0&0\\\ 0&0&1&0&1\\\ 1&0&0&0&0\\\ 0&1&0&0&0\\\
0&0&1&1&1\end{pmatrix}$

with columns corresponding to $A,B,C,D,E$. This tells us how to pass from
elements of $S_{n}$ to elements of $S_{n+1}$ by type. So we have that the size
of $S_{n}$ is given by

(19) $|S_{n}|=(1,1,1,1,1)M^{n-1}(0,0,1,0,0)^{T}$

where the vector $(0,0,1,0,0)$ corresponds to the initial string $1$ of length
one. We compute that the characteristic polynomial of $M$ is
$x^{2}(x^{3}-x^{2}-2)$, and then, as in the computation in (4), we find that

(20) $c_{n}=c_{c-1}+2c_{n-3}.$

The initial terms are as given in Table 1. ∎

###  3.4. Certain arrays with elements $0,1,2$.

Sequence [7, A203175] has description as follows.

######  Definition 3.

Let $A_{n}$ be the set of $n\times 2$ arrays, containing only elements of the
set $\\{0,1,2\\}$, such that

  * •

every 1 is immediately preceded by 0 to the left or above,

  * •

no 0 is immediately preceded by a 0, either above or to the left,

  * •

every 2 is immediately preceded by 0 1, in the two rows above.

I.e., if $m\in A_{n}$ has elements $m_{i,j}$, with $m_{0,0}=0$, then
$m_{i,j}=1\Rightarrow m_{i-1,j}=0$ (and $i>0$) or $m_{i,j-1}=0$ (and $j>0$);
$m_{i,j}=0\Rightarrow m_{i-1,j}\not=0$ (if $i>0$) and $m_{i,j-1}\not=0$ (if
$j>0$); and $m_{i,j}=2\Rightarrow m_{i,j-1}=1$ and $m_{i,j-2}=0$ (and $j>1$).
Let

(21) $d_{n}=|A_{n}|.$

For example, $A_{1}=\\{(0,1)\\}$, $A_{2}=\left\\{\begin{pmatrix}0&1\\\
1&0\end{pmatrix}\right\\}$ so $d_{1}=d_{2}=1$. The elements of $A_{5}$ are
shown in Figure 3, and $d_{5}=6$.

Just as we constructed $S_{n+1}$ from $S_{n}$ in the previous section, we can
construct $A_{n+1}$ from $A_{n}$ as follows. We define ten different types of
arrays, depending on the last two rows:

######  Definition 4.

An $n\times 2$ array of elements $0,1,2$ is said to have type
$A,B,C,D,E,F,G,H$ depending on the last row, according to the following table

$\begin{array}[]{ccccccccc}type&A&B&C&D&E&F&G&H\\\
row&(0,1^{0})&(0,1^{x})&(0,2)&(1,0)&(1,2)&(2,0)&(2,1^{0})&(2,1^{x})\end{array}$

Here, in the second entry, $1^{0}$ means $1$ with a $0$ above it, and $1^{x}$
means a $1$ with a $1$ or $2$ above it. In the first column, $1$ always has a
$0$ above it. We can never have a row of the form $(1,1)$, since this would
have to be preceded by a row $(0,0)$, and $0$ is not allowed to be next to
$0$, so this is impossible. Similarly, $(2,2)$ would have to be preceded by
$(1,1)$ so is not allowed. So the above list contains all the possible last
rows of elements of $A_{n}$ for all $n$ (not all of which will be achieved for
all $n$). We also refer to the last row as having the given type.

In the definition of $A_{n}$, we see that the elements are built up in terms
of the previous rows, so all elements of $A_{n+1}$ can be obtained from an
element of $A_{n}$ by adding one more row which satisfies the rules in
Definition 3.

Each type of matrix in $A_{n}$ can be extended to a matrix in $A_{n+1}$ by
adding a row, with type E.g., suppose a matrix $m$ in $A_{n}$ has type $A$,
and so ends with a row $m_{n}=(m_{n,1},m_{n,2})=(0,1^{0})$. Then for the next
row, with new elements $(m_{n+1,1},m_{n+1,2})$, we must have $m_{n+1,1}=1$,
since $0$ in the first column can only be followed by a $1$ below it. Since
$m_{n,2}$ has a $0$ above it, we could have $m_{n+1,2}=2$. Since
$m_{n+1,1}\not=0$, and $m_{n,2}\not=0$, we could have $m_{n+1,2}=0$, but we
can’t obtain $m_{n+1,2}=1$. So type $A$ can be followed by type $D$ or $E$. By
similar considerations, we obtain the following table, which shows all the
possible ways of extending a matrix of a given type in $A_{n}$ to a matrix of
a given type in $A_{n+1}$. We define a corresponding function $f$ on
$\\{A,B,C,D,E,F,G,H\\}$ as in the column on the right in Table 4.

$\begin{array}[]{l|l|l}\text{ type of }m_{n}&\text{possible type of
}m_{n+1}&f\\\ \hline\cr A&D,E&f(A)=\\{D,E\\}\\\ B&D&f(B)=\\{D\\}\\\
C&D&f(C)=\\{D\\}\\\ D&A,G&f(D)=\\{A,G\\}\\\ E&B,F&f(E)=\\{B,F\\}\\\
F&A&f(F)=\\{A\\}\\\ G&B,C&f(G)=\\{B,C\\}\\\ H&B&f(H)=\\{B\\}\end{array}$ Table
4. Rules for elements of $A_{n+1}$ following from elements of $A_{n}$.
$(0,1^{x})$ $B$ $(1,0)$ $D$ $(0,1^{0})$ $A$ $(2,1^{0})$ $G$ $(1,0)$ $D$
$(1,2)$ $E$ $(0,1^{x})$ $B$ $(0,2)$ $C$ $(0,1^{0})$ $A$ $(2,1^{0})$ $G$
$(0,1^{x})$ $B$ $(2,0)$ $F$ $(1,0)$ $D$ $(1,0)$ $D$ $\begin{pmatrix}0&1\\\
1&0\\\ 0&1\\\ 1&0\\\ 0&1\end{pmatrix}$$\begin{pmatrix}0&1\\\ 1&0\\\ 0&1\\\
1&0\\\ 2&1\end{pmatrix}$$\begin{pmatrix}0&1\\\ 1&0\\\ 0&1\\\ 1&2\\\
0&1\end{pmatrix}$$\begin{pmatrix}0&1\\\ 1&0\\\ 0&1\\\ 1&2\\\
2&0\end{pmatrix}$$\begin{pmatrix}0&1\\\ 1&0\\\ 2&1\\\ 0&1\\\
1&0\end{pmatrix}$$\begin{pmatrix}0&1\\\ 1&0\\\ 2&1\\\ 0&2\\\
1&0\end{pmatrix}$$d_{1}=1$$d_{2}=1$$d_{3}=2$$d_{4}=4$$d_{5}=6$ Figure 3.
Construction of elements of $A_{5}$, row by row, using the rules in Table 4

######  Theorem 5.

The number of elements of $A_{n}$ in Definition 3 is given by

(22) $\begin{array}[]{l}d_{n}=d_{n-1}+2d_{n-3}\text{ for }n\geq 4\\\
d_{1}=1,\>d_{2}=1,\>d_{3}=2.\end{array}$

###### Proof.

We have discussed above how rows $A,B,C,D,E,F,G,H$ of an element of $A_{n}$
transition to the next possible row of an element of $A_{n+1}$, as shown in
Table 4. Since row type $H$ never occurs in the image of $f$, we will leave
this out from now on. The transition function $f$ in Table 4 can be
represented by the matrix

(23) $N=\begin{pmatrix}0&0&0&1&0&1&0\\\ 0&0&0&0&1&0&1\\\ 0&0&0&0&0&0&1\\\
1&1&1&0&0&0&0\\\ 1&0&0&0&0&0&0\\\ 0&0&0&0&1&0&0\\\ 0&0&0&1&0&0&0\\\
\end{pmatrix}$

with rows and columns corresponding to $A$ to $G$ in alphabetical order. Since
$(0,1,0,0,0,0,0)$ corresponds to $B$, in the initial set $A_{1}=\\{B\\}$. We
have that the number of elements of each type in $A_{n}$ is given by the
corresponding component of the vector $N^{n-1}(0,1,0,0,0,0,0)^{T}$, and the
count of all of these is

(24) $d_{n}=(1,1,1,1,1,1,1)N^{n-1}(0,1,0,0,0,0,0)^{T}.$

The matrix $N$ has characteristic polynomial
$x(x^{3}-x^{2}-2)(x^{3}+x^{2}-1)$. The factor $(x^{3}-x^{2}-2)$ corresponds to
our expected recurrence relation. However, $(0,1,0,0,0,0,0,0)$, does not
belong to the kernel of this matrix, so we can’t immediately conclude our
proof.

The kernel of $N(N^{3}+N^{2}-I)$ is spanned by $(1,0,0,-1,0,0,0)$,
$(0,0,0,0,1,0,-1)$, $(0,1,-1,0,0,0,0)$, $(0,1,0,0,0,-1,0)$, which corresponds
to a partition of $\\{A,B,\dots,G\\}$ into the sets

$X=\\{A,D\\},Y=\\{E,G\\},Z=\\{B,C,F\\}.$

We can rewrite Table 4 in terms of $X,Y,Z$:

$\begin{array}[]{l|l}\text{ type of }m_{n}&\text{possible type of }m_{n+1}\\\
\hline\cr X&X,Y\\\ Y&Z,Z\\\ Z&X\end{array}$ Table 5. Rules for elements of
$A_{n+1}$ following from elements of $A_{n}$, in terms of types $X,Y,Z$.

This table shows how each type of matrix in $A_{n}$ can be extended to a
matrix of some type in $A_{n+1}$, in terms of the types $X,Y,Z$. For example,
the initial element $(0,1)\in A_{1}$ has type $Z$, and can only be followed by
an element in $A_{2}$ of type $X$, which can be followed in $A_{3}$ by
elements of type $X$ and $Y$. For example, to obtain the elements of $A_{5}$,
we have sequences corresponding to elements of $A_{5}$ as in Table 6.

$\begin{array}[]{c|c|c|c|c|l|l}\lx@intercol\hfil\text{applications of
}f\hfil\lx@intercol\vrule\lx@intercol&\text{resulting sequence}&\text{sequence
in terms of $A$ to $G$.}\\\ \hline\cr&&&X&X&ZXXXX&BDADA\\\
\cline{5-7}\cr&&X&&Y&ZXXXY&BDADG\\\ \cline{4-7}\cr Z&X&&Y&Z&ZXXYZ&BDAEB\\\
\cline{5-7}\cr&&&&Z&ZXXYZ&BDAEF\\\ \cline{3-7}\cr&&Y&Z&X&ZXYZX&BDGBD\\\
\cline{4-7}\cr&&&Z&X&ZXYZX&BDGCD\\\ \end{array}$ Table 6. Example of words in
$X,Y,Z$, and the corresponding words in $A,B,C,D,E,F,G$.

We can rewrite Table 5 as a function

(25) $f(X)=\\{X,Y\\},\>f(Y)=\\{Z,Z\\},\>f(Z)=\\{X\\},$

where the images are not sets, but ordered lists of elements of the set
$\\{X,Y,Z\\}$. The map $f$ (25) can now be written in matrix format as

$P=\begin{pmatrix}1&0&1\\\ 1&0&0\\\ 0&2&0\end{pmatrix},$

where the first, second and third rows and columns correspond to the sets
$X,Y,Z$ respectively. Since $P$ tells us how we can continue sequences of the
rows of elements of $A_{n}$ to $A_{n+1}$, and the starting element $B$ is
contained in $Z$, which corresponds to the vector $(0,0,1)$, heuristically, we
have that

(26) $d_{n}=(1,1,1)P^{n-1}(0,0,1)^{T}.$

To prove more formally that (26) holds, we view $\mathbb{R}^{3}$ as a quotient
of $\mathbb{R}^{7}$ by the kernel of $N(N^{3}+N^{2}-I)$. Corresponding to this
description, we find a quotient map,
$V:\mathbb{R}^{7}\rightarrow\mathbb{R}^{3}$, and a right inverse inclusion map
$U:\mathbb{R}^{3}\hookrightarrow\mathbb{R}^{7}$. For simplicity of notation,
we denote the corresponding matrices by the same symbols. The maps $U$ and $V$
are given by the matrices

(27) $U=\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&0&0\\\ 0&0&0\\\ 0&0&1\\\ 0&0&0\\\
0&0&0\\\
\end{pmatrix},\rule{28.45274pt}{0.0pt}V=\begin{pmatrix}1&0&0&1&0&0&0\\\
0&0&0&0&1&0&1\\\ 0&1&1&0&0&1&0\end{pmatrix}.$

We have $P=VNU$, and can also verify that $VU=I_{3}$. (the identity in
$\text{GL}(n)$ is denoted by $I$ for all $n$, or $I_{n}$ for clarity.) Define
linear maps $Q:\mathbb{R}\rightarrow\mathbb{R}^{3}$,
$R:\mathbb{R}\rightarrow\mathbb{R}^{7}$,
$S:\mathbb{R}^{3}\rightarrow\mathbb{R}$ and
$T:\mathbb{R}^{7}\rightarrow\mathbb{R}$ by

(28) $R=\begin{pmatrix}0\\\ 1\\\ 0\\\ 0\\\ 0\\\ 0\\\ 0\\\ 0\\\
\end{pmatrix},\rule{28.45274pt}{0.0pt}Q=\begin{pmatrix}0\\\ 0\\\
1\end{pmatrix},\rule{28.45274pt}{0.0pt}T=(1,1,1,1,1,1,1),\rule{28.45274pt}{0.0pt}S=(1,1,1).$

Then the RHS of (24) is the value of $TN^{n-1}R(1)$, and the RHS of (26) is
the value of $SP^{n-1}Q(1)$. So to prove that (26) holds, we must check that
$TN^{n-1}R=SP^{n-1}Q$ for all $n\geq 1$. This is equivalent to showing that
the following diagram commutes, that is, the top row is the same map as the
bottom row:

(29)
${{\mathbb{R}}}$${{\mathbb{R}^{7}}}$${{\mathbb{R}^{7}}}$${{\mathbb{R}^{7}}}$${{\mathbb{R}^{7}}}$${{\mathbb{R}^{7}}}$${{\mathbb{R}}}$${{\mathbb{R}}}$${{\mathbb{R}^{3}}}$${{\mathbb{R}^{3}}}$${{\mathbb{R}^{3}}}$${{\mathbb{R}^{3}}}$${{\mathbb{R}^{3}}}$${{\mathbb{R}}}$$\scriptstyle{R}$$\scriptstyle{N}$$\scriptstyle{V}$$\scriptstyle{N}$$\scriptstyle{V}$$\scriptstyle{V}$$\scriptstyle{N^{n-4}}$$\scriptstyle{N}$$\scriptstyle{V}$$\scriptstyle{V}$$\scriptstyle{T}$$\scriptstyle{Q}$$\scriptstyle{P}$$\scriptstyle{P}$$\scriptstyle{P^{n-4}}$$\scriptstyle{P}$$\scriptstyle{S}$

To see this, first note that we have equalities

(30) $Q=VR,\rule{28.45274pt}{0.0pt}T=SV,\rule{28.45274pt}{0.0pt}PV=VN,$

which can be checked computationally. Then by an inductive argument, we have
for $i=0,\dots,n-1$ that
$TN^{n-1}R=SVN^{n-1}R=SP^{i}VN^{n-1-i}R=SP^{n-1}VR=SP^{n-1}Q$, which just
corresponds to following through the diagram, and we see that (29) does
commute. So (26) does indeed hold. We find that the matrix $P$ has
characteristic polynomial $x^{3}-x^{2}-2$, so $P^{3}-P^{2}-2I=0$. Thus from
(26), using the same method as in (12), we obtain the recurrence

$d_{n}-d_{n-1}-2d_{n-3}=0,\text{ for }n\geq 3$

with initial terms $d_{1}=d_{2}=1$ and $d_{3}=2$ as in Figure 3. ∎

######  Corollary 1.

We have $a_{n}=b_{n-1}=c_{n}=d_{n-1}$, with $a_{n},b_{n},c_{n},d_{n}$ as
defined in (7), (14), Definition 1, and (21) respectively.

###### Proof.

The first few terms, $1,1,2,4,6$, of these sequences are given in (8), (15),
Table 1, and Figure 3 respectively. The only difference is that $a_{n}$ starts
from $n=0$, $b_{n}$ starts from $n=1$, $c_{n}$ starts from $n=0$, (inserting
an extra $c_{0}=1$ term) and $d_{n}$ starts from $n=1$. We showed that they
all satisfy the same recurrence relation, in Theorems 2, 3, 4, and 5
respectively. Thus the result follows. ∎

##  4\. Conclusions

By using the L-system for the boundary of the Harter-Heighway dragon curve, we
have been able to prove results not only about the dragon curve, but also
related sequences, found in [7], by also viewing them in terms of transition
matrices inspired by L-systems. Given that the sequences in Section 3 count
sizes of various sets, which all turn out to have the same size, we have
actually constucted bijections between these sets. The L-system for the
Heighway dragon results in a word, with letters in an order which is lost by
just using the matrix $M$, which only counts the total number of letters. The
elements of the sets in $S_{n}$ and $A_{n}$ in Sections 3.3 and 3.4 do not a
proiri have a natural ordering, but we can use the L-system for the right side
of the dragon curve to impose an ordering on the elements of the sets $S_{n}$
and $A_{n}$ (Definitions 3 and 1), though we must make a choice, e.g.,
lexicographical on the elements $A,\dots,G$ in Definition 4. This gives
orderings for example as in Table 1 and Figure 3. Given such a choice, this
results in a corresponding bijection between the elements of the sets $A_{n}$
and $S_{n}$ and the edges of the right side of the dragon curve
$\mathcal{S}_{n}$. This may well just be numerology, but perhaps there is an
interesing geometrical or number theoretical meaning waiting to be discovered.

## References

  * [1] Harold Abelson and Andrea A. diSessa.  Turtle geometry.  MIT Press Series in Artificial Intelligence. MIT Press, Cambridge, Mass.-London, 1981.  The computer as a medium for exploring mathematics.
  * [2] Jörg Arndt and Julia Handl.  “Plane-filling Folding Curves on the Square Grid”.  In Bridges Conference Proceedings, pages 179–186, 2018.
  * [3] D.E. Daykin and S. J. Tucker.  Sequences from folding paper.  Unpublished manuscript, reproduced in Online Encyclopedia of Integer Sequences (ed. N. J. A. Sloane), entry A003229, January 1975.
  * [4] Michel Dekking.  Paperfolding morphisms, planefilling curves, and fractal tiles.  Theoret. Comput. Sci., 414:20–37, 2012.
  * [5] G. Edgar.  Measure, Topology, and Fractal Geometry.  Undergraduate Texts in Mathematics. Springer, New York, second edition, 2008.
  * [6] Aristid Lindenmayer.  Mathematical models for cellular interactions in development ii. simple and branching filaments with two-sided inputs.  Journal of Theoretical Biology, 18(3):300–315, 1968.
  * [7] OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2024.  Published electronically at http://oeis.org.
  * [8] Simon Plouffe.  Approximations de séries génératrices et quelques conjectures.  Dissertation, Université du Québec à Montréal, 1992.  arXiv:0911.4975 [math.NT], 2009.
  * [9] S. Tabachnikov.  “Dragon Curves Revisited”.  Math. Intelligencer, 36(1):13–17, 2014.
  * [10] Helena Verrill.  L-systems for the boundaries of plane-filling folding curves.  https://arxiv.org/abs/2402.16106a.