A284116 -id:A284116 - 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.

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

Offset: 1

N. J. A. Sloane, Jul 29 2017

nonn

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

			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.

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

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

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;

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 *)

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.

A289671 Consider the Post tag system defined in A284116; a(n) = number of binary words of length n which terminate in a cycle.

Original entry on oeis.org

0, 2, 4, 8, 16, 48, 64, 128, 320, 704, 1536, 3328, 5632, 9728, 20480, 44032, 94208, 180224, 348160, 720896, 1458176, 2801664, 6062080, 12582912, 23986176, 49807360, 103809024, 202899456, 415760384, 853540864, 1663041536, 3332374528, 6752829440, 13153337344, 26055016448

Offset: 1

N. J. A. Sloane, Jul 29 2017

nonn

For n such that no binary word of length n has an infinite orbit under the Post tag system (cf. A284116), which includes all n <= 57, a(n) + A289670(n) = 2^n.

			For length n=2, there are two words which cycle, 10 and 11: 10 -> 101 -> 1101 -> 11101 -> 011101 -> 10100 -> 001101 -> 10100, which has entered a cycle.

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

Cf. A284116, A284119, A284121, A289670-A289674.

A289675 lists the initial words that terminate at the empty string.

Maple
```
See A289670.
```

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]]]];
2^n - ne, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)

A289673 Take n-th string over {1,2} in lexicographic order and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}) just once.

Original entry on oeis.org

-1, 12, 1, 1, 212, 212, 11, 11, 11, 11, 2212, 2212, 2212, 2212, 111, 211, 111, 211, 111, 211, 111, 211, 12212, 22212, 12212, 22212, 12212, 22212, 12212, 22212, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 112212

Offset: 1

N. J. A. Sloane, Jul 29 2017

sign

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
The empty word is denoted by -1.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.

			The initial words are:
1,2,11,12,21,22,111,112,121,122,211,212,221,222,1111,...
Applying the tag system over {1,2} these become:
-1, 12, 1, 1, 212, 212, 11, 11, 11, 11, 2212, 2212, 2212, 2212, 111, ...
If we were working over {0,1} the initial strings would be:
0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,...
and applying the tag system over {0,1} described in A284116 these would become:
-1, 01, 0, 0, 101, 101, 00, 00, 00, 00, 1101, 1101, 1101, 1101, 000, ...

Chai Wah Wu, Table of n, a(n) for n = 1..10000

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

A289674 Consider the Post tag system described in A284116 (but adapted to the alphabet {1,2}); sequence lists the words that belong to cycles.

Original entry on oeis.org

21211, 112212, 21211221211, 112212112212, 221222121111, 1112212221211, 2122212111111, 2221211112212, 12111122122212, 12221222121111, 22121111112212, 122122212221211, 211111122122212, 1111221222122212, 21211221211221211, 21222122212111111, 112212112212112212

Offset: 1

N. J. A. Sloane, Jul 29 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
Under this Post tag system, some words when iterated end at the empty word, others go into cycles, and others may have an orbit which grows without limit. See A289670 and A289671 for the counts of the first two types. This sequence gives a list of the words that belong to cycles.
It is an important open question to decide if there is any word whose orbit grows without limit.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.

			The first two cycles that one encounters when applying the Post tag system to words over the alphabet {1,2} are (21211, 112212) and (2122212111111, 22121111112212, 211111122122212, 1111221222122212, 122122212221211, 12221222121111).

Chai Wah Wu, Table of n, a(n) for n = 1..253 (terms < 10^49)
Shigeru Watanabe, Periodicity of Post's normal process of tag, in Jerome Fox, ed., Proceedings of Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press, Polytechnic Institute of Brooklyn, 1963, pp. 83-99. [Annotated scanned copy]

Cf. A284116, A284119, A284121, A289670-A289675.

Corrected and extended by Don Reble, Jul 31 2017

Terms sorted and more terms added by Chai Wah Wu, Aug 05 2017

A289675 Consider the Post tag system described in A284116 (but adapted to the alphabet {1,2}) ; sequence lists the words that terminate in the empty word.

Original entry on oeis.org

1, 2, 11, 12, 111, 112, 121, 122, 1111, 1121, 1211, 1221, 2111, 2121, 2211, 2221, 11111, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122, 12211, 12212, 12221, 12222, 111111, 111112, 111121, 111122, 112111, 112112, 112121, 112122, 121111, 121112, 121121, 121122, 122111, 122112, 122121, 122122

Offset: 1

N. J. A. Sloane, Jul 30 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
Under this Post tag system, some words when iterated end at the empty word, others go into cycles, and others may have an orbit which grows without limit. See A289670 and A289671 for the counts of the first two types. This sequence gives a list of the words that end at the empty word.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.
Stillwell (2016, page 100) remarks that Post was unable to find an algorithm to determine which words belong to this sequence, "and in fact this particular `halting problem' remains unsolved to this day".

			Working over the more usual alphabet {0,1}, the following are the orbits of the first few words that terminate at the empty word:
[0, -1]
[1, 01, 0, -1]
[00, 0, -1]
[01, 0, -1]
[000, 00, 0, -1]
[001, 00, 0, -1]
[010, 00, 0, -1]
[011, 00, 0, -1]
[0000, 000, 00, 0, -1]
[0010, 000, 00, 0, -1]
[0100, 000, 00, 0, -1]
[0110, 000, 00, 0, -1]
[1000, 01101, 0100, 000, 00, 0, -1]
[1010, 01101, 0100, 000, 00, 0, -1]
[1100, 01101, 0100, 000, 00, 0, -1]
[1110, 01101, 0100, 000, 00, 0, -1]
[00000, 0000, 000, 00, 0, -1]
...
Writing the initial words in this list over {1,2} rather than {0,1} gives the sequence.

John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.

Rémy Sigrist, Table of n, a(n) for n = 1..25000
Emil L. Post, Formal Reductions of the General Combinatorial Decision Problem, Amer. J. Math. 65, 197-215, 1943. See page 204.

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

A289675 = {};
Do[For[i = 0, i < 2^n, i++, lst = {};
   w = IntegerString[i, 2, n];
   While[! MemberQ[lst, w],
    AppendTo[lst, w];
    If[w == "", AppendTo[A289675, IntegerString[i, 2, n]]; Break[]];
    If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
     w = StringDrop[w <> "1101", 3]]]], {n, 6}];
Map[StringReplace[#, {"1" -> "2", "0" -> "1"}] &, A289675]
(* Robert Price, Sep 26 2019 *)

A289672 Consider the Post tag system defined in A284116; a(n) = maximum, taken over all binary words w of length n which terminate in a cycle, of the number of words in the orbit of w.

Original entry on oeis.org

4, 3, 4, 7, 8, 7, 14, 15, 14, 15, 16, 15, 24, 25, 28, 29, 30, 35, 38, 39, 38, 39, 38

Offset: 1

N. J. A. Sloane, Jul 29 2017

The terminating empty word is included in the count.

			For length n=2, there are two words which cycle, 10 and 11:
10 -> 101 -> 1101 -> 11101 -> 011101 -> 10100 -> 001101 -> 10100, which has entered a cycle.

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

# Uses procedures f1 and P from A289670.
# Count strings of length n which terminate and which cycle
# Print max length to reach empty word (mx)
mx:=[];
for n from 1 to 11 do
lprint("starting length ",n);
m:=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 if t4>m then m:=t4; fi; fi;
od;
mx:=[op(mx),m];
od:
mx;

a(12)-a(23) from Indranil Ghosh, Jul 30 2017

A291798 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = preperiod (or threshold) of orbit of that word.

Original entry on oeis.org

3, 4, 6, 2, 17, 15, 9, 11, 13, 14, 16, 12, 24, 10, 12, 19, 14, 23, 21, 4, 13, 9, 25, 11, 29, 27, 3, 7, 420, 25, 15, 24, 28, 6, 17, 19, 28, 4, 26, 21, 23, 419, 6, 417, 46, 24, 8, 5, 421, 26, 28, 415, 12, 413, 10, 44, 27, 10, 40, 22, 84, 411, 18, 20, 29, 9, 11

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.
This is an analog of A284119 for the words in A291797.

Lars Blomberg, Table of n, a(n) for n = 1..8190 (For terms in A291797 up to length 36.)
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102. See Table 3.

Cf. A284116, A284119, A291797.

a(31)-a(67) from Lars Blomberg, Sep 08 2017

A291799 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = period of orbit of that word, or 0 if the orbit ends at the empty word.

Original entry on oeis.org

0, 2, 0, 2, 6, 6, 0, 0, 0, 6, 6, 6, 6, 6, 0, 6, 0, 6, 6, 2, 6, 6, 6, 6, 6, 6, 4, 6, 0, 6, 0, 6, 6, 4, 0, 0, 6, 6, 6, 0, 0, 0, 6, 0, 6, 6, 4, 6, 0, 6, 6, 0, 6, 0, 6, 6, 0, 6, 6, 6, 10, 0, 0, 0, 6, 6, 4, 6, 6, 6, 0, 4, 0, 0, 0, 6, 6, 6, 0, 6, 4, 6, 6, 2, 6, 6, 6

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.
This is an analog of A291793 (or A284121) for the words in A291797.

Lars Blomberg, Table of n, a(n) for n = 1..8190 (For terms in A291797 up to length 36.)
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102. See Table 3.

Cf. A284116, A284121, A291793, A291797.

a(31)-a(87) from Lars Blomberg, Sep 08 2017

A291800 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = length of first word we see in the orbit of that word that is in the cycle, if the orbit cycles, or 0 if the orbit reaches the empty string, or -1 if the orbit is unbounded.

Original entry on oeis.org

0, 5, 0, 6, 15, 15, 0, 0, 0, 15, 15, 15, 15, 15, 0, 15, 0, 15, 15, 12, 15, 15, 15, 15, 19, 19, 13, 15, 0, 19, 0, 15, 15, 13, 0, 0, 15, 15, 15, 0, 0, 0, 13, 0, 19, 19, 13, 14, 0, 19, 19, 0, 17, 0, 13, 19, 0, 17, 19, 19, 31, 0, 0, 0, 15, 13, 13, 19, 13, 19, 0

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.
This is an analog of A291794 for the words in A291797.

Lars Blomberg, Table of n, a(n) for n = 1..8190 (For terms in A291797 up to length 36.)
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102. See Table 3.

Cf. A284116, A291794, A291797.

a(31)-a(71) from Lars Blomberg, Sep 08 2017

A291801 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = length of the longest word in the orbit, or -1 if the orbit is unbounded.

Original entry on oeis.org

3, 6, 6, 6, 16, 16, 9, 9, 9, 16, 16, 16, 16, 16, 12, 16, 12, 16, 16, 12, 16, 16, 16, 16, 22, 22, 14, 16, 56, 22, 15, 16, 16, 15, 15, 15, 16, 16, 16, 15, 15, 56, 16, 56, 22, 22, 16, 16, 56, 22, 22, 56, 20, 56, 17, 22, 18, 20, 22, 22, 34, 56, 18, 18, 18, 18, 18

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.
This is an analog of A291795 for the words in A291797.

Lars Blomberg, Table of n, a(n) for n = 1..8190 (For terms in A291797 up to length 36.)
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102. See Table 3.

Cf. A284116, A291794, A291795, A291797.

a(31)-a(67) from Lars Blomberg, Sep 08 2017

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A289671 Consider the Post tag system defined in A284116; a(n) = number of binary words of length n which terminate in a cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A289673 Take n-th string over {1,2} in lexicographic order and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}) just once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Extensions

A289674 Consider the Post tag system described in A284116 (but adapted to the alphabet {1,2}); sequence lists the words that belong to cycles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A289675 Consider the Post tag system described in A284116 (but adapted to the alphabet {1,2}) ; sequence lists the words that terminate in the empty word.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A289672 Consider the Post tag system defined in A284116; a(n) = maximum, taken over all binary words w of length n which terminate in a cycle, of the number of words in the orbit of w.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Extensions

A291798 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = preperiod (or threshold) of orbit of that word.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A291799 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = period of orbit of that word, or 0 if the orbit ends at the empty word.

Views

Author

Keywords

Comments

Links