This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A153141 Permutation of nonnegative integers: A059893-conjugate of A153151. 31

%I

%S 0,1,3,2,7,6,4,5,15,14,12,13,8,9,10,11,31,30,28,29,24,25,26,27,16,17,

%T 18,19,20,21,22,23,63,62,60,61,56,57,58,59,48,49,50,51,52,53,54,55,32,

%U 33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,127,126,124,125,120,121

%N Permutation of nonnegative integers: A059893-conjugate of A153151.

%C This permutation is induced by a wreath recursion a = s(a,b), b = (b,b) (i.e. binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on page 103 of Bondarenko, Grigorchuk, et al. paper, starting from the active (swapping) state a and rewriting bits from the second most significant bit to the least significant end, continuing complementing as long as the first 1-bit is reached, which is the last bit to be complemented.

%C The automorphism group of infinite binary tree (isomorphic to an infinitely iterated wreath product of cyclic groups of two elements) embeds naturally into the group of "size-preserving Catalan bijections". Scheme-function psi gives an isomorphism that maps these kind of permutations to the corresponding Catalan automorphisms/bijections (that act on S-expressions). The following identities hold: *A069770 = psi(A063946) (Just swap the left and right subtrees of the root), *A057163 = psi(A054429) (Reflect the whole tree), *A069767 = psi(A153141), *A069768 = psi(A153142), *A122353 = psi(A006068), *A122354 = psi(A003188), *A122301 = psi(A154435), *A122302 = psi(A154436) and from *A154449 = psi(A154439) up to *A154458 = psi(A154448). See also comments at A153246 and A153830.

%H A. Karttunen, <a href="/A153141/b153141.txt">Table of n, a(n) for n = 0..2047</a>

%H Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, Sunic, <a href="http://arxiv.org/abs/0803.3555">Classification of groups generated by 3-state automata over a 2-letter alphabet</a>, pp. 8--9 & 103.

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

%e 18 = 10010 in binary and after complementing the second, third and the fourthmost significant bits at positions 3, 2 and 1, we get 1110., at which point we stop (because bit-1 was originally 1) and fix the rest, so we get 11100 (28 in binary), thus a(18)=28. This is the inverse of "binary adding machine". See pages 8, 9 and 103 in Bondarenko, Grigorchuk, et al. paper.

%e 19 = 10011 in binary. By complementing bits in (zero-based) positions 3, 2 and 1 we get 11101 in binary, which is 29 in decimal, thus a(19)=29.

%o (MIT Scheme:)

%o (define (a153141 n) (if (< n 2) n (let loop ((maskbit (a072376 n)) (z n)) (cond ((zero? maskbit) z) ((not (zero? (modulo (floor->exact (/ n maskbit)) 2))) (- z maskbit)) (else (loop (floor->exact (/ maskbit 2)) (+ z maskbit)))))))

%o (define (psi inftreeperm) (lambda (s) (swap-binary-tree-according-to-infbintree-permutation s inftreeperm)))

%o (define (swap-binary-tree-according-to-infbintree-permutation s inftreeperm) (cond ((not (= 1 (inftreeperm 1))) (error "Function inftreeperm should return 1 for 1 and it should be one-to-one and onto!")) (else (let fork ((s s) (nod 1)) (cond ((pair? s) (fork (car s) (* 2 nod)) (fork (cdr s) (+ (* 2 nod) 1)) (let ((node-dest (inftreeperm nod)) (left-dest (inftreeperm (* 2 nod))) (right-dest (inftreeperm (1+ (* 2 nod))))) (cond ((or (not (= (floor->exact (/ left-dest 2)) node-dest)) (not (= (floor->exact (/ right-dest 2)) node-dest))) (error (format #t "Function inftreeperm is not an automorphism of an infinite binary tree. Either the left or right child flees from its parent: (inftreeperm ~a)=~a. Left: (inftreeperm ~a)=~a, Right: (inftreeperm ~a)=~a.\n" nod node-dest (* 2 nod) left-dest (1+ (* 2 nod)) right-dest))) ((= (1+ left-dest) right-dest)) (else (*A069770! s))))))) s)))

%Y Inverse: A153142. a(n) = A059893(A153151(A059893(n))) = A059894(A153152(A059894(n))) = A154440(A154445(n)) = A154442(A154443(n)). Corresponds to A069767 in the group of Catalan bijections. Cf. also A154435-A154436, A154439-A154448, A072376.

%Y Differs from A006068 for the first time at n=14, where a(14)=10 while A006068(14)=11.

%K nonn,base

%O 0,3

%A _Antti Karttunen_, Dec 20 2008

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .