A289670 -id:A289670 - cp's OEIS frontend

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.

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

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

Carlos Gómez-Ambrosi, Jul 02 2021

Post's tag system 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 whether there is any word whose orbit grows without limit.
Note that there is a one-to-one correspondence between positive integers and binary words (including the empty word), given by n (decimal) = 1w (binary) -> w.
With alphabet {0,1} replaced by {1,2}, the above correspondence is given by A007931, and a step of the tag system by A289673.
The present sequence allows for looking into Post's tag system "numerically", instead of "combinatorially".

			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. A289673 (alphabet 1,2).

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

a(n) = delete(append(n)), where:
append(1) = 1;
append(n) = 2^(2 + 2 * floor((n - 2^k)/2^(k-1))) * n + 13 * floor((n - 2^k)/2^(k-1)) if n > 1, where k = floor(log_2(n));
delete(n) = n + 2^t * (1 - floor(n/2^t)), where t = max(floor(log_2(n))-3,0).
In the expression for append(n), floor((n - 2^k)/2^(k-1)) is the second-highest bit in the binary expansion of n, which is A079944, with offset 2.

A290437 a(n) = A289676(3*n+2).

Original entry on oeis.org

1, 2, 4, 4, 13, 18, 40, 71, 132, 231, 459, 990, 2114, 4237, 8234, 16054, 31280, 60252, 115810

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.

A290438 a(n) = A289676(3*n).

Original entry on oeis.org

1, 1, 3, 3, 12, 20, 39, 64, 116, 210, 438, 966, 2089, 4155, 8032, 15657, 30325, 58379, 112885

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.

A290439 a(n) = A289677(3*n+1).

Original entry on oeis.org

0, 2, 4, 11, 22, 43, 85, 171, 366, 774, 1586, 3136, 6123, 12088, 24283, 49040, 99031, 200444, 405931

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.

A290440 a(n) = A289677(3*n+2).

Original entry on oeis.org

1, 2, 4, 12, 19, 46, 88, 185, 380, 793, 1589, 3106, 6078, 12147, 24534, 49482, 99792, 201892, 408478

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.

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

PARI

Sage

Formula

A290437 a(n) = A289676(3*n+2).

Views

Author

Keywords

Comments

Crossrefs

A290438 a(n) = A289676(3*n).

Views

Author

Keywords

Comments

Crossrefs

A290439 a(n) = A289677(3*n+1).

Views

Author

Keywords

Comments

Crossrefs

A290440 a(n) = A289677(3*n+2).

Views

Author

Keywords

Comments

Crossrefs