|
%I #28 Sep 04 2016 17:21:20
%S 1,2,3,4,5,7,6,8,9,12,10,15,13,14,11,16,17,21,18,27,22,24,19,31,28,29,
%T 23,30,25,26,20,32,33,38,34,48,39,42,35,58,49,51,40,54,43,45,36,63,59,
%U 60,50,61,52,53,41,62,55,56,44,57,46,47,37,64,65,71,66,86,72,76,67,106,87,90,73,96,77,80,68,121,107,109,88
%N Permutation of natural numbers: a(1) = 1; a(2n) = A087686(1+a(n)), a(2n+1) = A088359(a(n)), where A088359 and A087686 = numbers that occur only once (resp. more than once) in A004001.
%C This sequence can be represented as a binary tree. Each left hand child is produced as A087686(1+n), and each right hand child as A088359(n), when their parent contains n:
%C |
%C ...................1...................
%C 2 3
%C 4......../ \........5 7......../ \........6
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C 8 9 12 10 15 13 14 11
%C 16 17 21 18 27 22 24 19 31 28 29 23 30 25 26 20
%C etc.
%C The level k of the tree contains all numbers of binary width k, like many base-2 related permutations (A003188, A054429, etc). For a proof, see A267110, which gives the contents of each parent node (for node containing n).
%C A276442 shows the mirror-image of the same tree.
%H Antti Karttunen, <a href="/A267112/b267112.txt">Table of n, a(n) for n = 1..8192</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/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) = A087686(1+a(n)), a(2n+1) = A088359(a(n)).
%F As a composition of other permutations:
%F a(n) = A276442(A054429(n)).
%F a(n) = A276344(A233276(n)).
%F a(n) = A276346(A233278(n)).
%F a(n) = A276446(A003188(n)).
%F Other identities. For all n >= 0:
%F a(2^n) = 2^n. [Follows from the properties (3) and (4) of A004001 given on page 227 of Kubo & Vakil paper.]
%F a(A000225(n)) = A006127(n), i.e., a((2^(n+1)) - 1) = 2^n + n. [Numbers at the right edge.]
%o (Scheme, with memoization-macro definec)
%o (definec (A267112 n) (cond ((< n 2) n) ((even? n) (A087686 (+ 1 (A267112 (/ n 2))))) (else (A088359 (A267112 (/ (- n 1) 2))))))
%Y Inverse: A267111.
%Y Cf. A000079, A000225, A004001, A006127, A087686, A088359, A267110.
%Y Similar or related permutations: A003188, A054429, A276442, A233276, A233278, A276344, A276346, A276446.
%Y Cf. also permutations A266411, A266412 and arrays A265901, A265903.
%K nonn,tabf,look
%O 1,2
%A _Antti Karttunen_, Jan 10 2016
|
