|
%I #14 Dec 12 2017 08:13:05
%S 0,1,3,2,6,7,4,5,12,13,14,15,8,9,11,10,24,25,26,27,28,29,30,31,16,17,
%T 18,19,22,23,20,21,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,32,
%U 33,34,35,36,37,38,39,44,45,46,47,40,41,43,42,96,97,98,99,100,101,102
%N Permutation of nonnegative integers induced by Basilica group generating wreath recursion: a = (1,b), b = s(1,a), starting from the active (swapping) state b.
%C This permutation is induced by the Basilica group generating wreath recursion a = (1,b), b = s(1,a) (i.e. binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on the page 40 of Bartholdi and Virag paper, starting from the active (switching) state b and rewriting bits from the second most significant bit to the least significant end.
%D R. I. Grigorchuk and A. Zuk, Spectral properties of a torsion free weakly branch group defined by a three state automaton, Contemporary Mathematics 298 (2002), 57--82.
%H A. Karttunen, <a href="/A154441/b154441.txt">Table of n, a(n) for n = 0..2047</a>
%H L. Bartholdi and B. Virag, <a href="https://arxiv.org/abs/math/0305262">Amenability via random walks</a>, arXiv:math/0305262 [math.GR], 2003.
%H L. Bartholdi and B. Virag, <a href="https://projecteuclid.org/euclid.dmj/1131804019">Amenability via random walks</a>, Duke Math. J. Volume 130, Number 1 (2005), 39--56.
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e Starting from the second most significant bit, we continue complementing every second bit (in this case, starting from the second most significant bit), as long as the first zero is encountered, which is also complemented if its distance to the most significant bit is odd, after which the remaining bits are left intact. E.g. 121 = 1111001 in binary. Complementing its second and fourth most significant bits (positions 5 & 3) and stopping at the first zero-bit at position 2 (which is not complemented, as its distance to the msb is 6), we obtain "10100.." after which the rest of the bits stay same, so we get 1010001, which is 81's binary representation, thus a(121)=81. On the other hand, 125 = 1111101 in binary and the transducer complements the bits at positions 5, 3 and also the first zero at the position 1 (because at odd distance from the msb), yielding 101011., after which the remaining bit stays same, thus we get 1010111, which is 87's binary representation, thus a(125)=87.
%o (MIT Scheme:) (define (A154441 n) (if (< n 2) n (let loop ((maskbit (A072376 n)) (p 1) (z n)) (cond ((zero? maskbit) z) ((zero? (modulo (floor->exact (/ n maskbit)) 2)) (+ z (* p maskbit))) (else (loop (floor->exact (/ maskbit 2)) (- 1 p) (- z (* p maskbit))))))))
%Y Inverse: A154442. a(n) = A154443(A153142(n)) = A054429(A154445(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154451 in the group of Catalan bijections.
%K nonn,base
%O 0,3
%A _Antti Karttunen_, Jan 17 2009
%E Spelling/notation corrections by _Charles R Greathouse IV_, Mar 18 2010
|
