cp's OEIS Frontend

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.

%I A154436 #24 May 16 2020 02:32:15
%S A154436 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,
%T A154436 16,17,21,20,22,23,63,62,60,61,57,56,58,59,51,50,48,49,53,52,54,55,39,
%U A154436 38,36,37,33,32,34,35,43,42,40,41,45,44,46,47,127,126,124,125,121,120
%N 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.
%C A154436 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 (A054429-reflected conjugate of this permutation) and the second one induces Gray Code's inverse permutation A006068.
%H A154436 A. Karttunen, <a href="/A154436/b154436.txt">Table of n, a(n) for n = 0..2047</a>
%H A154436 S. Wolfram, R. Lamy, <a href="http://forum.wolframscience.com/showthread.php?threadid=107">Discussion on the NKS Forum</a>
%H A154436 <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%H A154436 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A154436 a(0) = 0, a(1) = 1, a(2) = 3, a(3) = 2,
%F A154436 if n > 3 and n even a(2*n) = 2*n + 1, a(2*n+1) = 2*a(n),
%F A154436 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
%e A154436 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.
%t A154436 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 *)
%o A154436 (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))))))))))
%o A154436 (PARI)
%o A154436 a003188(n) = bitxor(n, n>>1);
%o A154436 a054429(n) = 3<<#binary(n\2) - n - 1;
%o A154436 a(n) = if(n==0, 0, a054429(a003188(a054429(n)))); \\ _Indranil Ghosh_, Jun 11 2017
%o A154436 (Python)
%o A154436 from sympy import floor
%o A154436 def a003188(n): return n^(n>>1)
%o A154436 def a054429(n): return 1 if n==1 else 2*a054429(floor(n/2)) + 1 - n%2
%o A154436 def a(n): return 0 if n==0 else a054429(a003188(a054429(n))) # _Indranil Ghosh_, Jun 11 2017
%o A154436 (R)
%o A154436 maxn <- 63 # by choice
%o A154436 a <- c(1, 3, 2)
%o A154436 for(n in 2:maxn){
%o A154436   if(n%%2 == 0) {a[2*n] <- 2*a[n]+1 ; a[2*n+1] <- 2*a[n]}
%o A154436   else          {a[2*n] <- 2*a[n]   ; a[2*n+1] <- 2*a[n]+1}
%o A154436 }
%o A154436 (a <- c(0,a))
%o A154436 # _Yosu Yurramendi_, Apr 10 2020
%Y A154436 Inverse: A154435.
%Y A154436 a(n) = A059893(A154438(A059893(n))) = A054429(A003188(A054429(n))).
%Y A154436 Corresponds to A122302 in the group of Catalan bijections.
%Y A154436 Cf. also A153141-A153142, A154439-A154448, A072376.
%K A154436 nonn,base
%O A154436 0,3
%A A154436 _Antti Karttunen_, Jan 17 2009
%E A154436 Spelling/notation corrections by _Charles R Greathouse IV_, Mar 18 2010