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
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Jun 10 2017
STATUS
approved