login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #26 Mar 23 2022 12:56:18

%S 2,4,6,10,16,26,44,74,126,214,364,620,1058,1806,3082,5260,8978,15326,

%T 26162,44660,76238,130146,222172,379270,647454,1105272,1886816,

%U 3220996,5498584,9386670,16024048,27354760,46697496,79717612,136086476

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

%C It follows from the comment at A289035 that every term is even.

%C The first seven iterates:

%C 00

%C 0010

%C 001001

%C 0010010010

%C 0010010010001001

%C 00100100100010010001001001

%C 00100100100010010001001001000100100010010010

%C From _Michel Dekking_, Mar 20 2022: (Start)

%C 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 The difficulty is that the final-letter-removed mechanism does not give the usual iteration scheme. The crucial observation is that

%C N1(n) = a(n-1)/2.

%C 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 00->0010, 01->010, 10->010.

%C 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 (*) a(n) = 3*a(n-1)/2 + N00(n-1) - delta(n).

%C 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 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 a(n) = 2 a(n-1) - a(n-2) + 2*floor(a(n-2)/4).

%C (End)

%F a(n) = 2 a(n-1) - a(n-2) + 2 floor(a(n-2)/4) - _Michel Dekking_, Mar 20 2022

%t z = 10; (* number of iterations *)

%t s = {0, 0}; u[0] = StringJoin[Map[ToString, s]]; w[0] = u[0];

%t u[n_] := u[n] = StringReplace[w[n - 1], {"00" -> "0010", "01" -> "010", "10" -> "010"}];

%t w[n_] := w[n] = If[OddQ[StringLength[u[n]]], StringDrop[u[n], -1], u[n]];

%t TableForm[Table[w[n], {n, 0, 8}]]

%t st = ToCharacterCode[w[z]] - 48 (* A289035 *)

%t p0 = Flatten[Position[st, 0]] (* A289036 *)

%t p1 = Flatten[Position[st, 1]] (* A289037 *)

%t v = Table[StringLength[w[n]], {n, 0, 34}] (* A293077 *)

%t v/2 (* A293078 *)

%Y Cf. A289035, A293076, A293078.

%K nonn,easy

%O 1,1

%A _Clark Kimberling_, Sep 30 2017