A289670 Consider the Post tag system defined in A284116; a(n) = number of binary words of length n which terminate at the empty word.

2, 2, 4, 8, 16, 16, 64, 128, 192, 320, 512, 768, 2560, 6656, 12288, 21504, 36864, 81920, 176128, 327680, 638976, 1392640, 2326528, 4194304, 9568256, 17301504, 30408704, 65536000, 121110528, 220200960, 484442112, 962592768, 1837105152, 4026531840, 8304721920, 16206790656, 34712059904, 70934069248, 140190416896

Offset: 1

Author

N. J. A. Sloane, Jul 29 2017

Keywords

• nonn

Comments

The orbit of a word may terminate at the empty word (this sequence and A289675), or enter a cycle (A289671, A289672, A289674), or grow without limit (it is not known if this ever happens).

Examples

			For length n=2, there are two words which terminate at the empty word, 00 and 01. For example, 00 -> 0 -> empty word. See A289675 for further examples.
		

Links

• Don Reble, Table of n, a(n) for n = 1..57
• Don Reble, Python program for A289670.

Crossrefs

Cf. A284116, A284119, A284121, A289671, A289672, A289673, A289674, A289675.

Programs

Maple

with(StringTools):
# Post's tag system applied once to w
# The empty string is represented by -1.
f1:=proc(w) local L,t0,t1,ws,w2;
t0:="00"; t1:="1101"; ws:=convert(w,string);
if ws[1]="0" then w2:=Join([ws,t0],""); else w2:=Join([ws,t1],"");  fi;
L:=length(w2); if L <= 3 then return(-1); fi;
w2[4..L]; end;
# Post's tag system repeatedly applied to w (valid for |w| <= 11).
# Returns number of steps to reach empty string, or 999 if w cycles
P:=proc(w) local ws,i,M; global f1;
ws:=convert(w,string); M:=1;
for i from 1 to 38 do
M:=M+1; ws:=f1(ws); if ws = -1 then return(M); fi;
od; 999; end;
# Count strings of length n which terminate and which cycle
a0:=[]; a1:=[];
for n from 1 to 11 do
lprint("starting length ",n);
ter:=0; noter:=0;
for n1 from 0 to 2^n-1 do
t1:=convert(2^n+n1,base,2); t2:=[seq(t1[i],i=1..n)];
map(x->convert(x,string),t2); t3:=Join(%,""); t4:=P(%);
if t4=999 then noter:=noter+1; else ter:=ter+1; fi;
od;
a0:=[op(a0),ter]; a1:=[op(a1),noter];
od:
a0; a1;

Mathematica

Table[ne = 0;
 For[i = 0, i < 2^n, i++, lst = {};
  w = IntegerString[i, 2, n];
  While[! MemberQ[lst, w],
   AppendTo[lst, w];
   If[w == "", ne++; Break[]];
   If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
    w = StringDrop[w <> "1101", 3]]]];
ne, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)

Extensions

a(12)-a(57) from Don Reble, Jul 30 2017 and Aug 01 2017; a(12)-a(39) confirmed by Sean A. Irvine, Jul 30 2017.