login
A288203
Fixed point of the mapping 00->0010, 1->010, starting with 00.
4
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
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
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Jun 07 2017
STATUS
approved