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

0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 11, 13, 8, 9, 10, 12, 31, 30, 26, 29, 22, 24, 25, 28, 16, 17, 18, 20, 19, 21, 23, 27, 63, 62, 57, 61, 50, 55, 56, 60, 42, 45, 47, 51, 49, 52, 54, 59, 32, 33, 34, 36, 35, 37, 39, 43, 38, 40, 41, 44, 46, 48, 53, 58, 127, 126, 120

Offset: 0

Author

Antti Karttunen, Dec 18 2013

Keywords

• nonn
• tabf

Comments

For all n, a(A000079(n)) = A000225(n+1), i.e. a(2^n) = (2^(n+1))-1.

For n>=1, a(A000225(n)) = A000325(n).

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

0

|

...................1...................

3 2

7......../ \........6 4......../ \........5

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

15 14 11 13 8 9 10 12

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

etc.

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

Permutation A233278 gives the mirror image of the same tree.

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8191
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse permutation: A233275.

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

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

Related arrays: A255555, A255557.

Similarly constructed permutation pairs: A005940/A156552, A135141/A227413, A232751/A232752, A233277/A233278, A233279/A233280, A003188/A006068.

Formula

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

As a composition of related permutations:

a(n) = A233278(A054429(n)).

Extensions

Name changed and the illustration of binary tree added by Antti Karttunen, Apr 19 2015