cp's OEIS Frontend

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

%I A154448 #18 Jan 13 2024 10:41:56
%S A154448 0,1,3,2,7,6,4,5,14,15,13,12,8,9,10,11,28,29,30,31,27,26,24,25,16,17,
%T A154448 18,19,20,21,22,23,56,57,58,59,60,61,62,63,54,55,53,52,48,49,50,51,32,
%U A154448 33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,112,113,114,115,116,117
%N A154448 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state a, rewriting bits from the second most significant bit toward the least significant end.
%C A154448 This permutation of natural numbers is induced by the first 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 even distance from the most significant bit or B) the first 1-bit at odd distance from the most significant bit.
%H A154448 Antti Karttunen, <a href="/A154448/b154448.txt">Table of n, a(n) for n = 0..2047</a>
%H A154448 Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, and 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 A154448 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A154448 25 = 11001 in binary, the first zero-bit at odd distance from the msb is immediately at where we start (at the second most significant bit), so we complement it and fix the rest, yielding 10001 (17 in binary), thus a(25)=17.
%o A154448 (MIT/GNU Scheme) (define (A154448 n) (if (< n 2) n (let loop ((maskbit (A072376 n)) (p 1) (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 A154448 (R)
%o A154448 maxlevel <- 5 # by choice
%o A154448 a <- 1
%o A154448 for(m in 0:maxlevel) {
%o A154448   for(k in 0:(2^m-1)){
%o A154448   a[2^(m+1) + 2*k    ] <- 2*a[2^m + k]
%o A154448   a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1
%o A154448   }
%o A154448   x <- floor(2^(m+2)/3)
%o A154448   a[2*x    ] <- 2*a[x] + 1
%o A154448   a[2*x + 1] <- 2*a[x]
%o A154448 }
%o A154448 (a <- c(0, a))
%o A154448 # _Yosu Yurramendi_, Oct 12 2020
%Y A154448 Inverse: A154447. a(n) = A054429(A154447(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154446. Corresponds to A154458 in the group of Catalan bijections.
%K A154448 nonn,base
%O A154448 0,3
%A A154448 _Antti Karttunen_, Jan 17 2009
%E A154448 Spelling/notation corrections by _Charles R Greathouse IV_, Mar 18 2010