

A154436


Permutation of nonnegative integers induced by Lamplighter group generating wreath recursion, variant 1: a = s(a,b), b = (a,b), starting from the state a.


15



0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 13, 9, 8, 10, 11, 31, 30, 28, 29, 25, 24, 26, 27, 19, 18, 16, 17, 21, 20, 22, 23, 63, 62, 60, 61, 57, 56, 58, 59, 51, 50, 48, 49, 53, 52, 54, 55, 39, 38, 36, 37, 33, 32, 34, 35, 43, 42, 40, 41, 45, 44, 46, 47, 127, 126, 124, 125, 121, 120
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This permutation is induced by the first Lamplighter group generating wreath recursion a = s(a,b), b = (a,b) (i.e. binary transducer, where s means that the bits at that state are toggled: 0 <> 1) given on page 104 of 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. It is the same automaton as given in figure 1 on page 211 of Grigorchuk and Zuk paper. Note that the fourth wreath recursion on page 104 of Bondarenko, et al. paper induces similarly the binary reflected Gray code A003188 (A054429reflected conjugate of this permutation) and the second one induces Gray Code's inverse permutation A006068.


LINKS

A. Karttunen, Table of n, a(n) for n = 0..2047
S. Wolfram, R. Lamy, Discussion on the NKS Forum
Index entries for sequences related to groups
Index entries for sequences that are permutations of the natural numbers


FORMULA

a(0) = 0, a(1) = 1, a(2) = 3, a(3) = 2,
if n > 3 and n even a(2*n) = 2*n + 1, a(2*n+1) = 2*a(n),
if n > 3 and n odd a(2*n) = 2*a(n) , a(2*n+1) = 2*a(n) + 1.  Yosu Yurramendi, Apr 10 2020


EXAMPLE

312 = 100111000 in binary. Starting from the second most significant bit and, as we begin with the swapping state a, we complement the bits up to and including the first one encountered and so the beginning of the binary expansion is complemented as 1110....., then, as we switch to the inactive state b, the following bits are kept same, up to and including the first zero encountered, after which the binary expansion is 1110110.., after which we switch again to the complementing mode (state a) and we obtain 111011011, which is 475's binary representation, thus a(312)=475.


MATHEMATICA

Function[s, Map[s[[#]] &, BitXor[#, Floor[#/2]] & /@ s]]@ Flatten@ Table[Range[2^(n + 1)  1, 2^n, 1], {n, 0, 6}] (* Michael De Vlieger, Jun 11 2017 *)


PROG

(MIT Scheme:) (define (A154436 n) (if (< n 2) n (let loop ((maskbit (A072376 n)) (state 1) (z 1)) (if (zero? maskbit) z (let ((dombit (modulo (floor>exact (/ n maskbit)) 2))) (cond ((= state dombit) (loop (floor>exact (/ maskbit 2)) ( 1 state) (+ z z (modulo ( state dombit) 2)))) (else (loop (floor>exact (/ maskbit 2)) state (+ z z (modulo ( state dombit) 2))))))))))
(PARI)
a003188(n) = bitxor(n, n>>1);
a054429(n) = 3<<#binary(n\2)  n  1;
a(n) = if(n==0, 0, a054429(a003188(a054429(n)))); \\ Indranil Ghosh, Jun 11 2017
(Python)
from sympy import floor
def a003188(n): return n^(n>>1)
def a054429(n): return 1 if n==1 else 2*a054429(floor(n/2)) + 1  n%2
def a(n): return 0 if n==0 else a054429(a003188(a054429(n))) # Indranil Ghosh, Jun 11 2017
(R)
maxn < 63 # by choice
a < c(1, 3, 2)
for(n in 2:maxn){
if(n%%2 == 0) {a[2*n] < 2*a[n]+1 ; a[2*n+1] < 2*a[n]}
else {a[2*n] < 2*a[n] ; a[2*n+1] < 2*a[n]+1}
}
(a < c(0, a))
# Yosu Yurramendi, Apr 10 2020


CROSSREFS

Inverse: A154435.
a(n) = A059893(A154438(A059893(n))) = A054429(A003188(A054429(n))).
Corresponds to A122302 in the group of Catalan bijections.
Cf. also A153141A153142, A154439A154448, A072376.
Sequence in context: A276441 A153141 A006068 * A269402 A268934 A268832
Adjacent sequences: A154433 A154434 A154435 * A154437 A154438 A154439


KEYWORD

nonn,base


AUTHOR

Antti Karttunen, Jan 17 2009


EXTENSIONS

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


STATUS

approved



