cp's OEIS Frontend

A293077 Number of letters (0's and 1's) in the n-th iterate of the final-letter-removed mapping defined at A289035.

%I A293077 #26 Mar 23 2022 12:56:18
%S A293077 2,4,6,10,16,26,44,74,126,214,364,620,1058,1806,3082,5260,8978,15326,
%T A293077 26162,44660,76238,130146,222172,379270,647454,1105272,1886816,
%U A293077 3220996,5498584,9386670,16024048,27354760,46697496,79717612,136086476
%N A293077 Number of letters (0's and 1's) in the n-th iterate of the final-letter-removed mapping defined at A289035.
%C A293077 It follows from the comment at A289035 that every term is even.
%C A293077 The first seven iterates:
%C A293077 00
%C A293077 0010
%C A293077 001001
%C A293077 0010010010
%C A293077 0010010010001001
%C A293077 00100100100010010001001001
%C A293077 00100100100010010001001001000100100010010010
%C A293077 From _Michel Dekking_, Mar 20 2022: (Start)
%C A293077 Proof of the recursion in FORMULA: Let N1(n) be the number of 1's in the n-th iterate theta(n) of the final-letter-removed mapping defined in A289035.
%C A293077 The difficulty is that the final-letter-removed mechanism does not give the usual iteration scheme. The crucial observation is that
%C A293077       N1(n) = a(n-1)/2.
%C A293077 The reason is simple: theta(n-1) has a(n-1)/2 two-blocks at even positions, and each of them generates exactly one letter 1 in the word theta(n), since
%C A293077       00->0010, 01->010, 10->010.
%C A293077 Next we compute the length a(n) of theta(n). Let N00(n-1) be the number of blocks 00 occurring at even positions in theta(n-1), and let delta(n)= 0 if the final letter was not removed to obtain theta(n), and delta(n)= 1 if the final letter was removed. Then
%C A293077 (*)      a(n) = 3*a(n-1)/2 + N00(n-1) - delta(n).
%C A293077 This holds because all a(n-1)/2 two-blocks at even positions generate a word of length at least 3, and the 00 blocks a word of length 4 = 3+1.
%C A293077 We have N00(n-1) = a(n-1)/2 - N1(n-1), and delta(n) = a(n)/2 - 2*floor(a(n)/2). The latter gives an awkward formula when substituted in (*), so we note that delta(n) is 1 iff N1(n-1) is odd iff a(n-2)/2 is odd. This gives delta(n) = a(n-2)/2 - 2*floor(a(n-2)/4). Substituting all this in (*) yields
%C A293077       a(n) = 2 a(n-1) - a(n-2) + 2*floor(a(n-2)/4).
%C A293077 (End)
%F A293077 a(n) = 2 a(n-1) - a(n-2) + 2 floor(a(n-2)/4) - _Michel Dekking_, Mar 20 2022
%t A293077 z = 10; (* number of iterations *)
%t A293077 s = {0, 0}; u[0] = StringJoin[Map[ToString, s]]; w[0] = u[0];
%t A293077 u[n_] := u[n] = StringReplace[w[n - 1], {"00" -> "0010", "01" -> "010", "10" -> "010"}];
%t A293077 w[n_] := w[n] = If[OddQ[StringLength[u[n]]], StringDrop[u[n], -1], u[n]];
%t A293077 TableForm[Table[w[n], {n, 0, 8}]]
%t A293077 st = ToCharacterCode[w[z]] - 48  (* A289035 *)
%t A293077 p0 = Flatten[Position[st, 0]] (* A289036 *)
%t A293077 p1 = Flatten[Position[st, 1]]  (* A289037 *)
%t A293077 v = Table[StringLength[w[n]], {n, 0, 34}] (* A293077 *)
%t A293077 v/2  (* A293078 *)
%Y A293077 Cf. A289035, A293076, A293078.
%K A293077 nonn,easy
%O A293077 1,1
%A A293077 _Clark Kimberling_, Sep 30 2017