login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A153141 Permutation of nonnegative integers: A059893-conjugate 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 1-bit 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 "size-preserving Catalan bijections". Scheme-function psi gives an isomorphism that maps this kind of permutation to the corresponding Catalan automorphism/bijection (that acts 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.

a(1) to a(2^n) is the sequence of row sequency numbers in a Hadamard-Walsh matrix of order 2^n,  when constructed to give "dyadic" or Payley sequency ordering. - Ross Drewe, Mar 15 2014

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 3-state automata over a 2-letter alphabet, arXiv:0803.3555 [math.GR], 2008, pp. 8--9 & 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 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.

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.

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) (swap-binary-tree-according-to-infbintree-permutation s inftreeperm)))

(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)))

(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

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 A154435-A154436, A154439-A154448, A072376.

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

A240908-A240910 these give "natural" instead of "dyadic" sequency ordering values for Hadamard-Walsh 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 11 16:07 EST 2019. Contains 329019 sequences. (Running on oeis4.)