A288381 Fixed point of the mapping 00->0001, 1->11, starting with 00.

0, 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

Offset

1

Comments

Apparently this is A288132 shifted by one place (or index). - R. J. Mathar, Jun 14 2017

From Michel Dekking, Feb 18 2021: (Start)

Proof of Mathar's conjecture: obviously, a(2) = A288132(1), and we know that (a(n): n>1) is generated by a morphism mu (see below), and (A288132(n): n>1) is generated by a morphism nu (see A288132), given by nu(0)=0, nu(1)=11, nu(2)=210, both followed by replacing the letter 2 with the letter 0. Mathar's conjecture will therefore be a consequence of the following claim. Note that the shifting by one place occurs via the prefix 20 2^{-1} on the right side.

CLAIM: for all n one has mu^n(2) 0 = 20 2^{-1} nu^n(2).

Proof: By induction. For n=1:

mu(2)0 = 2010 = 20 2^{-1}210 = 20 2^{-1}nu(2).

Suppose true for n. Then

mu^{n+1}(2) 0 = mu^n(201) 0 =

mu^n(2) mu^n(0) mu^n(1) 0 =

20 2^{-1} nu^n(2) nu^n(1) 0 =

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

(End)

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 mu be the morphism on {0,1,2} given by

m(0) = 0, mu(1) = 11, mu(2) = 201.

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) = 0001, SR(1) = 11.

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

Proof: By induction. For n=1:

0^{-1}SR(00) = 0^{-1}0001 = 001 = lambda(mu(2)).

Suppose true for n. Then

0^{-1} SR^{n+1}(00) = 0^{-1}SR^n(0001) =

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

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

lambda(mu^n(201)) = lambda(mu{n+1}(2)).

Note that we proved that 0^{-1}SR^n(00) = (a(n): 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(mu^n(2))=n, N_1(mu^n(2))=2^n-1, N_2(mu^n(2))=1, for n>0.

Proof: Here N_2(mu^n(2)) = 1 for all n>0, is obvious. For 0 and 1 we use induction. For n=1: N_0(mu(2)) = 1, N_1(mu(2)) = 1.

Suppose true for n. Then

N_0(mu^{n+1}(2)) = N_0(mu^n(201)) = n + 1, and

N_1(mu^{n+1}(2)) = N_1(mu^n(201)) = 2^n - 1 + 2^n =2^{n+1} - 1.

It follows from CLAIM 2 that the length |mu^n(2)| of mu^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 conjecture in the MATHEMATICA program.

Next, let z(n) = A288382(n) be the positions of 0 in (a(n)). So z = 1, 2, 3, 5, 8, 13, 22, 39, ....

Observe that the (n+2)-th 0 occurs in lambda(mu^n(2)) right before the suffix [11]^{n-1} for n>1. It follows that

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

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

This proves Mathar's June 14, 2017 conjecture in A288382.

(End)

Links

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

Example

Iterates, starting with 00:
00
0001
0001011
000101101111
000101101111011111111
00010110111101111111101111111111111111

Mathematica

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

Crossrefs

Cf. A288382, A288383, A005126.

Sequence in context: A066247 A151774 A095792 * A169675 A093385 A350866

Adjacent sequences: A288378 A288379 A288380 * A288382 A288383 A288384

Keyword

nonn,easy

Author

Clark Kimberling, Jun 10 2017

Status

approved