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

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

Author

Clark Kimberling, Sep 30 2017

Keywords

• nonn
• easy

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)

Crossrefs

Cf. A289035, A293076, A293078.

Programs

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 *)

Formula

a(n) = 2 a(n-1) - a(n-2) + 2 floor(a(n-2)/4) - Michel Dekking, Mar 20 2022