|
%I #51 Apr 21 2024 22:16:01
%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 the 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 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.
%C 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
%C In the Stern-Brocot 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
%H A. Karttunen, <a href="/A153141/b153141.txt">Table of n, a(n) for n = 0..2047</a>
%H Ievgen Bondarenko, Rostislav Grigorchuk, Rostyslav Kravchenko, Yevgen Muntyan, Volodymyr Nekrashevych, Dmytro Savchuk, and Zoran Sunic, <a href="http://arxiv.org/abs/0803.3555">Classification of groups generated by 3-state automata over a 2-letter alphabet</a>, arXiv:0803.3555 [math.GR], 2008, pp. 8--9 & 103.
%H S. Wolfram and R. Lamy, <a href="http://forum.wolframscience.com/showthread.php?threadid=107">Discussion on the NKS Forum</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F a(n) = f(a(f(a(A053645(n)))) + A053644(n)) for n > 0 where f(n) = A054429(n) for n > 0 with f(0) = 0. - _Mikhail Kurkov_, Oct 02 2023 [verification needed]
%F From _Mikhail Kurkov_, Dec 22 2023: (Start)
%F a(2^m + k) = f(2^m + f(k)) for m >= 0, 0 <= k < 2^m with a(0) = 0.
%F a(n) = f(A153142(f(n))) for n > 0 with a(0) = 0.
%F a(n) < 2^k iff n < 2^k for k >= 0. (End) [verification needed]
%e 18 = 10010 in binary and after complementing the second, third and fourth most 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 the 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)))
%o (Python)
%o def ok(n): return n&(n - 1)==0
%o def a153151(n): return n if n<2 else 2*n - 1 if ok(n) else n - 1
%o def A(n): return (int(bin(n)[2:][::-1], 2) - 1)/2
%o def msb(n): return n if n<3 else msb(n/2)*2
%o def a059893(n): return A(n) + msb(n)
%o def a(n): return 0 if n==0 else a059893(a153151(a059893(n))) # _Indranil Ghosh_, Jun 09 2017
%o (R)
%o maxlevel <- 5 # by choice
%o a <- 1
%o for(m in 1:maxlevel){
%o a[2^m ] <- 2^(m+1) - 1
%o a[2^m + 1] <- 2^(m+1) - 2
%o for (k in 1:(2^m-1)){
%o a[2^(m+1) + 2*k ] <- 2*a[2^m + k]
%o a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1}
%o }
%o a <- c(0,a)
%o # _Yosu Yurramendi_, Aug 01 2020
%o (PARI) b1(n) = if(n == 0, 0, 3 * 2 ^ logint(n, 2) - n - 1)
%o a(n) = if(n == 0, 0, my(A = 2^logint(n, 2)); b1(b1(n - A) + A)) \\ _Mikhail Kurkov_, Dec 22 2023 [verification needed]
%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.
%Y A240908-A240910 these give "natural" instead of "dyadic" sequency ordering values for Hadamard-Walsh matrices, orders 8,16,32. - _Ross Drewe_, Mar 15 2014
%K nonn,base,changed
%O 0,3
%A _Antti Karttunen_, Dec 20 2008
|
