|
|
A284116
|
|
a(n) = largest number of distinct words arising in Post's tag system {00, 1101} applied to a binary word w, over all starting words w of length n, or a(n) = -1 if there is a word w with an unbounded trajectory.
|
|
47
|
|
|
4, 7, 6, 7, 22, 23, 24, 25, 30, 31, 34, 421, 422, 423, 422, 423, 424, 2169, 2170, 2171, 2170, 2171, 2172, 2165, 2166, 2167, 24566, 24567, 24568, 24567, 24568, 24569, 24568, 24569, 24570, 253513, 253514, 342079, 342080, 342083, 342084, 342103, 20858070
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Post's tag system {00, 1101} 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.
It is an important open question to decide if there is any word whose orbit grows without limit. - N. J. A. Sloane, Jul 30 2017, based on an email from Allan C. Wechsler
Comment from Don Reble, Aug 01, 2017: For n <= 57, all words reach the empty word or a cycle. - N. J. A. Sloane, Aug 01 2017
A word w can be described by the pair (c, d) where c is the length of w and d is the number represented by the binary word w. Then 0 <= d < 2^c.
Appending a word ww of m letters to w is the same as setting d to 2^m * w + ww. Preserving only the rightmost q digits of w is the same as setting w to w mod 2^q.
Lastly, we're only really interested in the 1st, 4th, 7th, ... leftmost digits. The others could without loss of generality be set to 0. This can be done with bitand(x, y), with y in A033138.
Therefore this problem can be formulated as follows: Let w = (c, d).
Then if d < 2^(c - 1), w' = (c - 1, bitand(4*d, floor(2^(c + 1) / 7)))
else (if (d >= 2^(c - 1)), w' = (c + 1, bitand(16*d + 13, floor(2^(c + 3) / 7))).
To find a(n), it would be enough to check values d in A152111 with n binary digits and c = n.
(End)
|
|
REFERENCES
|
John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.
|
|
LINKS
|
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]
|
|
EXAMPLE
|
Suppose n=1. Then w = 0 ->000 -> w' = empty word, and w = 1 -> 11101 -> w' = 01 -> 0100 -> w'' = 0 -> 000 -> w''' = empty word. So a(1) = 4 by choosing w = 1.
For n = 5 the orbit of the word 10010 begins 10010, 101101, 1011101, ..., 0000110111011101, and the next word in the orbit has already appeared. The orbit consists of 22 distinct words.
The 5-letter word w = 10100 can be described as (a, b) = (5, 20). This is equivalent to (5, bitand(20, floor(2^7 / 7))) = (5, bitand(20, 18)) = (5, 16).
As 16 >= 2^(5-1), w' = (5 + 1, bitand(16*16 + 13, floor(2^(5 + 3) / 7))) = (6, bitand(279, 36)) = (6, 4). w'' = w = (5, 16) so 10100 ~ 10000 ends in a period. (End)
Words w that achieve a(1) through a(7) are 1, 10, 100, 0001, 10010, 100000, 0001000. - N. J. A. Sloane, Aug 17 2017
|
|
MATHEMATICA
|
Table[nmax = 0;
For[i = 0, i < 2^n, i++, lst = {};
w = IntegerString[i, 2, n];
While[! MemberQ[lst, w],
AppendTo[lst, w];
If[w == "", Break[]];
If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
w = StringDrop[w <> "1101", 3]]];
nmax = Max[nmax, Length[lst]]]; nmax, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)
(* Or, using the (c, d) procedure: *)
Table[nmax = 0;
For[i = 0, i < 2^n, i++,
c = n; d = i; lst = {};
While[! MemberQ[lst, {c, d}],
AppendTo[lst, {c, d}];
If[c == 0, Break[]];
If[ d < 2^(c - 1),
d = BitAnd[4*d, 2^(c - 1) - 1]; c--,
d = BitAnd[16*d + 13, 2^(c + 1) - 1]; c++]];
nmax = Max[nmax, Length[lst]]]; nmax, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)
|
|
CROSSREFS
|
Cf. A033138, A152111, A284119, A284121, A289670, A289671, A289672, A289673, A289674, A289675, A289676, A289677.
For the 3-shift tag systems {00,1101}, {00, 1011}, {00, 1110}, {00, 0111} see A284116, A291067, A291068, A291069 respectively (as well as the cross-referenced entries mentioned there).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Edited by N. J. A. Sloane, Jul 29 2017 and Oct 23 2017 (adding escape clause in case an infinite trajectory exists)
|
|
STATUS
|
approved
|
|
|
|