|
|
A289670
|
|
Consider the Post tag system defined in A284116; a(n) = number of binary words of length n which terminate at the empty word.
|
|
18
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
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).
|
|
LINKS
|
|
|
EXAMPLE
|
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.
|
|
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]]]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|