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).
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
Examples
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)
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.
Crossrefs
Programs
-
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<
-
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)))
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.
Comments