%I A154435
%S A154435 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,
%T A154435 22,23,18,19,17,16,53,52,54,55,50,51,49,48,58,59,57,56,61,60,62,63,42,
%U A154435 43,41,40,45,44,46,47,37,36,38,39,34,35,33,32,106,107,105,104,109,108
%N A154435 Permutation of non-negative integers induced by Lamplighter group generating 
               wreath recursion, variant 3: a = s(b,a), b = (a,b), starting from 
               the state a.
%C A154435 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.
%H A154435 A. Karttunen, <a href="b154435.txt">Table of n, a(n) for n = 0..2047</
               a>
%H A154435 <a href="Sindx_Per.html#IntegerPermutation">Index entries for sequences 
               that are permutations of the natural numbers</a>
%H A154435 R. I. Grigorchuk and A. Zuk, <a href="http://www.springerlink.com/content/
               r462872j42160j3h/">The lamplighter group as a group generated by 
               a 2-state automaton and its spectrum</a>, Geometriae Dedicata, vol. 
               87 (2001), no. 1-3, pp. 209--244.
%H A154435 Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, Sunic, 
               <a href="http://arxiv.org/abs/0803.3555">Classification of groups 
               generated by 3-state automata over a 2-letter alphabet</a>, pp. 8--9 
               & 103.
%H A154435 S. Wolfram, R. Lamy, <a href="http://forum.wolframscience.com/showthread.php?threadid=107">
               Discussion on the NKS Forum</a>
%e A154435 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.
%o A154435 (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))))))))))
%Y A154435 Inverse: A154436. a(n) = A059893(A154437(A059893(n))) = A054429(A006068(A054429(n))). 
               Corresponds to A122301 in the group of Catalan bijections. Cf. also 
               A153141-A153142, A154439-A154448, A072376.
%Y A154435 Sequence in context: A153142 A154447 A003188 this_sequence A006042 A100280 
               A092745
%Y A154435 Adjacent sequences: A154432 A154433 A154434 this_sequence A154436 A154437 
               A154438
%K A154435 nonn,base
%O A154435 0,3
%A A154435 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Jan 17 2009