login
a(0)=0, a(1)=1, after which a(2n) = A055938(a(n)), a(2n+1) = A005187(1+a(n)).
16

%I #20 Apr 19 2015 20:49:51

%S 0,1,2,3,5,4,6,7,12,10,9,8,13,11,14,15,27,23,21,19,20,18,17,16,28,25,

%T 24,22,29,26,30,31,58,53,48,46,44,41,40,38,43,39,37,35,36,34,33,32,59,

%U 54,52,49,51,47,45,42,60,56,55,50,61,57,62,63,121,113,108

%N a(0)=0, a(1)=1, after which a(2n) = A055938(a(n)), a(2n+1) = A005187(1+a(n)).

%C This permutation is obtained by "entangling" even and odd numbers with complementary pair A055938 & A005187, meaning that it can be viewed as a binary tree. Each child to the left is obtained by applying A055938(n) to the parent node containing n, and each child to the right is obtained as A005187(n+1):

%C 0

%C |

%C ...................1...................

%C 2 3

%C 5......../ \........4 6......../ \........7

%C / \ / \ / \ / \

%C / \ / \ / \ / \

%C / \ / \ / \ / \

%C 12 10 9 8 13 11 14 15

%C 27 23 21 19 20 18 17 16 28 25 24 22 29 26 30 31

%C etc.

%C For n >= 1, A256991(n) gives the contents of the immediate parent node of the node containing n, while A070939(n) gives the total distance to zero at the root from the node containing n, with A256478(n) telling how many of the terms encountered on that journey are terms of A005187 (including the penultimate 1 but not the final 0 in the count), while A256479(n) tells how many of them are terms of A055938.

%C Permutation A233276 gives the mirror image of the same tree.

%H Antti Karttunen, <a href="/A233278/b233278.txt">Table of n, a(n) for n = 0..8191</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(0)=0, a(1)=1, and thereafter, a(2n) = A055938(a(n)), a(2n+1) = A005187(1+a(n)).

%F As a composition of related permutations:

%F a(n) = A233276(A054429(n)).

%o (Scheme, with memoizing definec-macro from _Antti Karttunen_'s IntSeq-library)

%o (definec (A233278 n) (cond ((< n 2) n) ((even? n) (A055938 (A233278 (/ n 2)))) (else (A005187 (+ 1 (A233278 (/ (- n 1) 2)))))))

%Y Inverse permutation: A233277.

%Y Cf. A005187, A054429, A055938, A256991, A256478, A256479.

%Y Cf. also A070939 (the binary width of both n and a(n)).

%Y Related arrays: A255555, A255557.

%Y Similarly constructed permutation pairs: A005940/A156552, A135141/A227413, A232751/A232752, A233275/A233276, A233279/A233280, A003188/A006068.

%K nonn,tabf

%O 0,3

%A _Antti Karttunen_, Dec 18 2013

%E Name changed and the illustration of binary tree added by _Antti Karttunen_, Apr 19 2015