

A287372


0limiting word of the mapping 00>1000, 10>000, starting with 00.


9



0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1


COMMENTS

Iterates of the mapping, starting with 00:
00
1000
0001000
100000001000
0001000100010000001000
10000000100000010000001000100000001000
The 0limiting word is the limit of the nth iterates even n.
Conjecture: the number of letters (0's and 1's) in the nth iterate is given by A287439(n), for n >= 0.
Here is a proof of the conjecture. We note first that the mapping SR: 00>1000, 10>000, is an algorithmic procedure given by StringReplace in Mathematica. This makes it hard to describe iterates of it. However, in this particular case there is a way to deal with this. Let
w1:=00, w2:=1000, w3:=0001000.
Then
SR(00) = w2, SR^2(00) = SR(w2) = w3, SR^3(00)=SR(w3) = w2w1w1w2.
Moreover, the 'isolated' 1's do not occur at any border of w1, w2 or w3. It follows from this that SR acts context free on the semigroup generated by {w1,w2,w3}.
Let sigma be the morphism on the alphabet {1,2,3} given by
sigma(1) = 2, sigma(2) = 3, sigma(3) = 2112.
Then it is not hard to see that
delta(sigma^n(1)) = SR^n(00) for n=0,1,2,...,
where delta is the 'decoration' morphism defined by
delta(1) = 00, delta(2) = 1000, delta(3) = 0001000.
From this it follows that
(a(n)) = delta(x),
where x = (x(n)) is the infinite word with x(1)=3 fixed by sigma^2, i.e., sigma^2(x)=x.
Note that we also proved that the number of letters (0's and 1's) in the nth iterate of SR is equal to the vector/matrix/vector product
(2,4,7) M^n (1,0,0)^T,
where (1,0,0)^T is the transpose of (1,0,0), and M is the incidence matrix of the morphism sigma, i.e., M equals
0 0 2
1 0 2
0 1 0.
The characteristic polynomial of M is equal to chi(u) = u^32u2.
Thus the conjecture is proved by an application of the CayleyHamilton theorem:
M^3 = 2M + 2Id.
(End)


LINKS



EXAMPLE

The first three nth iterates for even n
00
0001000
0001000100010000001000


MATHEMATICA

s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
w[n_] := StringReplace[w[n  1], {"00" > "1000", "10" > "000"}]
Table[w[n], {n, 0, 8}]
st = ToCharacterCode[w[22]]  48 (* A287372 *)
Flatten[Position[st, 0]] (* A287527 *)
Flatten[Position[st, 1]] (* A287402 *)
Table[StringLength[w[n]], {n, 0, 30}] (* A287439 *)
(* Second program: *)
SubstitutionSystem[{"00" > "1000", "10" > "000"}, "00", 8] // Last // Characters // ToExpression (* JeanFrançois Alcover, Dec 17 2018 *)


CROSSREFS



KEYWORD

nonn,easy


AUTHOR



STATUS

approved



