login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A289670 Consider the Post tag system defined in A284116; a(n) = number of binary words of length n which terminate at the empty word. 17
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

Don Reble, Table of n, a(n) for n = 1..57

Don Reble, Python program for A289670.

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]]]];

ne, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)

CROSSREFS

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

Sequence in context: A222935 A279059 A054243 * A005864 A112433 A171648

Adjacent sequences:  A289667 A289668 A289669 * A289671 A289672 A289673

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jul 29 2017

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.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 04:44 EDT 2020. Contains 337165 sequences. (Running on oeis4.)