A288203 Fixed point of the mapping 00->0010, 1->010, starting with 00.

0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0

Offset

1

Comments

From Michel Dekking, Oct 12 2018: (Start)

Here is a proof of the conjecture on the sequence of lengths 2, 4, 8, 18, 38, 80, ... of the iterates of the mapping (see also A288206). We note first that the mapping SR: 00->0010, 1->010, is an algorithmic procedure given by StringReplace in Mathematica. This makes it hard in general to describe iterates of it. However, here is an analysis of what happens in this particular case. Let

H:=100, T:=1000, Z:=00, E1:=100, E2:=10.

Then

SR(H) = 0100010 = 0 T H 0^{-1},

SR(T) = 01000100 = 0 T T 0^{-1},

SR(Z) = 0010 = Z H 0^{-1},

SR(E1) = 0100010 = 0 T E2,

SR(E2) = 0100 = 0 E1.

Let sigma be the morphism on the alphabet {H,T,Z,E1,E2} given by

sigma(Z)=ZH, sigma(H)=TH, sigma(T)=TT, sigma(E1)= T E2, sigma(E2)= E1.

Then, because the 0's at the beginning of SR(H), SR(T), SR(E1) and SR(E2) always cancel, we have

sigma^n(Z E2) = SR^{n+1}(Z) for n=0,1,2,...,

Examples:

Z E2 = 0010 = SR(00),

sigma(Z E2) = ZH E1 = 00100100,

sigma^2(Z E2) = ZHTHT E2 = 001001000100100010.

From this it follows that

(a(n)) = delta(x),

where x = (x(n)) is the infinite word with x(1)=Z fixed by sigma, i.e., sigma(x)=x, and delta is the 'decoration' morphism

delta(H):=100, delta(T):=1000, delta(Z):=00.

Note that sigma is a reducible morphism, and that E1 and E2 do not occur in the fixed point x (they only occur at the end of the SR^n(00)).

We also proved that the number of letters (Z's, H's, T's, E1's, and E2's} in the n-th iterate of SR is equal to the vector/matrix/vector product

(2,3,4,3,2) M^n (1,0,0,0,1)^T,

where (1,0,0,0,1)^T is the transpose of (1,0,0,0,1), and M is the incidence matrix of the morphism sigma, i.e., M equals

|1 0 0 0 0|

|1 1 0 0 0|

|0 1 2 1 0|

|0 0 0 0 1|

|0 0 0 1 0|

The characteristic polynomial of M is equal to chi(u) = u^5-4u^4+4u^3+2u^2-5u+2. It follows therefore from the Cayley-Hamilton theorem that the sequence of lengths satisfies the linear recursion

a(n+5) = 4*a(n+4) - 4*a(n+3) - 2*a(n+2) + 5*a(n+1) - 2*a(n).

This is not the conjectured recursion a(n+4) = 3*a(n+3) - a(n+2) - 3*a(n+1) + 2*a(n) from A288206.

However, if we add this recursion to the shifted recursion a(n+5) = 3*a(n+4) - a(n+3) - 3*a(n+2) + 2*a(n+1), then we obtain the recursion above. This proves the conjecture.

(End)

From the analysis above it follows that the frequencies of 0 and 1 in (a(n)) exist and are equal to 3/4 and 1/4. - Michel Dekking, Oct 12 2018

Links

Clark Kimberling, Table of n, a(n) for n = 1..10000

Example

Iterates, starting with 00:
00
0010
00100100
001001000100100010
00100100010010001000100010010001000100

Mathematica

s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "010"}]
Table[w[n], {n, 0, 8}]
st = ToCharacterCode[w[11]] - 48   (* A288203 *)
Flatten[Position[st, 0]]  (* A288204 *)
Flatten[Position[st, 1]]  (* A288205 *)
Table[StringLength[w[n]], {n, 1, 35}] (* A288206 conjectured *)

Crossrefs

Cf. A288204, A288205, A288206.

Sequence in context: A080887 A099395 A182581 * A238470 A286748 A289001

Adjacent sequences: A288200 A288201 A288202 * A288204 A288205 A288206

Keyword

nonn,easy

Author

Clark Kimberling, Jun 07 2017

Status

approved