A284121 -id:A284121 - cp's OEIS frontend

A291799 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = period of orbit of that word, or 0 if the orbit ends at the empty word.

0, 2, 0, 2, 6, 6, 0, 0, 0, 6, 6, 6, 6, 6, 0, 6, 0, 6, 6, 2, 6, 6, 6, 6, 6, 6, 4, 6, 0, 6, 0, 6, 6, 4, 0, 0, 6, 6, 6, 0, 0, 0, 6, 0, 6, 6, 4, 6, 0, 6, 6, 0, 6, 0, 6, 6, 0, 6, 6, 6, 10, 0, 0, 0, 6, 6, 4, 6, 6, 6, 0, 4, 0, 0, 0, 6, 6, 6, 0, 6, 4, 6, 6, 2, 6, 6, 6

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.
This is an analog of A291793 (or A284121) for the words in A291797.

Lars Blomberg, Table of n, a(n) for n = 1..8190 (For terms in A291797 up to length 36.)
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102. See Table 3.

Cf. A284116, A284121, A291793, A291797.

a(31)-a(87) from Lars Blomberg, Sep 08 2017

A302202 a(n) = number of distinct words arising in Post's tag system {00, 1101} applied to the word (100)^n , or a(n) = -1 if this word has an unbounded trajectory.

Original entry on oeis.org

6, 21, 16, 31, 412, 57, 2156, 859, 382, 2811, 372, 2609, 704, 37913, 618, 155, 1008, 2407, 1210, 629, 5286, 1779, 1468, 4346275, 4130, 3247, 7024, 3891, 14638, 7025, 4570, 4329, 147694, 1863, 11126, 81147, 20210, 3853, 116020, 7641, 6494

Offset: 1

Lars Blomberg and N. J. A. Sloane, Apr 19 2018

nonn

a(n) = A284119(n) + A284121(n) (or -1 if the trajectory is unbounded).
a(n) is a lower bound on A284116(3n) (assuming that there is no starting string with an unbounded trajectory).
On October 30 2020, a student in my CS 360 class, Zhiping Cai, found that for n = 70051, 96938660265781 (96.9 trillion) steps are needed.  See https://github.com/zcai1/posts-problem .  I am not sure this has been independently verified. - Jeffrey Shallit, Sep 13 2021

Lars Blomberg, Table of n, a(n) for n = 1..6075

Cf. A284119, A284121; A284116.

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

A291799 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = period of orbit of that word, or 0 if the orbit ends at the empty word.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A302202 a(n) = number of distinct words arising in Post's tag system {00, 1101} applied to the word (100)^n , or a(n) = -1 if this word has an unbounded trajectory.

Views

Author

Keywords

Comments

Links

Crossrefs

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