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.
Original entry on oeis.org
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
Offset: 1
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.
From _David A. Corneth_, Aug 02 2017: (Start)
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
- John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.
- Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
- Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent, 2007.
- Liesbeth De Mol, Tag systems and Collatz-like functions Theoret. Comput. Sci. 390 (2008), no. 1, 92-101.
- Liesbeth De Mol, On the complex behavior of simple tag systems—an experimental approach, Theoret. Comput. Sci. 412 (2011), no. 1-2, 97-112.
- Emil L. Post, Formal Reductions of the General Combinatorial Decision Problem, Amer. J. Math. 65, 197-215, 1943. See page 204.
- Don Reble, Python program for A289670.
- 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]
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).
-
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 *)
Edited by
N. J. A. Sloane, Jul 29 2017 and Oct 23 2017 (adding escape clause in case an infinite trajectory exists)
A289670
Consider the Post tag system defined in A284116; a(n) = number of binary words of length n which terminate at the empty word.
Original entry on oeis.org
2, 2, 4, 8, 16, 16, 64, 128, 192, 320, 512, 768, 2560, 6656, 12288, 21504, 36864, 81920, 176128, 327680, 638976, 1392640, 2326528, 4194304, 9568256, 17301504, 30408704, 65536000, 121110528, 220200960, 484442112, 962592768, 1837105152, 4026531840, 8304721920, 16206790656, 34712059904, 70934069248, 140190416896
Offset: 1
For length n=2, there are two words which terminate at the empty word, 00 and 01. For example, 00 -> 0 -> empty word. See A289675 for further examples.
-
with(StringTools):
# Post's tag system applied once to w
# The empty string is represented by -1.
f1:=proc(w) local L,t0,t1,ws,w2;
t0:="00"; t1:="1101"; ws:=convert(w,string);
if ws[1]="0" then w2:=Join([ws,t0],""); else w2:=Join([ws,t1],""); fi;
L:=length(w2); if L <= 3 then return(-1); fi;
w2[4..L]; end;
# Post's tag system repeatedly applied to w (valid for |w| <= 11).
# Returns number of steps to reach empty string, or 999 if w cycles
P:=proc(w) local ws,i,M; global f1;
ws:=convert(w,string); M:=1;
for i from 1 to 38 do
M:=M+1; ws:=f1(ws); if ws = -1 then return(M); fi;
od; 999; end;
# Count strings of length n which terminate and which cycle
a0:=[]; a1:=[];
for n from 1 to 11 do
lprint("starting length ",n);
ter:=0; noter:=0;
for n1 from 0 to 2^n-1 do
t1:=convert(2^n+n1,base,2); t2:=[seq(t1[i],i=1..n)];
map(x->convert(x,string),t2); t3:=Join(%,""); t4:=P(%);
if t4=999 then noter:=noter+1; else ter:=ter+1; fi;
od;
a0:=[op(a0),ter]; a1:=[op(a1),noter];
od:
a0; a1;
-
Table[ne = 0;
For[i = 0, i < 2^n, i++, lst = {};
w = IntegerString[i, 2, n];
While[! MemberQ[lst, w],
AppendTo[lst, w];
If[w == "", ne++; Break[]];
If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
w = StringDrop[w <> "1101", 3]]]];
ne, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)
A289675
Consider the Post tag system described in A284116 (but adapted to the alphabet {1,2}) ; sequence lists the words that terminate in the empty word.
Original entry on oeis.org
1, 2, 11, 12, 111, 112, 121, 122, 1111, 1121, 1211, 1221, 2111, 2121, 2211, 2221, 11111, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122, 12211, 12212, 12221, 12222, 111111, 111112, 111121, 111122, 112111, 112112, 112121, 112122, 121111, 121112, 121121, 121122, 122111, 122112, 122121, 122122
Offset: 1
Working over the more usual alphabet {0,1}, the following are the orbits of the first few words that terminate at the empty word:
[0, -1]
[1, 01, 0, -1]
[00, 0, -1]
[01, 0, -1]
[000, 00, 0, -1]
[001, 00, 0, -1]
[010, 00, 0, -1]
[011, 00, 0, -1]
[0000, 000, 00, 0, -1]
[0010, 000, 00, 0, -1]
[0100, 000, 00, 0, -1]
[0110, 000, 00, 0, -1]
[1000, 01101, 0100, 000, 00, 0, -1]
[1010, 01101, 0100, 000, 00, 0, -1]
[1100, 01101, 0100, 000, 00, 0, -1]
[1110, 01101, 0100, 000, 00, 0, -1]
[00000, 0000, 000, 00, 0, -1]
...
Writing the initial words in this list over {1,2} rather than {0,1} gives the sequence.
- John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.
-
A289675 = {};
Do[For[i = 0, i < 2^n, i++, lst = {};
w = IntegerString[i, 2, n];
While[! MemberQ[lst, w],
AppendTo[lst, w];
If[w == "", AppendTo[A289675, IntegerString[i, 2, n]]; Break[]];
If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
w = StringDrop[w <> "1101", 3]]]], {n, 6}];
Map[StringReplace[#, {"1" -> "2", "0" -> "1"}] &, A289675]
(* Robert Price, Sep 26 2019 *)
A289677
a(n) = A289671(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3) = A004523(n).
Original entry on oeis.org
0, 1, 1, 2, 2, 3, 4, 4, 5, 11, 12, 13, 22, 19, 20, 43, 46, 44, 85, 88, 89, 171, 185, 192, 366, 380, 396, 774, 793, 814, 1586, 1589, 1610, 3136, 3106, 3130, 6123, 6078, 6103, 12088, 12147, 12229, 24283, 24534, 24736, 49040, 49482, 49879, 99031, 99792, 100747, 200444, 201892, 203765, 405931, 408478, 411403
Offset: 1
-
from _future_ import division
def A289677(n):
c, k, r, n2, cs, ts = 0, 1+(n-1)//3, 2**((n-1) % 3), 2**(n-1), set(), set()
for i in range(2**k):
j, l = int(bin(i)[2:],8)*r, n2
traj = set([(l,j)])
while True:
if j >= l:
j = j*16+13
l *= 2
else:
j *= 4
l //= 2
if l == 0:
ts |= traj
break
j %= 2*l
if (l,j) in traj:
c += 1
cs |= traj
break
if (l,j) in cs:
c += 1
break
if (l,j) in ts:
break
traj.add((l,j))
return c # Chai Wah Wu, Aug 03 2017
A289672
Consider the Post tag system defined in A284116; a(n) = maximum, taken over all binary words w of length n which terminate in a cycle, of the number of words in the orbit of w.
Original entry on oeis.org
4, 3, 4, 7, 8, 7, 14, 15, 14, 15, 16, 15, 24, 25, 28, 29, 30, 35, 38, 39, 38, 39, 38
Offset: 1
For length n=2, there are two words which cycle, 10 and 11:
10 -> 101 -> 1101 -> 11101 -> 011101 -> 10100 -> 001101 -> 10100, which has entered a cycle.
-
# Uses procedures f1 and P from A289670.
# Count strings of length n which terminate and which cycle
# Print max length to reach empty word (mx)
mx:=[];
for n from 1 to 11 do
lprint("starting length ",n);
m:=0;
for n1 from 0 to 2^n-1 do
t1:=convert(2^n+n1,base,2); t2:=[seq(t1[i],i=1..n)];
map(x->convert(x,string),t2); t3:=Join(%,""); t4:=P(%);
if t4 <> 999 then if t4>m then m:=t4; fi; fi;
od;
mx:=[op(mx),m];
od:
mx;
A289676
a(n) = A289670(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3).
Original entry on oeis.org
2, 1, 1, 2, 2, 1, 4, 4, 3, 5, 4, 3, 10, 13, 12, 21, 18, 20, 43, 40, 39, 85, 71, 64, 146, 132, 116, 250, 231, 210, 462, 459, 438, 960, 990, 966, 2069, 2114, 2089, 4296, 4237, 4155, 8485, 8234, 8032, 16496, 16054, 15657, 32041, 31280, 30325, 61700, 60252, 58379, 118357, 115810, 112885
Offset: 1
-
from _future_ import division
def A289676(n):
c, k, r, n2, cs, ts = 0, 1+(n-1)//3, 2**((n-1) % 3), 2**(n-1), set(), set()
for i in range(2**k):
j, l = int(bin(i)[2:],8)*r, n2
traj = set([(l,j)])
while True:
if j >= l:
j = j*16+13
l *= 2
else:
j *= 4
l //= 2
if l == 0:
c += 1
ts |= traj
break
j %= 2*l
if (l,j) in traj:
cs |= traj
break
if (l,j) in cs:
break
if (l,j) in ts:
c += 1
break
traj.add((l,j))
return c # Chai Wah Wu, Aug 03 2017
A291072
Take n-th string over {1,2} in lexicographic order and apply the Watanabe tag system {00, 1011} described in A291067 (but adapted to the alphabet {1,2}) just once.
Original entry on oeis.org
-1, 22, 1, 1, 122, 122, 11, 11, 11, 11, 2122, 2122, 2122, 2122, 111, 211, 111, 211, 111, 211, 111, 211, 12122, 22122, 12122, 22122, 12122, 22122, 12122, 22122, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 112122, 122122, 212122, 222122
Offset: 1
-
# First define the mapping by defining the strings T1 and T2:
# Work over the alphabet {1,2}
# 11 / 2212 A284116 This is the "Post Tag System"
T1:="11"; T2:="2212";
# 11 / 2122 A291067 These three are from the Watanabe paper
T1:="11"; T2:="2122";
# 11 / 2221 A291068
T1:="11"; T2:="2221";
# 11 / 1222 A291069
T1:="11"; T2:="1222";
with(StringTools):
# the mapping:
f1:=proc(w) local L, ws, w2; global T1,T2;
ws:=convert(w, string);
if ws="-1" then return("-1"); fi;
if ws[1]="1" then w2:=Join([ws, T1], ""); else w2:=Join([ws, T2], ""); fi;
L:=length(w2); if L <= 3 then return("-1"); fi;
w2[4..L]; end;
# Construct list of words over {1,2} (A007931)
a:= proc(n) local m, r, d; m, r:= n, 0;
while m>0 do d:= irem(m, 2, 'm');
if d=0 then d:=2; m:= m-1 fi;
r:= d, r
od; parse(cat(r))/10
end:
WLIST := [seq(a(n), n=1..100)];
# apply the map once:
# this produces A289673, A291072, A291073, A291074
W2:=map(f1,WLIST);
A291073
Take n-th string over {1,2} in lexicographic order and apply the Watanabe tag system {00, 1110} described in A291068 (but adapted to the alphabet {1,2}) just once.
Original entry on oeis.org
-1, 21, 1, 1, 221, 221, 11, 11, 11, 11, 2221, 2221, 2221, 2221, 111, 211, 111, 211, 111, 211, 111, 211, 12221, 22221, 12221, 22221, 12221, 22221, 12221, 22221, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111
Offset: 1
A291074
Take n-th string over {1,2} in lexicographic order and apply the Watanabe tag system {00, 0111} described in A291069 (but adapted to the alphabet {1,2}) just once.
Original entry on oeis.org
-1, 22, 1, 1, 222, 222, 11, 11, 11, 11, 1222, 1222, 1222, 1222, 111, 211, 111, 211, 111, 211, 111, 211, 11222, 21222, 11222, 21222, 11222, 21222, 11222, 21222, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111
Offset: 1
A346040
a(n) is 1w' converted to decimal, where the binary word w' is the result of applying Post's tag system {00,1101} to the binary word w, where 1w is n converted to binary (the leftmost 1 acts as a delimiter).
Original entry on oeis.org
1, 1, 5, 2, 2, 13, 13, 4, 4, 4, 4, 29, 29, 29, 29, 8, 12, 8, 12, 8, 12, 8, 12, 45, 61, 45, 61, 45, 61, 45, 61, 16, 20, 24, 28, 16, 20, 24, 28, 16, 20, 24, 28, 16, 20, 24, 28, 77, 93, 109, 125, 77, 93, 109, 125, 77, 93, 109, 125, 77, 93, 109, 125, 32, 36, 40
Offset: 1
n = 22 (decimal) = 10110 (binary) = 1w ->
w = 0110 ->
011000 ->
w' = 000 ->
1w' = 1000 (binary) = 8 (decimal) = a(22)
n = 25 (decimal) = 11001 (binary) = 1w ->
w = 1001 ->
10011101 ->
w' = 11101 ->
1w' = 111101 (binary) = 61 (decimal) = a(25)
- Carlos Gómez-Ambrosi, Table of n, a(n) for n = 1..10000
- Liesbeth De Mol, Tracing unsolvability: a mathematical, historical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, University of Ghent, 2007. See also.
- Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197-215. See also. Post's tag system {00,1101} appears on page 204.
Cf.
A284116,
A284119,
A284121,
A289670,
A289671,
A289672,
A289674,
A289675,
A291792,
A291793,
A291794,
A291795,
A291796,
A291798,
A291799,
A291800,
A291801,
A291802,
A337537.
-
function m = A346040(n)
if n == 1
m = 1;
else
s = dec2bin(n);
if strcmp(s(2),'0')
t = [s '00'];
else
t = [s '1101'];
end
t(2) = [];
t(2) = [];
t(2) = [];
m = bin2dec(t);
end
end
-
a(n) = if(n==1,1, my(k=logint(n,2)); if(bittest(n,k-1), n=n<<4+13;k++, n<<=2;k--); bitand(n,bitneg(0,k)) + 1<Kevin Ryde, Jul 02 2021
-
def a(n):
if n == 1:
return 1
else:
s = n.digits(2)
s.reverse()
if s[1] == 0:
t = s + [0,0]
else:
t = s + [1,1,0,1]
del(t[1])
del(t[1])
del(t[1])
return sum(t[k]*2^(len(t)-1-k) for k in srange(0,len(t)))
Showing 1-10 of 10 results.
Comments