A153141 Permutation of nonnegative integers: A059893-conjugate of A153151.

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

Offset: 0

Author

Antti Karttunen, Dec 20 2008

Keywords

• nonn
• base

Comments

This permutation is induced by a wreath recursion a = s(a,b), b = (b,b) (i.e., binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on page 103 of the 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, continuing complementing as long as the first 1-bit is reached, which is the last bit to be complemented.

The automorphism group of infinite binary tree (isomorphic to an infinitely iterated wreath product of cyclic groups of two elements) embeds naturally into the group of "size-preserving Catalan bijections". Scheme-function psi gives an isomorphism that maps this kind of permutation to the corresponding Catalan automorphism/bijection (that acts on S-expressions). The following identities hold: *A069770 = psi(A063946) (just swap the left and right subtrees of the root), *A057163 = psi(A054429) (reflect the whole tree), *A069767 = psi(A153141), *A069768 = psi(A153142), *A122353 = psi(A006068), *A122354 = psi(A003188), *A122301 = psi(A154435), *A122302 = psi(A154436) and from *A154449 = psi(A154439) up to *A154458 = psi(A154448). See also comments at A153246 and A153830.

a(1) to a(2^n) is the sequence of row sequency numbers in a Hadamard-Walsh matrix of order 2^n, when constructed to give "dyadic" or Payley sequency ordering. - Ross Drewe, Mar 15 2014

In the Stern-Brocot enumeration system for positive rationals (A007305/A047679), this permutation converts the denominator into the numerator: A007305(n) = A047679(a(n)). - Yosu Yurramendi, Aug 01 2020

Examples

			18 = 10010 in binary and after complementing the second, third and fourth most significant bits at positions 3, 2 and 1, we get 1110, at which point we stop (because bit-1 was originally 1) and fix the rest, so we get 11100 (28 in binary), thus a(18)=28. This is the inverse of "binary adding machine". See pages 8, 9 and 103 in the Bondarenko, Grigorchuk, et al. paper.
19 = 10011 in binary. By complementing bits in (zero-based) positions 3, 2 and 1 we get 11101 in binary, which is 29 in decimal, thus a(19)=29.
		

Links

• A. Karttunen, Table of n, a(n) for n = 0..2047
• Ievgen Bondarenko, Rostislav Grigorchuk, Rostyslav Kravchenko, Yevgen Muntyan, Volodymyr Nekrashevych, Dmytro Savchuk, and Zoran Sunic, Classification of groups generated by 3-state automata over a 2-letter alphabet, arXiv:0803.3555 [math.GR], 2008, pp. 8--9 & 103.
• S. Wolfram and R. Lamy, Discussion on the NKS Forum
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A153142. a(n) = A059893(A153151(A059893(n))) = A059894(A153152(A059894(n))) = A154440(A154445(n)) = A154442(A154443(n)). Corresponds to A069767 in the group of Catalan bijections. Cf. also A154435-A154436, A154439-A154448, A072376.

Differs from A006068 for the first time at n=14, where a(14)=10 while A006068(14)=11.

A240908-A240910 these give "natural" instead of "dyadic" sequency ordering values for Hadamard-Walsh matrices, orders 8,16,32. - Ross Drewe, Mar 15 2014

Programs

Python

def ok(n): return n&(n - 1)==0
def a153151(n): return n if n<2 else 2*n - 1 if ok(n) else n - 1
def A(n): return (int(bin(n)[2:][::-1], 2) - 1)/2
def msb(n): return n if n<3 else msb(n/2)*2
def a059893(n): return A(n) + msb(n)
def a(n): return 0 if n==0 else a059893(a153151(a059893(n))) # Indranil Ghosh, Jun 09 2017

R

maxlevel <- 5 # by choice
a <- 1
for(m in 1:maxlevel){
a[2^m    ] <- 2^(m+1) - 1
a[2^m + 1] <- 2^(m+1) - 2
for (k in 1:(2^m-1)){
   a[2^(m+1) + 2*k    ] <- 2*a[2^m + k]
   a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1}
}
a <- c(0,a)
# Yosu Yurramendi, Aug 01 2020

Formula

Conjecture: a(n) = f(a(f(a(A053645(n)))) + A053644(n)) for n > 0 where f(n) = A054429(n) for n > 0 with f(0) = 0. - Mikhail Kurkov, Oct 02 2023

From Mikhail Kurkov, Dec 22 2023: (Start)

a(n) < 2^k iff n < 2^k for k >= 0.

Conjectured formulas:

a(2^m + k) = f(2^m + f(k)) for m >= 0, 0 <= k < 2^m with a(0) = 0.

a(n) = f(A153142(f(n))) for n > 0 with a(0) = 0. (End)