Regular paperfolding sequence

In mathematics the regular paperfolding sequence, also known as the dragon curve sequence, is an infinite automatic sequence of 0s and 1s defined as the limit of the following process:

1

1 1 0

1 1 0 1 1 0 1

1 1 0 1 1 0 0 1 1 1 0 0 1 1 0

At each stage an alternating sequence of 1s and 0s is inserted between the terms of the previous sequence. The sequence takes its name from the fact that it represents the sequence of left and right folds along a strip of paper that is folded repeatedly in half in the same direction. If each fold is then opened out to create right angled corner, the resulting shape approaches the dragon curve fractal.

Starting at n = 1, the first few terms of the regular paperfolding sequence are:

1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, ... (sequence A014577 in the OEIS)

Properties

The value of any given term t_n in the regular paperfolding sequence can be found recursively as follows. If n = m.2^k where m is odd then

$t_{n}={\begin{cases}1&{\text{if }}m=1\mod 4\\0&{\text{if }}m=3\mod 4\end{cases}}$

Thus t₁₂ = t₃ = 0 but t₁₂ = 1.

The paperfolding word 1101100111001001..., which is created by concatenating the terms of the regular paperfolding sequence, is a fixed point of the morphism or string substitution rules

11 → 1101

01 → 1001

10 → 1100

00 → 1000

as follows:

11 → 1101 → 11011001 → 1101100111001001 → 11011001110010011101100011001001 ...

It can be seen from the morphism rules that the paperfolding word contains at most three consecutive 0s and at most three consecutive 1s.

The paperfolding sequence also satisfies the symmetry relation:

$t_{n}={\begin{cases}1&{\text{if }}n=2^{k}\\1-t_{2^{k}-n}&{\text{if }}2^{k-1}<n<2^{k}\end{cases}}$

which shows that the paperfolding word can be constructed as the limit of another iterated process as follows:

1

1 1 0

110 1 100

1101100 1 1100100

110110011100100 1 110110001100100

Generating function

The generating function of the paperfolding sequence is given by

$G(t_{n};x)=\sum _{n=0}^{\infty }t_{n}x^{n}\,.$

From the construction of the paperfolding sequence it can be seen that G satisfies the functional relation

$G(t_{n};x)=G(t_{n};x^{2})+\sum _{n=0}^{\infty }x^{4n+1}=G(t_{n};x^{2})+{\frac {x}{1-x^{4}}}\,.$

Paperfolding constant

Substituting x = ½ into the generating function gives a real number between 0 and 1 whose binary expansion is the paperfolding word

$G(t_{n};{\frac {1}{2}})=\sum _{n=1}^{\infty }{\frac {t_{n}}{2^{n}}}$

This number is known as the paperfolding constant and has the value

$\sum _{k=0}^{\infty }{\frac {8^{2^{k}}}{2^{2^{k+2}}-1}}=0.85073618820186...$ (sequence A143347 in the OEIS)

References

• Jean-Paul Allouche and Jeffrey Shallit Automatic Sequences Cambridge University Press 2003