A284119 -id:A284119 - cp's OEIS frontend

A336327 Period of orbit of Post's tag system ({0,1},{(0,0),(1,01101)},3,100^n).

0, 4, 0, 4450, 0, 4450, 0, 0, 0, 4450, 0, 0, 6, 0, 0, 4450, 0, 0, 0, 0, 910, 4450, 0, 4450, 910, 4450, 0, 4450, 0, 4450, 910, 0, 0, 4450, 0, 4450, 910, 4, 0, 4, 0, 0, 910, 0, 6, 0, 910, 0, 0, 4450, 0, 4450, 910, 4450, 0, 292, 0, 4450, 0, 0, 910, 4450, 6, 4450

Offset: 1

A.H.M. Smeets, Jul 17 2020

nonn

In general a tag as defined by Emil Leon Post, is given by a 4-tuple (Sigma,AF,n,w0), where Sigma is some (nonempty) set of symbols called the alphabet, AF is the associated function (sometimes also called set of production rules) AF: Sigma -> Sigma*, n is the deletion number and w0 the initial string.
From the starting sequence we obtain a new string in each step by adjoining the string associated to the prefix symbol of the string, where after the prefix n symbols are removed from the string.
The decision problem is: will the tag end up in an empty string, a(n) = 0 or not, a(n) <> 0?
a(n) is an even number. Proof: for each cycle the number of associations (productions) 0 -> 0 must equal the number of associations (productions) 1 -> 01101 applied within a cycle.
For n=85 the tag is hard to solve by a brute force method, similar to the tag for n=110 with associated function {(0,00),(1,1101)} as reported in A284119.
Also period of orbit of Post's tag system ({0,1},{(0,0),(0,11010)},3,100^(n-1)).

Emil L. Post, Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, Vol. 65, No. 2 (Apr., 1943), pp. 197-215.
Eric Weisstein's World of Mathematics, Tag System

Cf. A284119, A291793, A292091, A336287.

def step(w):
    i = 0
    while w[0] != alfabet[i]:
        i = i+1
    w = w+suffix[i]
    return w[n:len(w)]
alfabet, suffix, n, ws, w0, m = "01", ["0", "01101"], 3, "100", "", 0
while m >= 0:
    w0, m = w0+ws, m+1
    w, ww, i, a = w0, w0, 0, 0
    while w != "" and a == 0:
        w, i = step(w), i+1
        if i%100000 == 0:
            ww = w
        else:
            if w == ww or w == "":
                if w != "":
                    a = i%100000
                print(m, a)

Observed: if n is even then a(n) in {0, 4, 292, 4450}, if n is odd then a(n) in {0, 6, 910}.

A291798 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) = preperiod (or threshold) of orbit of that word.

Original entry on oeis.org

3, 4, 6, 2, 17, 15, 9, 11, 13, 14, 16, 12, 24, 10, 12, 19, 14, 23, 21, 4, 13, 9, 25, 11, 29, 27, 3, 7, 420, 25, 15, 24, 28, 6, 17, 19, 28, 4, 26, 21, 23, 419, 6, 417, 46, 24, 8, 5, 421, 26, 28, 415, 12, 413, 10, 44, 27, 10, 40, 22, 84, 411, 18, 20, 29, 9, 11

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 A284119 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, A284119, A291797.

a(31)-a(67) 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.

A337537 Period of orbit of Post's tag system ({0,1},{(0,0101100),(1,11000111100000)},10,(1+0^9)^n).

Original entry on oeis.org

7, 7, 7, 7, 7, 308, 7, 308, 308, 112, 308, 308, 140, 308, 140, 3429251, 140, 308, 140, 802613, 3429251, 140, 140, 3429251, 802613, 3429251, 3429251, 3429251, 3429251, 3429251, 140, 140, 802613, 3429251, 802613, 802613, 140, 802613, 140, 802613, 802613, 3429251

Offset: 1

A.H.M. Smeets, Aug 31 2020

nonn

In general a tag as defined by Emil Leon Post, is given by a 4-tuple (Sigma,AF,n,w0), where Sigma is some (nonempty) set of symbols called the alphabet, AF is the associated function (sometimes also called set of production rules) AF: Sigma -> Sigma*, n is the deletion number and w0 the initial string.
From the starting sequence we obtain a new string in each step by adjoining the string associated to the prefix symbol of the string, where after the prefix n symbols are removed from the string.
The decision problem is: will the tag end up in an empty string, a(n) = 0 or not, a(n) <> 0?
This tag system was proposed by Liesbeth De Mol (p. 329).
a(n) == 0 (mod 7). Proof: for each cycle four times the number of associations (productions) 0 -> 0101100 must equal three times the number of associations (productions) 1 -> 11000111100000 applied within a cycle.

Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent (2007). See page 329.
Emil L. Post, Formal reductions of the general combinatorial decision problem., American Journal of Mathematics, Vol. 65, No. 2 (Apr., 1943), pp. 197-215.
Eric Weisstein's World of Mathematics, Tag System

Cf. A284119, A291793, A292091, A336287, A336327.

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

A336327 Period of orbit of Post's tag system ({0,1},{(0,0),(1,01101)},3,100^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A291798 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) = preperiod (or threshold) of orbit of that 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

A337537 Period of orbit of Post's tag system ({0,1},{(0,0101100),(1,11000111100000)},10,(1+0^9)^n).

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