cp's OEIS Frontend

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).

%I A346040 #31 Aug 04 2021 03:18:25
%S A346040 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,
%T A346040 45,61,45,61,16,20,24,28,16,20,24,28,16,20,24,28,16,20,24,28,77,93,
%U A346040 109,125,77,93,109,125,77,93,109,125,77,93,109,125,32,36,40
%N 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).
%C A346040 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.
%C A346040 The empty word is included in the count.
%C A346040 It is an important open question to decide whether there is any word whose orbit grows without limit.
%C A346040 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.
%C A346040 With alphabet {0,1} replaced by {1,2}, the above correspondence is given by A007931, and a step of the tag system by A289673.
%C A346040 The present sequence allows for looking into Post's tag system "numerically", instead of "combinatorially".
%H A346040 Carlos Gómez-Ambrosi, <a href="/A346040/b346040.txt">Table of n, a(n) for n = 1..10000</a>
%H A346040 Liesbeth De Mol, <a href="http://hdl.handle.net/1854/LU-8515634">Tracing unsolvability: a mathematical, historical and philosophical analysis with a special focus on tag systems</a>, Ph.D. Thesis, University of Ghent, 2007. See <a href="https://www.clps.ugent.be/sites/default/files/publications/dissertation.pdf">also</a>.
%H A346040 Emil L. Post, <a href="https://www.jstor.org/stable/2371809">Formal reductions of the general combinatorial decision problem</a>, Amer. J. Math. 65 (1943), 197-215. See <a href="http://www.lib.ysu.am/articles_art/63062f3ed126193beb426becc0fbbe33.pdf">also</a>. Post's tag system {00,1101} appears on page 204.
%F A346040 a(n) = delete(append(n)), where:
%F A346040 append(1) = 1;
%F A346040 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));
%F A346040 delete(n) = n + 2^t * (1 - floor(n/2^t)), where t = max(floor(log_2(n))-3,0).
%F A346040 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.
%e A346040 n = 22 (decimal) = 10110 (binary) = 1w ->
%e A346040                 w = 0110 ->
%e A346040                     011000 ->
%e A346040                   w' = 000 ->
%e A346040                 1w' = 1000 (binary) = 8 (decimal) = a(22)
%e A346040 n = 25 (decimal) = 11001 (binary) = 1w ->
%e A346040                 w = 1001 ->
%e A346040                     10011101 ->
%e A346040                   w' = 11101 ->
%e A346040                 1w' = 111101 (binary) = 61 (decimal) = a(25)
%o A346040 (Sage)
%o A346040 def a(n):
%o A346040     if n == 1:
%o A346040         return 1
%o A346040     else:
%o A346040         s = n.digits(2)
%o A346040         s.reverse()
%o A346040         if s[1] == 0:
%o A346040             t = s + [0,0]
%o A346040         else:
%o A346040             t = s + [1,1,0,1]
%o A346040         del(t[1])
%o A346040         del(t[1])
%o A346040         del(t[1])
%o A346040         return sum(t[k]*2^(len(t)-1-k) for k in srange(0,len(t)))
%o A346040 (MATLAB)
%o A346040 function m = A346040(n)
%o A346040 if n == 1
%o A346040     m = 1;
%o A346040 else
%o A346040     s = dec2bin(n);
%o A346040     if strcmp(s(2),'0')
%o A346040         t = [s '00'];
%o A346040     else
%o A346040         t = [s '1101'];
%o A346040     end
%o A346040     t(2) = [];
%o A346040     t(2) = [];
%o A346040     t(2) = [];
%o A346040     m = bin2dec(t);
%o A346040 end
%o A346040 end
%o A346040 (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
%Y A346040 Cf. A289673 (alphabet 1,2).
%Y A346040 Cf. A284116, A284119, A284121, A289670, A289671, A289672, A289674, A289675, A291792, A291793, A291794, A291795, A291796, A291798, A291799, A291800, A291801, A291802, A337537.
%K A346040 nonn,base,easy
%O A346040 1,3
%A A346040 _Carlos Gómez-Ambrosi_, Jul 02 2021