A154439 Permutation of nonnegative integers induced by Basilica group generating wreath recursion: a = (1,b), b = s(1,a), starting from the inactive (fixing) state a.

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 14, 15, 12, 13, 16, 17, 18, 19, 20, 21, 22, 23, 28, 29, 30, 31, 24, 25, 27, 26, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 56, 57, 58, 59, 60, 61, 62, 63, 48, 49, 50, 51, 54, 55, 52, 53, 64, 65, 66, 67, 68, 69, 70, 71

Offset

0,3

Comments

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 inactive (fixing) state a and rewriting bits from the second most significant bit to the least significant end.

References

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.

Links

A. Karttunen, Table of n, a(n) for n = 0..2047

L. Bartholdi and B. Virag, Amenability via random walks, arXiv:math/0305262 [math.GR], 2003.

L. Bartholdi and B. Virag, Amenability via random walks, Duke Math. J. Volume 130, Number 1 (2005), 39--56.

Index entries for sequences related to groups

Index entries for sequences that are permutations of the natural numbers

Example

Starting from the second most significant bit, we continue complementing every second bit (in this case, not starting before at the thirdmost significant bit), as long as the first zero is encountered, which is also complemented if its distance to the most significant bit is even, after which the remaining bits are left intact. E.g. 121 = 1111001 in binary. Complementing its thirdmost significant bit and the first zero-bit two positions right of it (i.e. bit-2, 4 steps to the most significant bit, bit-6), we obtain "11011.." after which the rest of the bits stay same, so we get 1101101, which is 109's binary representation, thus a(121)=109. On the other hand, 125 = 1111101 in binary and the transducer complements the bits at positions 4 and 2, yielding 11010.. and then switches to the fixing state at the zero encounted at bit-position 1, without complementing it (as it is 5 steps from the msb) and the rest are fixed, so we get 1101001, which is 105's binary representation, thus a(125)=105.

Prog

(MIT Scheme:) (define (A154439 n) (if (< n 2) n (let loop ((maskbit (A072376 n)) (p 0) (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))))))))

Crossrefs

Inverse: A154440. a(n) = A154445(A153142(n)) = A054429(A154443(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154441-A154448. Corresponds to A154449 in the group of Catalan bijections.

Sequence in context: A069769 A307747 A347758 * A154440 A371959 A371960

Adjacent sequences: A154436 A154437 A154438 * A154440 A154441 A154442

Keyword

nonn,base

Author

Antti Karttunen, Jan 17 2009

Extensions

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

Status

approved