cp's OEIS Frontend

A153141 Permutation of nonnegative integers: A059893-conjugate of A153151.

%I A153141 #54 Apr 25 2024 14:58:11
%S A153141 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 A153141 18,19,20,21,22,23,63,62,60,61,56,57,58,59,48,49,50,51,52,53,54,55,32,
%U A153141 33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,127,126,124,125,120,121
%N A153141 Permutation of nonnegative integers: A059893-conjugate of A153151.
%C A153141 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 A153141 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 A153141 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 A153141 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 A153141 A. Karttunen, <a href="/A153141/b153141.txt">Table of n, a(n) for n = 0..2047</a>
%H A153141 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 A153141 S. Wolfram and R. Lamy, <a href="http://forum.wolframscience.com/showthread.php?threadid=107">Discussion on the NKS Forum</a>
%H A153141 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A153141 Conjecture: 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
%F A153141 From _Mikhail Kurkov_, Dec 22 2023: (Start)
%F A153141 a(n) < 2^k iff n < 2^k for k >= 0.
%F A153141 Conjectured formulas:
%F A153141 a(2^m + k) = f(2^m + f(k)) for m >= 0, 0 <= k < 2^m with a(0) = 0.
%F A153141 a(n) = f(A153142(f(n))) for n > 0 with a(0) = 0. (End)
%e A153141 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 A153141 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 A153141 (MIT Scheme:)
%o A153141 (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 A153141 (define (psi inftreeperm) (lambda (s) (swap-binary-tree-according-to-infbintree-permutation s inftreeperm)))
%o A153141 (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 A153141 (Python)
%o A153141 def ok(n): return n&(n - 1)==0
%o A153141 def a153151(n): return n if n<2 else 2*n - 1 if ok(n) else n - 1
%o A153141 def A(n): return (int(bin(n)[2:][::-1], 2) - 1)/2
%o A153141 def msb(n): return n if n<3 else msb(n/2)*2
%o A153141 def a059893(n): return A(n) + msb(n)
%o A153141 def a(n): return 0 if n==0 else a059893(a153151(a059893(n))) # _Indranil Ghosh_, Jun 09 2017
%o A153141 (R)
%o A153141 maxlevel <- 5 # by choice
%o A153141 a <- 1
%o A153141 for(m in 1:maxlevel){
%o A153141 a[2^m    ] <- 2^(m+1) - 1
%o A153141 a[2^m + 1] <- 2^(m+1) - 2
%o A153141 for (k in 1:(2^m-1)){
%o A153141    a[2^(m+1) + 2*k    ] <- 2*a[2^m + k]
%o A153141    a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1}
%o A153141 }
%o A153141 a <- c(0,a)
%o A153141 # _Yosu Yurramendi_, Aug 01 2020
%Y A153141 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 A153141 Differs from A006068 for the first time at n=14, where a(14)=10 while A006068(14)=11.
%Y A153141 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 A153141 nonn,base
%O A153141 0,3
%A A153141 _Antti Karttunen_, Dec 20 2008