cp's OEIS Frontend

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.

%I A154435 #25 Jul 31 2020 19:24:34
%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 nonnegative 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="/A154435/b154435.txt">Table of n, a(n) for n = 0..2047</a>
%H A154435 I. Bondarenko, R. Grigorchuk, R. Kravchenko, Y. Muntyan, V. Nekrashevych, D. Savchuk, Z. 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, arXiv:0803.3555 [math.GR], 2008.
%H A154435 R. I. Grigorchuk and A. Zuk, <a href="https://doi.org/10.1023/A:1012061801279">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 S. Wolfram, R. Lamy, <a href="http://forum.wolframscience.com/showthread.php?threadid=107">Discussion on the NKS Forum</a>
%H A154435 <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%H A154435 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</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))))))))))
%o A154435 (Python)
%o A154435 from sympy import floor
%o A154435 def a006068(n):
%o A154435     s=1
%o A154435     while True:
%o A154435         ns=n>>s
%o A154435         if ns==0: break
%o A154435         n=n^ns
%o A154435         s<<=1
%o A154435     return n
%o A154435 def a054429(n): return 1 if n==1 else 2*a054429(floor(n/2)) + 1 - n%2
%o A154435 def a(n): return 0 if n==0 else a054429(a006068(a054429(n))) # _Indranil Ghosh_, Jun 11 2017
%o A154435 (R)
%o A154435 maxn <- 63 # by choice
%o A154435 a <- c(1,3,2) # If it were a <- 1:3, it would be A180200
%o A154435 for(n in 2:maxn){
%o A154435   a[2*n  ] <- 2*a[n] + (a[n]%%2 == 0)
%o A154435   a[2*n+1] <- 2*a[n] + (a[n]%%2 != 0)  }
%o A154435 a
%o A154435 # _Yosu Yurramendi_, Jun 21 2020
%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.
%K A154435 nonn,base
%O A154435 0,3
%A A154435 _Antti Karttunen_, Jan 17 2009
%E A154435 Spelling/notation corrections by _Charles R Greathouse IV_, Mar 18 2010