A288213 Fixed point of the mapping 00->0010, 1->011, starting with 00.

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

Offset

1

Comments

From Michel Dekking, Sep 27 2019: (Start)

This sequence is a morphic sequence, i.e, the letter-to-letter image of a fixed point of a morphism.

Proof: We note first that the mapping SR: 00->0010, 10->011, is an algorithmic procedure given by StringReplace in Mathematica. This makes it hard to describe iterates of it. However, in this particular case one can deal with this.

There are three types of 0's occurring in (a(n)). The first 0 in a pair 00, which we code by the letter F, the second 0 in a pair 00 which we code by the letter G, and the single 0 occurring between two 1's, coded by G. The 1 at the end of the iterates SR^n, we code by D ('dead'). The other 1's we code by A ('active').

So, if we denote this code by psi, then for example,

psi(SR(00)) = psi(0010) = FGAD,

psi(SR^2(00)) = psi(00100110) = FGAFGAAD.

Now consider the morphism sigma on the alphabet {F,G,D,A} given by

sigma(F) = FGA, sigma(G) = F, sigma(D) = D, sigma(A) = GAA.

Let pi be the inverse of psi: pi(F) = pi(G) = pi(D) = 0, pi(A) = 1.

Any word with prefix 00 and without occurrences of 000, is a concatenation of the three words u=00, v=1 and w=101. The SR-procedure acts context-free on such concatenations. One has

SR(u) = 0010, SR(v) = 011, SR(w) = 0110011.

The psi-images are

psi(u) = FG, psi(v) = A, psi(w) = AGA.

The sigma-images of these are

sigma(FG) = FGAF, sigma(A) = GAA, sigma(AGA) = GAAFGAA.

The pi-images of these are

pi sigma psi(u) = 0010, pi sigma psi(v) = 011, pi sigma psi(w) = 0110011.

We see that pi sigma psi acts exactly in the same way as SR.

It follows that (a(n)) = pi(x), where x = FGAFGAA... is the unique fixed point of sigma. QED

(End)

From Michel Dekking, Sep 27 2019: (Start)

Now that we know that this sequence is a morphic sequence, we may prove Kimberling's conjecture that the lengths of the words SR^n(00) are given by A182780.

Here b:=A182780 has b(0) = 2, b(1) = 4, and satisfies the linear recurrence b(n) = 3*b(n-1) - b(n-2) - b(n-3) for n>2.

The number of letters (F's, G's, D's and A's) in the word psi(SR^n(00)) is equal to the vector/matrix/vector product

(1,1,1,1) M^n (1,0,1,0)^T,

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

|1 1 0 0|

|1 0 0 1|

|0 0 1 0|

|1 0 0 2|.

The characteristic polynomial of M is equal to

chi(u) = u^4 - 4u^3 + 4u^2 - 1 = (u^3 - 3u^2 + u + 1)(u - 1).

Thus the conjecture is proved by an application of the Cayley-Hamilton theorem: M^3 = 3M^2 - M - Id.

(End)

From Michel Dekking, Sep 28 2019: (Start)

The application of Cayley-Hamilton is more subtle than suggested above. In fact chi(u) has a second factor u-1: chi(u) = (u^2-2u-1)(u-1)^2, but b=A182780 does not satisfy the Pell recurrence a(n) = 2*a(n-1) + a(n-2).

Removing the letter D from {F,G,D,A} gives a morphism tau defined by

tau(F) = FGA, tau(G) = F, tau(A) = GAA.

The iterates tau^n(F) are equal to the iterates sigma^n(FD), with the suffix D removed. So

|SR^n(00)|= |sigma^n(FD)|=|tau^n(F)|+1,

where |.| denotes length.

The characteristic polynomial of the incidence matrix of tau is equal to u^3-3u^2+u+1.

So, by the Cayley-Hamilton theorem, the sequence

(|tau^n(F)|) = 1,3,7,17,41,99,... = A078057=:c

satisfies the recurrence c(n) = 3c(n-1)-c(n-2)-c(n-3). This implies that the sequence (|SR^n(00)|) = (c(n)+1) satisfies the recurrence

b(n) = 3b(n-1) - b(n-2) - b(n-3). QED

(End)

Links

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

Formula

a(n) = A001953(n-1) mod 2 (conjectured). - Jon Maiga, Sep 27 2019

Example

Iterates, starting with 00:
00
0010
00100110
001001100100110110
001001100100110110010011001001101100110110

Mathematica

s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "011"}]
Table[w[n], {n, 0, 8}]
st = ToCharacterCode[w[11]] - 48   (* A288213 *)
Flatten[Position[st, 0]]  (* A288214 *)
Flatten[Position[st, 1]]  (* A288215 *)
Table[StringLength[w[n]], {n, 1, 35}] (* A182780 conjectured *)

Crossrefs

Cf. A001953, A288214, A288215, A182780.

Sequence in context: A354029 A189624 A014707 * A308187 A289007 A308901

Adjacent sequences: A288210 A288211 A288212 * A288214 A288215 A288216

Keyword

nonn,easy

Author

Clark Kimberling, Jun 07 2017

Status

approved