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

Author

Jeffrey Shallit, Mar 20 2017

Keywords

• nonn

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

Examples

			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)
		

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)

Crossrefs

Cf. A284116, A284121, A292090.

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)

Extensions

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