

A153141


Permutation of nonnegative integers: A059893conjugate of A153151.


35



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, 18, 19, 20, 21, 22, 23, 63, 62, 60, 61, 56, 57, 58, 59, 48, 49, 50, 51, 52, 53, 54, 55, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 127, 126, 124, 125, 120, 121
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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 1bit is reached, which is the last bit to be complemented.
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 "sizepreserving Catalan bijections". Schemefunction psi gives an isomorphism that maps this kind of permutation to the corresponding Catalan automorphism/bijection (that acts on Sexpressions). 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.
a(1) to a(2^n) is the sequence of row sequency numbers in a HadamardWalsh matrix of order 2^n, when constructed to give "dyadic" or Payley sequency ordering.  Ross Drewe, Mar 15 2014
In the SternBrocot enumeration system for positive rationals (A007305/A047679), this permutation converts the denominator into the numerator: A007305(n) = A047679(a(n)).  Yosu Yurramendi, Aug 01 2020


LINKS

A. Karttunen, Table of n, a(n) for n = 0..2047
Ievgen Bondarenko, Rostislav Grigorchuk, Rostyslav Kravchenko, Yevgen Muntyan, Volodymyr Nekrashevych, Dmytro Savchuk, Zoran Sunic, Classification of groups generated by 3state automata over a 2letter alphabet, arXiv:0803.3555 [math.GR], 2008, pp. 89 & 103.
S. Wolfram, R. Lamy, Discussion on the NKS Forum
Index entries for sequences that are permutations of the natural numbers


EXAMPLE

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 bit1 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.
19 = 10011 in binary. By complementing bits in (zerobased) positions 3, 2 and 1 we get 11101 in binary, which is 29 in decimal, thus a(19)=29.


PROG

(MIT Scheme:)
(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)))))))
(define (psi inftreeperm) (lambda (s) (swapbinarytreeaccordingtoinfbintreepermutation s inftreeperm)))
(define (swapbinarytreeaccordingtoinfbintreepermutation s inftreeperm) (cond ((not (= 1 (inftreeperm 1))) (error "Function inftreeperm should return 1 for 1 and it should be onetoone and onto!")) (else (let fork ((s s) (nod 1)) (cond ((pair? s) (fork (car s) (* 2 nod)) (fork (cdr s) (+ (* 2 nod) 1)) (let ((nodedest (inftreeperm nod)) (leftdest (inftreeperm (* 2 nod))) (rightdest (inftreeperm (1+ (* 2 nod))))) (cond ((or (not (= (floor>exact (/ leftdest 2)) nodedest)) (not (= (floor>exact (/ rightdest 2)) nodedest))) (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 nodedest (* 2 nod) leftdest (1+ (* 2 nod)) rightdest))) ((= (1+ leftdest) rightdest)) (else (*A069770! s))))))) s)))
(Python)
def ok(n): return n&(n  1)==0
def a153151(n): return n if n<2 else 2*n  1 if ok(n) else n  1
def A(n): return (int(bin(n)[2:][::1], 2)  1)/2
def msb(n): return n if n<3 else msb(n/2)*2
def a059893(n): return A(n) + msb(n)
def a(n): return 0 if n==0 else a059893(a153151(a059893(n))) # Indranil Ghosh, Jun 09 2017
(R)
maxlevel < 5 # by choice
a < 1
for(m in 1:maxlevel){
a[2^m ] < 2^(m+1)  1
a[2^m + 1] < 2^(m+1)  2
for (k in 1:(2^m1)){
a[2^(m+1) + 2*k ] < 2*a[2^m + k]
a[2^(m+1) + 2*k + 1] < 2*a[2^m + k] + 1}
}
a < c(0, a)
# Yosu Yurramendi, Aug 01 2020


CROSSREFS

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 A154435A154436, A154439A154448, A072376.
Differs from A006068 for the first time at n=14, where a(14)=10 while A006068(14)=11.
A240908A240910 these give "natural" instead of "dyadic" sequency ordering values for HadamardWalsh matrices, orders 8,16,32.  Ross Drewe, Mar 15 2014
Sequence in context: A233276 A304083 A276441 * A006068 A154436 A269402
Adjacent sequences: A153138 A153139 A153140 * A153142 A153143 A153144


KEYWORD

nonn,base


AUTHOR

Antti Karttunen, Dec 20 2008


STATUS

approved



