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

%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.