%I #58 Sep 27 2019 07:57:48
%S 2,2,4,8,16,16,64,128,192,320,512,768,2560,6656,12288,21504,36864,
%T 81920,176128,327680,638976,1392640,2326528,4194304,9568256,17301504,
%U 30408704,65536000,121110528,220200960,484442112,962592768,1837105152,4026531840,8304721920,16206790656,34712059904,70934069248,140190416896
%N Consider the Post tag system defined in A284116; a(n) = number of binary words of length n which terminate at the empty word.
%C 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).
%H Don Reble, <a href="/A289670/b289670.txt">Table of n, a(n) for n = 1..57</a>
%H Don Reble, <a href="/A289670/a289670.txt">Python program for A289670.</a>
%e 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.
%p with(StringTools):
%p # Post's tag system applied once to w
%p # The empty string is represented by -1.
%p f1:=proc(w) local L,t0,t1,ws,w2;
%p t0:="00"; t1:="1101"; ws:=convert(w,string);
%p if ws[1]="0" then w2:=Join([ws,t0],""); else w2:=Join([ws,t1],""); fi;
%p L:=length(w2); if L <= 3 then return(-1); fi;
%p w2[4..L]; end;
%p # Post's tag system repeatedly applied to w (valid for |w| <= 11).
%p # Returns number of steps to reach empty string, or 999 if w cycles
%p P:=proc(w) local ws,i,M; global f1;
%p ws:=convert(w,string); M:=1;
%p for i from 1 to 38 do
%p M:=M+1; ws:=f1(ws); if ws = -1 then return(M); fi;
%p od; 999; end;
%p # Count strings of length n which terminate and which cycle
%p a0:=[]; a1:=[];
%p for n from 1 to 11 do
%p lprint("starting length ",n);
%p ter:=0; noter:=0;
%p for n1 from 0 to 2^n-1 do
%p t1:=convert(2^n+n1,base,2); t2:=[seq(t1[i],i=1..n)];
%p map(x->convert(x,string),t2); t3:=Join(%,""); t4:=P(%);
%p if t4=999 then noter:=noter+1; else ter:=ter+1; fi;
%p od;
%p a0:=[op(a0),ter]; a1:=[op(a1),noter];
%p od:
%p a0; a1;
%t Table[ne = 0;
%t For[i = 0, i < 2^n, i++, lst = {};
%t w = IntegerString[i, 2, n];
%t While[! MemberQ[lst, w],
%t AppendTo[lst, w];
%t If[w == "", ne++; Break[]];
%t If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
%t w = StringDrop[w <> "1101", 3]]]];
%t ne, {n, 1, 12}] (* _Robert Price_, Sep 26 2019 *)
%Y Cf. A284116, A284119, A284121, A289671, A289672, A289673, A289674, A289675.
%K nonn
%O 1,1
%A _N. J. A. Sloane_, Jul 29 2017
%E 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.