

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 3state automata over a 2letter 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 0bit at even distance from the most significant bit or B) the first 1bit at odd distance from the most significant bit.


LINKS

A. Karttunen, Table of n, a(n) for n = 0..2047
Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, Sunic, Classification of groups generated by 3state automata over a 2letter alphabet, arXiv:0803.3555 [math.GR], 2008, p. 144.
Index entries for sequences that are permutations of the natural numbers


EXAMPLE

25 = 11001 in binary, the first zerobit 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 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^m1)){
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, A153141A153142, A154435A154436, A154439A154446. Corresponds to A154458 in the group of Catalan bijections.
Sequence in context: A096899 A265345 A340447 * A099896 A160679 A335536
Adjacent sequences: A154445 A154446 A154447 * A154449 A154450 A154451


KEYWORD

nonn,base


AUTHOR

Antti Karttunen, Jan 17 2009


EXTENSIONS

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010


STATUS

approved



