cp's OEIS Frontend

A154447 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state b, rewriting bits from the second most significant bit toward the least significant end.

%I A154447 #10 Oct 24 2020 17:32:12
%S A154447 0,1,3,2,6,7,5,4,12,13,14,15,11,10,8,9,24,25,26,27,28,29,30,31,22,23,
%T A154447 21,20,16,17,18,19,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,44,
%U A154447 45,46,47,43,42,40,41,32,33,34,35,36,37,38,39,96,97,98,99,100,101,102
%N A154447 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state b, rewriting bits from the second most significant bit toward the least significant end.
%C A154447 This permutation of natural numbers is induced by the second generator of group 2861 mentioned on page 144 of "Classification of groups generated by 3-state automata over a 2-letter alphabet" paper. It can be computed by starting scanning n's binary expansion rightward from the second most significant bit, complementing every bit down to and including A) either the first 0-bit at odd distance from the most significant bit or B) the first 1-bit at even distance from the most significant bit.
%H A154447 A. Karttunen, <a href="/A154447/b154447.txt">Table of n, a(n) for n = 0..2047</a>
%H A154447 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>, arXiv:0803.3555 [math.GR], 2008, p. 144.
%H A154447 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A154447 25 = 11001 in binary, the first zero-bit at odd distance from the msb is at position 1 (distance 3) and the first one-bit at even distance from the msb is at position 0 (distance 4), thus we stop at the former, after complementing the bits 3-1, which gives us 10111 (23 in binary), thus a(25)=23.
%o A154447 (MIT Scheme:) (define (A154447 n) (if (< n 2) n (let loop ((maskbit (A072376 n)) (p 0) (z n)) (cond ((zero? maskbit) z) ((= p (modulo (floor->exact (/ n maskbit)) 2)) (+ z (* (- 1 (* 2 p)) maskbit))) (else (loop (floor->exact (/ maskbit 2)) (- 1 p) (- z (* (- 1 (* 2 p)) maskbit))))))))
%o A154447 (R)
%o A154447 maxlevel <- 5 # by choice
%o A154447 a <- 1
%o A154447 for(m in 0:maxlevel) {
%o A154447   for(k in 0:(2^m-1)) {
%o A154447   a[2^(m+1) + 2*k    ] <- 2*a[2^m + k]
%o A154447   a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1
%o A154447   }
%o A154447   x <- floor(2^m*5/3)
%o A154447   a[2*x    ] <- 2*a[x] + 1
%o A154447   a[2*x + 1] <- 2*a[x]
%o A154447 }
%o A154447 (a <- c(0, a))
%o A154447 # _Yosu Yurramendi_, Oct 12 2020
%Y A154447 Inverse: A154448. a(n) = A054429(A154448(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154446. Corresponds to A154457 in the group of Catalan bijections.
%K A154447 nonn,base
%O A154447 0,3
%A A154447 _Antti Karttunen_, Jan 17 2009