A288132 Fixed point of the mapping 00->0010, 1->11, starting with 00.

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

Offset

1

Comments

From Michel Dekking, Feb 18 2021: (Start)

This is a morphic sequence, i.e., the letter to letter image of a fixed point of a morphism. Let nu be the morphism on {0,1,2} given by

nu(0) = 0, nu(1) = 11, nu(2) = 210.

Let lambda be the letter to letter substitution given by

lambda(0) = 0, lambda(1) =1, lambda(2) = 0.

Let SR be the StringReplace procedure SR(00) = 0010, SR(1) = 11.

CLAIM 1: 0^{-1}SR^n(00) = lambda(nu^n(2)).

Proof: By induction. For n=1:

0^{-1}SR(00) = 0^{-1}0010 = 010 = lambda(nu(2)).

Suppose true for n. Then

0^{-1} SR^{n+1}(10) = 0^{-1}SR^n(0010) =

0^{-1}SR^n(00) [11]^{2n} 0 =

lambda(mu^n(2)) [11]^{2n} 0 =

lambda(nu^n(210))= lambda(nu{n+1}(2)).

Note that we proved that 0^{-1}SR^n(00) = (a(n+1)) is a morphic sequence, but it is general knowledge that x morphic => 0x morphic.

Let N_i(w) denote the number of letters i in the word w.

CLAIM 2: N_0(nu^n(2))=n, N_1(nu^n(2))=2^n-1, N_2(nu^n(2))=1, for n>0.

Proof: This follows directly from the same result for the morphism mu in A288381, since nu has the same incidence matrix as mu in A288381.

It follows from CLAIM 2 that the length |nu^n(2)| of nu^n(2) is equal to 2^n+n, and so by CLAIM 1, the length of SR^n(00) is equal to

|SR^n(00)| = 2^n + n + 1 = A005126(n).

This proves Kimberling's (corrected) conjecture in the MATHEMATICA program.

Next, let z(n) = A288133(n) be the positions of 0 in (a(n)). So z = 1, 2, 4, 7, 12, 21, 38, 71, 136, 265, 522, 1035,....

Observe that the (n+2)-th 0 occurs in lambda( mu^n(2)) at the end of mu^n(2) for n>1. It follows that

z(n+2) = 1+|mu^n(2)| = 2^n + n +1.

So z(n) = 2^{n-2} + n - 1 = A005126(n-2) for n>3.

(End)

Links

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

Example

Iterates, starting with 00:
00
0010
0010110
001011011110
001011011110111111110
00101101111011111111011111111111111110

Mathematica

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

Crossrefs

Cf. A288133, A288134, A078038.

Sequence in context: A143538 A242018 A324682 * A324903 A011656 A295309

Adjacent sequences: A288129 A288130 A288131 * A288133 A288134 A288135

Keyword

nonn,easy

Author

Clark Kimberling, Jun 07 2017

Extensions

Kimberling's conjecture on the length of the iterates corrected, and proved. - Michel Dekking, Feb 18 2021

Status

approved