%I #12 Sep 03 2016 17:04:47
%S 1,3,2,6,7,5,4,11,14,13,15,10,12,9,8,20,26,25,30,23,29,28,31,19,24,22,
%T 27,18,21,17,16,37,47,46,57,44,56,55,62,41,53,52,61,50,60,59,63,36,45,
%U 43,54,40,51,49,58,35,42,39,48,34,38,33,32,70,85,84,105,82,104,103,120,79,101,100,119,98,118,117,126,75,95,94
%N Permutation of natural numbers: a(1) = 1; a(2n) = A088359(a(n)), a(2n+1) = A087686(1+a(n)), where A088359 & A087686 = numbers that occur only once & more than once in A004001.
%C This sequence can be represented as a binary tree. Each left hand child is produced as A088359(n), and each right hand child as A087686(1+n), when their parent contains n:
%C |
%C ...................1...................
%C 3 2
%C 6......../ \........7 5......../ \........4
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C 11 14 13 15 10 12 9 8
%C 20 26 25 30 23 29 28 31 19 24 22 27 18 21 17 16
%C etc.
%C As in the mirror image permutation A267112, the level k of the tree contains all numbers of binary width k like many other base-2 related permutations (A003188, A054429, A233278, etc). For a proof, see A267110, which gives the contents of each parent node (for a node containing n > 1).
%H Antti Karttunen, <a href="/A276442/b276442.txt">Table of n, a(n) for n = 1..8191</a>
%H T. Kubo and R. Vakil, <a href="http://dx.doi.org/10.1016/0012-365X(94)00303-Z">On Conway's recursive sequence</a>, Discr. Math. 152 (1996), 225-252.
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F a(1) = 1; after which, a(2n) = A088359(a(n)), a(2n+1) = A087686(1+a(n)).
%F As a composition of other permutations:
%F a(n) = A267112(A054429(n)).
%F a(n) = A276344(A233278(n)).
%F a(n) = A276346(A233276(n)).
%F a(n) = A276444(A003188(n)).
%o (Scheme)
%o (definec (A276442 n) (cond ((< n 2) n) ((even? n) (A088359 (A276442 (/ n 2)))) (else (A087686 (+ 1 (A276442 (/ (- n 1) 2)))))))
%Y Inverse: A276441.
%Y Cf. A004001, A087686, A088359, A267110.
%Y Related or similar permutations: A003188, A054429, A233276, A233278, A267112, A276344, A276346, A276444.
%K nonn,base,tabf
%O 1,2
%A _Antti Karttunen_, Sep 03 2016
|