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

Links

Table of n, a(n) for n=1..35.

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

Cf. A289035, A293076, A293078.

Sequence in context: A306293 A307795 A065795 * A000801 A080105 A023557

Adjacent sequences: A293074 A293075 A293076 * A293078 A293079 A293080

Keyword

nonn,easy

Author

Clark Kimberling, Sep 30 2017

Status

approved