A284119 Preperiod (or threshold) of orbit of Post's {00, 1101} tag system applied to the word (100)^n, or -1 if this word has an unbounded trajectory.

4, 15, 10, 25, 411, 47, 2128, 853, 372, 2805, 366, 2603, 703, 37912, 612, 127, 998, 2401, 1200, 623, 5280, 1778, 1462, 4346269, 4129, 3241, 7018, 3885, 14632, 7019, 4564, 4277, 147688, 1857, 11120, 81141, 20204, 3847, 116014, 7635, 6488, 5665, 6142, 73515, 5826, 6062, 3781, 7865, 28630

Offset

1,1

Comments

Post's tag system maps a word w over {0,1} to w', where if w begins with 0, w' is obtained by appending 00 to w and deleting the first three letters, or if w begins with 1, w' is obtained by appending 1101 to w and deleting the first three letters.

The empty word is included in the count.

The orbit of the word (100)^n for n=110 dies after 43913328040672 iterations. The longest word in the orbit is 31299218, which appeared at iteration 14392308412264. See also A291792. - Lars Blomberg, Oct 04, 2017

Links

Lars Blomberg, Table of n, a(n) for n = 1..6075

Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.

Lars Blomberg, Graph of the terms

Lars Blomberg, Graph of preperiod of a(110)

Lars Blomberg, Graph of preperiod of a(4974)

N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Formula

From Lars Blomberg, Apr 20 2018: (Start)

Using Excel, trendlines were created for the preperiod of the Post Tag and Watanabe Tag systems as follows:

A284119: y = 8.6528*x^2.0831, R^2 = 0.478.

A292090: y = 8.5595*x^2.1033, R^2 = 0.472.

Although the error value is rather large, the curves are quite similar. (End)

Example

For n = 2 the orbit of (100)^2 = 100100 consists of a preperiod of length 15, followed by a periodic portion of length 6:
Preperiod:
100100,
1001101,
11011101,
111011101,
0111011101,
101110100,
1101001101,
10011011101,
110111011101,
1110111011101,
01110111011101,
1011101110100,
11011101001101,
111010011011101,
0100110111011101,
followed by the period:
(011011101110100,
01110111010000,
1011101000000,
11010000001101,
100000011011101,
0000110111011101)
(repeat)

Crossrefs

Cf. A284116, A284121, A292090.

Sequence in context: A154068 A309526 A126601 * A290377 A332767 A095331

Adjacent sequences: A284116 A284117 A284118 * A284120 A284121 A284122

Keyword

nonn

Author

Jeffrey Shallit, Mar 20 2017

Extensions

Edited by N. J. A. Sloane, Jul 29 2017. Added "escape clause" to the definition, Apr 19 2018.

Status

approved