A284116 -id:A284116 - cp's OEIS frontend

A289677 a(n) = A289671(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3) = A004523(n).

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

N. J. A. Sloane, Aug 01 2017

nonn

This is the number of distinct binary words w of length n that eventually cycle 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, A289676.

Cf. also A290436-A290441.

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

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

A290436 a(n) = A289676(3*n+1).

Original entry on oeis.org

2, 2, 4, 5, 10, 21, 43, 85, 146, 250, 462, 960, 2069, 4296, 8485, 16496, 32041, 61700, 118357

Offset: 0

N. J. A. Sloane, Aug 02 2017

No formulas or recurrences are known for the important sequences A289670 and A289671. The essence of these two sequences is captured in the six entries A290436-A290441. Any numerical properties of these would be most welcome.

Cf. A284116, A284119, A284121, A289670-A289677, A290436-A290441.

A290441 a(n) = A289677(3*n).

Original entry on oeis.org

1, 3, 5, 13, 20, 44, 89, 192, 396, 814, 1610, 3130, 6103, 12229, 24736, 49879, 100747, 203765, 411403

Offset: 1

N. J. A. Sloane, Aug 02 2017

No formulas or recurrences are known for the important sequences A289670 and A289671. The essence of these two sequences is captured in the six entries A290436-A290441. Any numerical properties of these would be most welcome.

Cf. A284116, A284119, A284121, A289670-A289677, A290436-A290441.

A291780 Consider the Watanabe tag system defined in A291067; a(n) = number of binary words of length n which terminate at the empty word.

Original entry on oeis.org

2, 4, 4, 4, 16, 32, 64, 128, 128, 320, 1152, 1792, 3584, 8704, 16384, 28672, 65536, 118784, 221184, 483328, 851968, 1720320, 3866624, 6815744, 14483456, 31719424, 55574528, 113770496, 246939648, 438304768, 837812224, 1790967808, 3309305856

Offset: 1

Don Reble and N. J. A. Sloane, Sep 01 2017

nonn

Don Reble, Table of n, a(n) for n = 1..60

Cf. A284116, A291067, A291781.

A291781 Consider the Watanabe tag system defined in A291067; a(n) = number of binary words of length n which terminate in a cycle.

Original entry on oeis.org

0, 0, 4, 12, 16, 32, 64, 128, 384, 704, 896, 2304, 4608, 7680, 16384, 36864, 65536, 143360, 303104, 565248, 1245184, 2473984, 4521984, 9961472, 19070976, 35389440, 78643200, 154664960, 289931264, 635437056, 1309671424, 2503999488, 5280628736

Offset: 1

Don Reble and N. J. A. Sloane, Sep 01 2017

nonn

Don Reble, Table of n, a(n) for n = 1..60

Cf. A284116, A291067, A291780.

A292090 Preperiod (or threshold) of orbit of Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n.

Original entry on oeis.org

171, 166, 11, 154, 105, 14, 57, 68, 173, 1098, 8265, 720, 1715, 130, 1979, 2024, 833, 162, 591, 6124, 59673, 748, 11631, 3200, 1453, 13740, 2947, 2202, 15101, 1268, 608049, 30758, 29903, 1076, 17547, 2888, 72231, 10154, 2321, 68916, 10965, 2276, 151785, 4678

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.
Lars Blomberg, Graph of the terms
Lars Blomberg, Graph of preperiod of a(2263)
Lars Blomberg, Graph of preperiod of a(2540)
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, A284119, 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.

From Lars Blomberg, Apr 20 2018: (Start)
Using Excel, trendlines were created for the preperiod of the Post Tag and Watanabe Tag systems as follows:
A284119: y = 8.6528*x^2.0831, R^2 = 0.478.
A292090: y = 8.5595*x^2.1033, R^2 = 0.472.
Although the error value is rather large, the curves are quite similar. (End)

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

A291068 Largest number of distinct words arising in Watanabe's tag system {00, 1110} applied to a binary word w, over all starting words w of length n.

Original entry on oeis.org

6, 5, 4, 15, 14, 13, 26, 25, 24, 39, 38, 37, 54, 53, 52, 69, 68, 67, 86, 85, 84, 103, 102, 101, 120, 119, 118, 139, 138, 137, 158, 157, 156, 177, 176, 175, 196, 195, 194, 215, 214, 213, 236, 235, 234, 257, 256, 255, 278, 277

Offset: 1

N. J. A. Sloane, Aug 18 2017

Watanabe's tag system {00, 1110} 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 1110 to w and deleting the first three letters.
The empty word is included in the count.
Comment from Don Reble, Aug 25 2017: (Start)
The following comment applies to both the 3-shift tag systems {00,1110} (A291068) and {00,0111} (A291069). Number the bits in a binary word w starting at the left with bit 0. For the trajectory of w under the tag system, only bits numbered 0,3,6,9,... are important, the others (the unimportant bits) having no effect on the outcome.
An important 1 bit produces 0111 or 1110, and exactly one of those new 1 bits is important. The number of important 1's never changes. So the number of initial words of length n that terminate (the analog of A289670) is just 2^(number-of-unimportant-bits) = 2^(floor(2*n/3)) = A291778.
The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779.
Furthermore, the number of important zeros is eventually bounded.
Proof. If a word has A important zeros and B important ones, then after A+B steps, there will be at most 2A+4B bits, and at most (2A+4B+2)/3 important bits. B of them are important ones, so at most (2A+B+2)/3 are important zeros.
If A >= B+3, then (2A+B+2)/3 <= (2A+A-1)/3 < A. If A < B+3, then (2A+B+2)/3 < (3B+8)/3 = B+2. The first kind must shrink; the second kind can't grow past A+B+2. QED
Ultimately, a word with B important ones has at most A+B+2 important bits, so can't diverge. So the word "finite" in the definition was unnecessary and has been omitted. (End)

			Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".

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]
N. J. A. Sloane, Maple programs that compute first 7 terms for each of A284116, A291067, A291068, A291069

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

Cf. A291073.

Maple
```
See link.
```

a(8)-(50) from Lars Blomberg, Sep 16 2017

A291069 Largest number of distinct words arising in Watanabe's tag system {00, 0111} applied to a binary word w, over all starting words w of length n.

Original entry on oeis.org

5, 4, 4, 14, 13, 12, 25, 24, 23, 38, 37, 36, 53, 52, 51, 68, 67, 66, 85, 84, 83, 102, 101, 100, 119, 118, 117, 138, 137, 136, 157, 156, 155, 176, 175, 174, 195, 194, 193, 214, 213, 212, 235, 234, 233, 256, 255, 254, 277, 276

Offset: 1

N. J. A. Sloane, Aug 18 2017

Watanabe's tag system {00, 0111} 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 0111 to w and deleting the first three letters.
The empty word is included in the count.
Comment from Don Reble, Aug 25 2017: (Start)
The following comment applies to both the 3-shift tag systems {00,1110} (A291068) and {00,0111} (A291069). Number the bits in a binary word w starting at the left with bit 0. For the trajectory of w under the tag system, only bits numbered 0,3,6,9,... are important, the others (the unimportant bits) having no effect on the outcome.
An important 1 bit produces 0111 or 1110, and exactly one of those new 1 bits is important. The number of important 1's never changes. So the number of initial words of length n that terminate (the analog of A289670) is just 2^(number-of-unimportant-bits) = 2^(floor(2*n/3)) = A291778.
The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779.
Furthermore, the number of important zeros is eventually bounded.
Proof. If a word has A important zeros and B important ones, then after A+B steps, there will be at most 2A+4B bits, and at most (2A+4B+2)/3 important bits. B of them are important ones, so at most (2A+B+2)/3 are important zeros.
If A >= B+3, then (2A+B+2)/3 <= (2A+A-1)/3 < A. If A < B+3, then (2A+B+2)/3 < (3B+8)/3 = B+2. The first kind must shrink; the second kind can't grow past A+B+2. QED
Ultimately, a word with B important ones has at most A+B+2 important bits, so can't diverge. So the word "finite" in the definition was unnecessary and has been omitted. (End)

			Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".

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]
N. J. A. Sloane, Maple programs that compute first 7 terms for each of A284116, A291067, A291068, A291069

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

Cf. A291074.

Maple
```
See link.
```

a(8)-(50) from Lars Blomberg, Sep 16 2017

A292089 Numbers n such that Watanabe's 3-shift tag system {00/1011} started at the word (100)^n eventually dies (i.e., reaches the empty string).

Original entry on oeis.org

5, 9, 11, 16, 20, 22, 23, 25, 37, 38, 43, 47, 61, 64, 66, 68, 71, 82, 87, 95, 100, 115, 119, 120, 123, 126, 137, 141, 142, 143, 144, 147, 149, 153, 156, 158, 164, 165, 171, 178, 179, 183, 188, 195, 196, 201, 202, 203, 205, 206, 212, 214, 216, 218, 223, 232

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.
These are the numbers such that A292091(n)=0.
Oct 11, 2017: Lars Blomberg has found that 872 is a member of this sequence. The word (100)^872 reaches the empty string after 72392976118788 iterations. The attached graph shows the lengths of the successive words in the trajectory. - N. J. A. Sloane, Oct 13 2017

			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..1440
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
Lars Blomberg, Lengths of words in the trajectory of (100)^872
N. J. A. Sloane, Maple code for A291792, A284119, A291793, A284121, A291794, A291795, A291796, A292089, A292090, A292091, A292092, A292093, A292094.
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, A291793 (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(8)-(18) from Lars Blomberg, Sep 14 2017

a(19) and beyond from Lars Blomberg, Apr 20 2018

A292092 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = length of first word we see that is in the cycle, if the orbit cycles, or 0 if the orbit reaches the empty string, or -1 if the orbit is unbounded.

Original entry on oeis.org

56, 56, 16, 56, 0, 28, 38, 42, 0, 34, 0, 34, 34, 82, 20, 0, 70, 100, 20, 0, 20, 0, 0, 56, 0, 46, 64, 64, 64, 92, 74, 34, 118, 66, 88, 52, 0, 0, 34, 268, 42, 34, 0, 46, 30, 92, 0, 16, 34, 76, 76, 34, 34, 38, 110, 20, 64, 92, 46, 56, 0, 46, 76, 0, 74, 0, 88, 0

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.
Following Asveld we set a(n)=0 if the orbit ends at the empty word.

			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)-(68) from Lars Blomberg, Sep 14 2017

cp's OEIS Frontend

A289677 a(n) = A289671(n)/2^f(n), where f(n) = 2*floor((n-1)/3) + ((n+2) mod 3) = A004523(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

Extensions

A290436 a(n) = A289676(3*n+1).

Views

Author

Keywords

Comments

Crossrefs

A290441 a(n) = A289677(3*n).

Views

Author

Keywords

Comments

Crossrefs

A291780 Consider the Watanabe tag system defined in A291067; a(n) = number of binary words of length n which terminate at the empty word.

Views

Author

Keywords

Links

Crossrefs

A291781 Consider the Watanabe tag system defined in A291067; a(n) = number of binary words of length n which terminate in a cycle.

Views

Author

Keywords

Links

Crossrefs

A292090 Preperiod (or threshold) of orbit of Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A291068 Largest number of distinct words arising in Watanabe's tag system {00, 1110} applied to a binary word w, over all starting words w of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A291069 Largest number of distinct words arising in Watanabe's tag system {00, 0111} applied to a binary word w, over all starting words w of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A292089 Numbers n such that Watanabe's 3-shift tag system {00/1011} started at the word (100)^n eventually dies (i.e., reaches the empty string).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A292092 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = length of first word we see that is in the cycle, if the orbit cycles, or 0 if the orbit reaches the empty string, or -1 if the orbit is unbounded.

Views

Author

Keywords

Comments