A291794 -id:A291794 - cp's OEIS frontend

A291802 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) = position of the longest word in the orbit, or -1 if the orbit is unbounded.

0, 3, 0, 0, 16, 14, 0, 0, 0, 13, 15, 11, 23, 9, 0, 18, 0, 22, 20, 0, 12, 8, 24, 10, 20, 18, 2, 6, 106, 16, 0, 23, 27, 0, 0, 0, 27, 5, 25, 0, 0, 105, 3, 103, 37, 15, 1, 1, 107, 17, 19, 101, 9, 99, 2, 35, 7, 7, 31, 13, 71, 97, 0, 0, 0, 0, 0, 22, 0, 34, 0, 0, 0

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 A291796 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, A291794, A291795, A291796, A291797.

a(31)-a(73) from Lars Blomberg, Sep 08 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.

cp's OEIS Frontend

A291802 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) = position of the longest word in the orbit, or -1 if the orbit is unbounded.

Views

Author

Keywords

Comments

Links

Crossrefs

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