login
A293077
Number of letters (0's and 1's) in the n-th iterate of the final-letter-removed mapping defined at A289035.
4
2, 4, 6, 10, 16, 26, 44, 74, 126, 214, 364, 620, 1058, 1806, 3082, 5260, 8978, 15326, 26162, 44660, 76238, 130146, 222172, 379270, 647454, 1105272, 1886816, 3220996, 5498584, 9386670, 16024048, 27354760, 46697496, 79717612, 136086476
OFFSET
1,1
COMMENTS
It follows from the comment at A289035 that every term is even.
The first seven iterates:
00
0010
001001
0010010010
0010010010001001
00100100100010010001001001
00100100100010010001001001000100100010010010
From Michel Dekking, Mar 20 2022: (Start)
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.
The difficulty is that the final-letter-removed mechanism does not give the usual iteration scheme. The crucial observation is that
N1(n) = a(n-1)/2.
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
00->0010, 01->010, 10->010.
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
(*) a(n) = 3*a(n-1)/2 + N00(n-1) - delta(n).
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.
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
a(n) = 2 a(n-1) - a(n-2) + 2*floor(a(n-2)/4).
(End)
FORMULA
a(n) = 2 a(n-1) - a(n-2) + 2 floor(a(n-2)/4) - Michel Dekking, Mar 20 2022
MATHEMATICA
z = 10; (* number of iterations *)
s = {0, 0}; u[0] = StringJoin[Map[ToString, s]]; w[0] = u[0];
u[n_] := u[n] = StringReplace[w[n - 1], {"00" -> "0010", "01" -> "010", "10" -> "010"}];
w[n_] := w[n] = If[OddQ[StringLength[u[n]]], StringDrop[u[n], -1], u[n]];
TableForm[Table[w[n], {n, 0, 8}]]
st = ToCharacterCode[w[z]] - 48 (* A289035 *)
p0 = Flatten[Position[st, 0]] (* A289036 *)
p1 = Flatten[Position[st, 1]] (* A289037 *)
v = Table[StringLength[w[n]], {n, 0, 34}] (* A293077 *)
v/2 (* A293078 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Sep 30 2017
STATUS
approved