login
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.
14
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, 18, 19, 20, 21, 22, 23, 56, 57, 58, 59, 60, 61, 62, 63, 54, 55, 53, 52, 48, 49, 50, 51, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 112, 113, 114, 115, 116, 117
OFFSET
0,3
COMMENTS
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.
LINKS
Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, and Sunic, Classification of groups generated by 3-state automata over a 2-letter alphabet, arXiv:0803.3555 [math.GR], 2008, p. 144.
EXAMPLE
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.
PROG
(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))))))))
(R)
maxlevel <- 5 # by choice
a <- 1
for(m in 0:maxlevel) {
for(k in 0:(2^m-1)){
a[2^(m+1) + 2*k ] <- 2*a[2^m + k]
a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1
}
x <- floor(2^(m+2)/3)
a[2*x ] <- 2*a[x] + 1
a[2*x + 1] <- 2*a[x]
}
(a <- c(0, a))
# Yosu Yurramendi, Oct 12 2020
CROSSREFS
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.
Sequence in context: A265345 A340447 A360983 * A099896 A160679 A335536
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, Jan 17 2009
EXTENSIONS
Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010
STATUS
approved