login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A291792 Numbers n such that Post's tag system started at the word (100)^n eventually dies (i.e., reaches the empty string). 11
5, 13, 14, 22, 25, 46, 47, 54, 63, 65, 70, 74, 78, 80, 91, 93, 106, 110, 117, 118, 128, 144, 148, 160, 166, 169, 190, 195, 199, 209, 222, 229, 234, 236, 239, 240, 243, 252, 254, 263, 264, 265, 266, 278, 281, 283, 286, 302, 304, 310, 324, 326, 327, 336, 339 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

These are the numbers such that A291793(n)=0, or equivalently A284121(n)=1.

Comments from Lars Blomberg on the method used in calculating the terms, Sep 14 2017: (Start)

Here is an overview of the method I have been using.

Build the words in a large byte array. Each iteration just adds 00 or 1101 to the end and removes 3 bytes from the beginning, without moving the whole word, just keeping track of the length of the word and where it starts within the array.

When the word reaches the end of the array it is moved to the beginning.  This allows for very fast iterations, as long as the word is substantially shorter than the array.

The size of the byte array is 10^9, this is the longest word we can handle.

As for cycle detection, the words at iterations A: k*10^5 and B: (k+1)*10^5 are saved.

For iterations above B when the current word has same length as B (a fast test), then check if the current word is equal to the one at B. If so, we have a cycle whose length can be determined simply by continue iterating.  When the current iteration reaches C: (k+2)*10^5, move B->A, C->B, and continue.

The cycle has started somewhere between A and B and we know the cycle length. So restart two iterations at A and initially iterate one of them by the cycle length. Then iterate the two in parallel (being a cycle length apart) until they are equal, which gives the start of the cycle. Only the two words being iterated need to be stored.

One drawback with this method is that it cannot detect a cycle longer than 10^5 (or whatever value we choose). In that case the iterations will go on forever.

(End)

The trajectory of the word (100)^n for n=110 dies after 43913328040672 iterations, so 110 is a term in this sequence. The longest word in the trajectory is 31299218, which appeared at iteration 14392308412264. Lars Blomberg, Oct 04, 2017

LINKS

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

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

N. J. A. Sloane, Maple code for A291792, A284119, A291793, A284121), A291794, A291795, A291796, A292089, A292090, A292091, A292092, A292093, A292094.

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)

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]

CROSSREFS

Cf. A284116, A284119, A284121, A291793.

Asveld's Table 1 gives data about the behavior of Post's 3-shift tag system {00/1101} applied to the word (100)^n. The first column gives n, the nonzero values in column 2 give A291792, and columns 3 through 7 give A284119, 291793 (or A284121), A291794, A291795, A291796. For the corresponding data for Watanabe's 3-shift tag system {00/1011} applied to (100)^n see A292089, A292090, A292091, A292092, A292093, A292094.

Sequence in context: A244435 A134202 A191382 * A292565 A174069 A020996

Adjacent sequences:  A291789 A291790 A291791 * A291793 A291794 A291795

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Sep 04 2017

EXTENSIONS

a(8)-a(17) from Lars Blomberg, Sep 08 2017

a(18)-a(55) from Lars Blomberg, Oct 15 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 August 24 13:48 EDT 2019. Contains 326279 sequences. (Running on oeis4.)