OFFSET
1,3
COMMENTS
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".
LINKS
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.
FORMULA
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.
EXAMPLE
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)
PROG
(Sage)
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)))
(MATLAB)
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
(PARI) 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<<k); \\ Kevin Ryde, Jul 02 2021
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Carlos Gómez-Ambrosi, Jul 02 2021
STATUS
approved