cp's OEIS Frontend

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

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