The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A289674 Consider the Post tag system described in A284116 (but adapted to the alphabet {1,2}); sequence lists the words that belong to cycles. 10
21211, 112212, 21211221211, 112212112212, 221222121111, 1112212221211, 2122212111111, 2221211112212, 12111122122212, 12221222121111, 22121111112212, 122122212221211, 211111122122212, 1111221222122212, 21211221211221211, 21222122212111111, 112212112212112212 (list; graph; refs; listen; history; text; internal format)



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.


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]


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


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

Sequence in context: A109029 A284915 A252165 * A217265 A345563 A345564

Adjacent sequences: A289671 A289672 A289673 * A289675 A289676 A289677




N. J. A. Sloane, Jul 29 2017


Corrected and extended by Don Reble, Jul 31 2017

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



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 13:07 EDT 2023. Contains 361599 sequences. (Running on oeis4.)