A284116 -id:A284116 - cp's OEIS frontend

A292093 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = length of the longest word in the orbit, or -1 if the orbit is unbounded.

59, 59, 17, 59, 31, 85, 41, 85, 49, 159, 328, 93, 93, 83, 215, 193, 121, 101, 109, 357, 781, 150, 273, 261, 171, 341, 182, 229, 551, 187, 2627, 593, 503, 187, 400, 261, 1369, 371, 226, 1045, 374, 280, 849, 375, 437, 255, 667, 365, 291, 2972, 463, 905, 631, 405

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

Watanabe's tag system {00/1011} 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 1011 to w and deleting the first three letters.

The empty word is included in the count.

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..6080
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
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. A284116, A291067, A291780, A291781.

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.

a(25)-(54) from Lars Blomberg, Sep 14 2017

A292094 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = position of the longest word in the orbit, or -1 if the orbit is unbounded.

Original entry on oeis.org

138, 133, 10, 121, 24, 215, 36, 333, 38, 407, 4429, 343, 1338, 85, 720, 1023, 420, 105, 118, 2259, 33530, 328, 6250, 1515, 370, 9729, 2059, 825, 6282, 309, 310620, 20089, 10014, 187, 12069, 1101, 21756, 2359, 1253, 53811, 7277, 598, 103772, 1275, 5584, 269

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

Watanabe's tag system {00/1011} 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 1011 to w and deleting the first three letters.

The empty word is included in the count.

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..6080
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
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. A284116, A291067, A291780, A291781.

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.

a(25)-(46) from Lars Blomberg, Sep 14 2017

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

N. J. A. Sloane, Aug 01 2017

nonn

This is the number of distinct binary words w of length n that terminate under the Post tag system (see A284116, A289670) reduced to take into account the observation made by Don Reble that (if the bits of w are labeled from the left starting at bit 0) bits 1,2,4,5,7,8,... (not a multiple of 3) are "junk DNA" and have no effect on the outcome.

Cf. A284116, A284119, A284121, A289670, A289671, A289672, A289673, A289674, A289675, A289677.

Cf. also A290436-A290441.

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

Corrected by Don Reble, Aug 01 2017 (there were errors in A289670)

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

N. J. A. Sloane, Aug 18 2017

sign

Cf. A007931, A284116, A291067, A291068, A291069.

Cf. also A289673, A291073, A291074.

# 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);

A290741 Orbit of word "2" under the 3-shift tag system over the alphabet {1,2} defined in the Comments.

Original entry on oeis.org

2, 21222, 221221222, 2212221221222, 22212212221221222, 122122212212221221222, 1222122122212212222112, 21221222122122221122112, 212221221222211221121221222, 2212212222112211212212221221222, 22122221122112122122212212221221222, 222211221121221222122122212212221221222

Offset: 1

N. J. A. Sloane, Aug 11 2017

nonn

This tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 2112 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 1221222 to w and deleting the first three letters.

This is a 3-shift version of a 5-shift tag system studied in [De Mol, p. 307] (cf. A293945).

Michael S. Branicky, Table of n, a(n) for n = 1..328
Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent. See page 307.

Cf. A284116, A290742, A293945.

with(StringTools);
f1:=proc(w) local L, t2, t1, ws, w2;
t1:="2112"; t2:="1221222"; ws:=convert(w, string);
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;
# and apply f1 repeatedly to "2"

from itertools import islice
def agen(w="2"):
    while True:
        yield int(w)
        w += ("2112" if w[0] == "1" else "1221222")
        w = w[3:]
print(list(islice(agen(), 12))) # Michael S. Branicky, Mar 15 2022

Definition corrected by N. J. A. Sloane, Oct 23 2017 (this is not De Mol's 5-shift tag system, which is described in A293945).

A290742 Orbit of word "1" under the 3-shift tag system over the alphabet {1,2} defined in the Comments.

Original entry on oeis.org

1, 12, 112, 2112, 21221222, 212221221222, 2212212221221222, 22122212212221221222, 222122122212212221221222, 1221222122122212212221221222, 12221221222122122212212222112, 212212221221222122122221122112, 2122212212221221222211221121221222

Offset: 1

N. J. A. Sloane, Aug 11 2017

nonn

This tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 2112 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 1221222 to w and deleting the first three letters.

This is a 3-shift version of a 5-shift tag system studied in [De Mol, p. 307].

Michael S. Branicky, Table of n, a(n) for n = 1..322
Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent. See page 307.

Cf. A284116, A290741.

with(StringTools);
f1:=proc(w) local L, t2, t1, ws, w2;
t1:="2112"; t2:="1221222"; ws:=convert(w, string);
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;
# and apply f1 repeatedly to "1"

from itertools import islice
def agen(w="1"):
    while True:
        yield int(w)
        w += ("2112" if w[0] == "1" else "1221222")
        w = w[3:]
print(list(islice(agen(), 13))) # Michael S. Branicky, Mar 15 2022

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

N. J. A. Sloane, Aug 18 2017

sign

Cf. A007931, A284116, A291067, A291068, A291069.

Cf. also A289673, A291072, A291074.

Maple
```
See A291072.
```

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

N. J. A. Sloane, Aug 18 2017

sign

Cf. A007931, A284116, A291067, A291068, A291069.

Cf. also A289673, A291072, A291073.

Maple
```
See A291072.
```

A152111 An increasing basis of order 3. See Comments for full definition.

Original entry on oeis.org

0, 1, 2, 4, 8, 9, 16, 18, 32, 36, 64, 65, 72, 73, 128, 130, 144, 146, 256, 260, 288, 292, 512, 513, 520, 521, 576, 577, 584, 585, 1024, 1026, 1040, 1042, 1152, 1154, 1168, 1170, 2048, 2052, 2080, 2084, 2304, 2308, 2336, 2340, 4096, 4097, 4104, 4105, 4160

Offset: 1

David S. Newman, Mar 22 2009

Using the terminology of A008932, call a set A a basis of order h if every number can be written as the sum of h (not necessarily distinct) elements of A. Call a basis an increasing basis of order h if its elements are arranged in increasing order, a0 < a1 < a2 < ...
This sequence is constructed as follows: Take the union of the following three sets: (1) the set of all nonnegative numbers which can be written in base two as sums of powers, k, of 2, where k is congruent to 0 mod 3; (2) the set of all nonnegative numbers which can be written in base two as sums of powers, k, of 2, where k is congruent to 1 mod 3; (3) the set of all nonnegative numbers which can be written in base two as sums of powers, k, of 2, where k is congruent to 2 mod 3.
Numbers of the form A033045(k), or 2*A033045(k), or 4*A033045(k). - R. J. Mathar, Sep 21 2009
There are 3*2^i - 1 terms up to 8^i. - David A. Corneth, Aug 02 2017

David A. Corneth, Table of n, a(n) for n = 1..12287 (terms up to 8^12).
Index entries for sequences that are an additive basis, order 3.

Cf. A008932, A033045, A152112, A284116.

ismod3 := proc(n,m) b := convert(n,base,2) ; for i from 1+((m+1) mod 3) to nops(b) by 3 do if op(i,b) <> 0 then RETURN(false) ; fi; od: for i from 1 + ((m+2) mod 3) to nops(b) by 3 do if op(i,b) <> 0 then RETURN(false) ; fi; od: true ; end: for n from 0 to 20700 do if ismod3(n,0) or ismod3(n,1) or ismod3(n,2) then printf("%d,",n); fi; od: # R. J. Mathar, Sep 21 2009

upto(n) = {my(i = 1, r, res = List()); while(1, b = binary(i); r = sum(i=1, #b, 8^i*b[#b+1-i])>>3; if(r > n, break); listput(res, r); i+=2); q = #res; for(i=1,  q, e = res[i] << 1; while(e <= n, listput(res, e); e=e<<1)); listput(res, 0); listsort(res); res} \\ David A. Corneth, Aug 02 2017

More terms from R. J. Mathar, Sep 21 2009

A293945 Orbit of word "2" under De Mol's 5-shift tag system over the alphabet {1,2} defined in the Comments.

Original entry on oeis.org

2, 222, 21222, 1221222, 222112, 21221222, 2221221222, 212221221222, 12212221221222, 2212212222112, 122221121221222, 11212212222112, 2122221122112, 211221121221222, 11212212221221222, 2122212212222112, 122122221121221222, 22211212212222112, 2122122221121221222, 222211212212221221222

Offset: 1

N. J. A. Sloane, Oct 23 2017

nonn

This tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 2112 to w and deleting the first five letters, or if w begins with 2, w' is obtained by appending 1221222 to w and deleting the first five letters.

It can be shown that under this tag system every word different from "1" has an infinite orbit [De Mol, p. 307].

Michael S. Branicky, Table of n, a(n) for n = 1..1025
Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent. See page 307.

Cf. A284116, A290741, A290742.

with(StringTools);
f1:=proc(w) local L, t2, t1, ws, w2;
t1:="2112"; t2:="1221222"; ws:=convert(w, string);
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[6..L]; end;
# and apply f1 repeatedly to "2"

from itertools import islice
def agen(w="2"):
    while True:
        yield int(w)
        w += ("2112" if w[0] == "1" else "1221222")
        w = w[5:]
print(list(islice(agen(), 20))) # Michael S. Branicky, Jan 06 2025

cp's OEIS Frontend

A292093 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = length of the longest word in the orbit, or -1 if the orbit is unbounded.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A292094 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = position of the longest word in the orbit, or -1 if the orbit is unbounded.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A289676 a(n) = A289670(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3).

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

Extensions

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.

Views

Author

Keywords

Crossrefs

Programs

Maple

A290741 Orbit of word "2" under the 3-shift tag system over the alphabet {1,2} defined in the Comments.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Python

Extensions

A290742 Orbit of word "1" under the 3-shift tag system over the alphabet {1,2} defined in the Comments.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Python

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.

Views

Author

Keywords

Crossrefs

Programs

Maple

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.

Views

Author

Keywords

Crossrefs

Programs

Maple

A152111 An increasing basis of order 3. See Comments for full definition.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI