In mathematics the regular paperfolding sequence, also known as the dragon curve sequence, is an infinite sequence of 0s and 1s. It is obtained from the repeating partial sequence
by filling in the question marks by another copy of the whole sequence. The first few terms of the resulting sequence are:
If a strip of paper is folded repeatedly in half in the same direction, i {\displaystyle i} times, it will get 2 i − 1 {\displaystyle 2^{i}-1} folds, whose direction (left or right) is given by the pattern of 0's and 1's in the first 2 i − 1 {\displaystyle 2^{i}-1} terms of the regular paperfolding sequence. Opening out each fold to create a right-angled corner (or, equivalently, making a sequence of left and right turns through a regular grid, following the pattern of the paperfolding sequence) produces a sequence of polygonal chains that approaches the dragon curve fractal:
Properties The value of any given term t n {\displaystyle t_{n}} in the regular paperfolding sequence, starting with n = 1 {\displaystyle n=1} , can be found recursively as follows. Divide n {\displaystyle n} by two, as many times as possible, to get a factorization of the form n = m ⋅ 2 k {\displaystyle n=m\cdot 2^{k}} where m {\displaystyle m} is an odd number. Then
t n = { 1 if m ≡ 1 mod 4 0 if m ≡ 3 mod 4 {\displaystyle t_{n}={\begin{cases}1&{\text{if }}m\equiv 1\mod 4\\0&{\text{if }}m\equiv 3\mod 4\end{cases}}}
Thus, for instance, t 12 = t 3 = 0 {\displaystyle t_{12}=t_{3}=0} : dividing 12 by two, twice, leaves the odd number 3. As another example, t 13 = 1 {\displaystyle t_{13}=1} because 13 is congruent to 1 mod 4. 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 = { 1 if n = 2 k 1 − t 2 k − n if 2 k − 1 < n < 2 k {\displaystyle 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 In each iteration of this process, a 1 is placed at the end of the previous iteration's string, then this string is repeated in reverse order, replacing 0 by 1 and vice versa.
Generating function The generating function of the paperfolding sequence is given by
G ( t n ; x ) = ∑ n = 1 ∞ t n x n . {\displaystyle G(t_{n};x)=\sum _{n=1}^{\infty }t_{n}x^{n}\,.}
From the construction of the paperfolding sequence, it can be seen that G satisfies the functional relation
… excerpt ends here. Continue reading the full article.
