|
%I #14 Feb 06 2022 14:59:42
%S 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,
%T 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,
%U 1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1
%N Fixed point of the mapping 00->0001, 1->11, starting with 00.
%C Apparently this is A288132 shifted by one place (or index). - _R. J. Mathar_, Jun 14 2017
%C From _Michel Dekking_, Feb 18 2021: (Start)
%C 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.
%C CLAIM: for all n one has mu^n(2) 0 = 20 2^{-1} nu^n(2).
%C Proof: By induction. For n=1:
%C mu(2)0 = 2010 = 20 2^{-1}210 = 20 2^{-1}nu(2).
%C Suppose true for n. Then
%C mu^{n+1}(2) 0 = mu^n(201) 0 =
%C mu^n(2) mu^n(0) mu^n(1) 0 =
%C 20 2^{-1} nu^n(2) nu^n(1) 0 =
%C 20 2^{-1} nu^n(210) = 20 2^{-1} nu^{n+1}(2).
%C (End)
%C From _Michel Dekking_, Feb 18 2021: (Start)
%C 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
%C m(0) = 0, mu(1) = 11, mu(2) = 201.
%C Let lambda be the letter-to-letter substitution given by lambda(0) = 0, lambda(1) =1, lambda(2) = 0.
%C Let SR be the StringReplace procedure SR(00) = 0001, SR(1) = 11.
%C CLAIM 1: 0^{-1}SR^n(00) = lambda(mu^n(2)).
%C Proof: By induction. For n=1:
%C 0^{-1}SR(00) = 0^{-1}0001 = 001 = lambda(mu(2)).
%C Suppose true for n. Then
%C 0^{-1} SR^{n+1}(00) = 0^{-1}SR^n(0001) =
%C 0^{-1}SR^n(00) 0 [11]^{2n} =
%C lambda(mu^n(2)) 0 [11]^{2n} =
%C lambda(mu^n(201)) = lambda(mu{n+1}(2)).
%C 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.
%C Let N_i(w) denote the number of letters i in the word w.
%C 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.
%C 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.
%C Suppose true for n. Then
%C N_0(mu^{n+1}(2)) = N_0(mu^n(201)) = n + 1, and
%C N_1(mu^{n+1}(2)) = N_1(mu^n(201)) = 2^n - 1 + 2^n =2^{n+1} - 1.
%C 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
%C |SR^n(00)| = 2^n + n + 1 = A005126(n).
%C This proves Kimberling's conjecture in the MATHEMATICA program.
%C Next, let z(n) = A288382(n) be the positions of 0 in (a(n)). So z = 1, 2, 3, 5, 8, 13, 22, 39, ....
%C 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
%C z(n+2) = 1+|mu^n(2)| - 2^{n-1} = 1+ 2^n+n-2^{n-1} = 2^{n-1}+n+1.
%C So z(n) = 2^{n-3} + n - 1 = A052968(n-2) for n>3.
%C This proves Mathar's June 14, 2017 conjecture in A288382.
%C (End)
%H Clark Kimberling, <a href="/A288381/b288381.txt">Table of n, a(n) for n = 1..10000</a>
%e Iterates, starting with 00:
%e 00
%e 0001
%e 0001011
%e 000101101111
%e 000101101111011111111
%e 00010110111101111111101111111111111111
%t s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
%t w[n_] := StringReplace[w[n - 1], {"00" -> "0001", "1" -> "11"}]
%t Table[w[n], {n, 0, 8}]
%t st = ToCharacterCode[w[11]] - 48 (* A288381 *)
%t Flatten[Position[st, 0]] (* A288382 *)
%t Flatten[Position[st, 1]] (* A288383 *)
%t Table[StringLength[w[n]], {n, 1, 35}] (* A005126 conjectured *)
%Y Cf. A288382, A288383, A005126.
%K nonn,easy
%O 1
%A _Clark Kimberling_, Jun 10 2017
|
