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

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

Offset

1

Comments

Iterates of the mapping, starting with 00:

00

1000

0001000

100000001000

0001000100010000001000

10000000100000010000001000100000001000

The 0-limiting word is the limit of the n-th iterates even n.

Conjecture: the number of letters (0's and 1's) in the n-th iterate is given by A287439(n), for n >= 0.

From Michel Dekking, Mar 18 2018: (Start)

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 n-th 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^3-2u-2.

Thus the conjecture is proved by an application of the Cayley-Hamilton theorem:

M^3 = 2M + 2Id.

(End)

Links

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

Example

The first three n-th 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 (* Jean-François Alcover, Dec 17 2018 *)

Crossrefs

Cf. A287527, A287402, A287439, A287457 (1-limiting word).

Sequence in context: A188086 A105563 A188291 * A188221 A011765 A342023

Adjacent sequences: A287369 A287370 A287371 * A287373 A287374 A287375

Keyword

nonn,easy

Author

Clark Kimberling, Jun 17 2017

Status

approved