Regular paperfolding sequence

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 = { 1 if  m = 1 mod 4 0 if  m = 3 mod 4

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 = { 1 if  n = 2 k 1 − t 2 k − n if  2 k − 1 < n < 2 k

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 = 0 ∞ 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 ) + ∑ n = 0 ∞ x 4 n + 1 = G ( t n ; x 2 ) + x 1 − x 4 .

Paperfolding constant

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

G ( t n ; 1 2 ) = ∑ n = 1 ∞ t n 2 n

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

∑ k = 0 ∞ 8 2 k 2 2 k + 2 − 1 = 0.85073618820186... (sequence A143347 in the OEIS)

General paperfolding sequence

The regular paperfolding sequence corresponds to folding a strip of paper consistently in the same direction. If we allow the direction of the fold to vary at each step we obtain a more general class of sequences. Given a binary sequence (f_i), we can define a general paperfolding sequence with folding instructions (f_i).

For a binary word w, let w^‡ denote the reverse of the complement of w. Define an operator F_a as

F a : w ↦ w a w ‡  

and then define a sequence of words depending on the (f_i) by w₀ = ε,

w n = F f 1 ( F f 2 ( ⋯ F f n ( ε ) ⋯ ) )   .

The limit w of the sequence w_n is a paperfolding sequence. The regular paperfolding sequence corresponds to the folding sequence f_i = 1 for all i.

If n = m·2^k where m is odd then

t n = { f j if  m = 1 mod 4 1 − f j if  m = 3 mod 4

which may be used as a definition of a paperfolding sequence.

Properties

A paperfolding sequence is not ultimately periodic.

A paperfolding sequence is 2-automatic if and only if the folding sequence is ultimately periodic (1-automatic).