

A154435


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


15



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



OFFSET

0,3


COMMENTS

This permutation is induced by the third Lamplighter group generating wreath recursion a = s(b,a), 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.


LINKS

A. Karttunen, Table of n, a(n) for n = 0..2047
R. I. Grigorchuk and A. Zuk, The lamplighter group as a group generated by a 2state automaton and its spectrum, Geometriae Dedicata, vol. 87 (2001), no. 13, pp. 209244.
Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, Sunic, Classification of groups generated by 3state automata over a 2letter alphabet, pp. 89 & 103, arXiv:0803.3555 [math.GR], 2008.
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


EXAMPLE

475 = 111011011 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 zero encountered and so the beginning of the binary expansion is complemented as 1001....., then, as we switch to the inactive state b, the following bits are kept same, again up to and including the first zero encountered, after which the binary expansion is 1001110.., after which we switch again to the active state (state a), which complements the two rightmost 1's and we obtain the final answer 100111000, which is 312's binary representation, thus a(475)=312.


PROG

(MIT Scheme:) (define (A154435 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 ((= 0 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))))))))))
(Python)
from sympy import floor
def a006068(n):
s=1
while True:
ns=n>>s
if ns==0: break
n=n^ns
s<<=1
return n
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(a006068(a054429(n))) # Indranil Ghosh, Jun 11 2017


CROSSREFS

Inverse: A154436. a(n) = A059893(A154437(A059893(n))) = A054429(A006068(A054429(n))). Corresponds to A122301 in the group of Catalan bijections. Cf. also A153141A153142, A154439A154448, A072376.
Sequence in context: A269401 A268933 A268831 * A006042 A100280 A268827
Adjacent sequences: A154432 A154433 A154434 * A154436 A154437 A154438


KEYWORD

nonn,base


AUTHOR

Antti Karttunen, Jan 17 2009


EXTENSIONS

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


STATUS

approved



