A153246 -id:A153246 - cp's OEIS frontend

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

Antti Karttunen, Dec 20 2008

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

			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.

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

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

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

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

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)

A153830 Index sequence to A089840: positions of bijections that preserve A127302 (the non-oriented form of binary trees) and whose behavior does not depend on whether there are internal or terminal nodes (leaves) in the neighborhood of any vertex.

Original entry on oeis.org

0, 1, 3, 7, 15, 21, 27, 46, 92, 114, 149, 169, 225, 251, 299, 400, 638, 753, 1233, 1348, 1705, 1823, 1992, 2097, 2335, 2451, 2995, 3128, 3485, 3607, 3677, 3771, 4214, 4307, 4631, 5254, 6692, 7393, 10287, 10988, 13145, 13860, 20353, 21054

Offset: 0

Antti Karttunen, Jan 07 2009

nonn

These elements form a subgroup in A089840 (A089839) isomorphic to a group consisting of all finitely iterated wreath products of the form S_2 wr S_2 wr ... wr S_2 and each is an image of some finitary automorphism of an infinite binary tree. E.g. A089840(1) = *A069770 is an image of the generator A of Grigorchuk Group. See comments at A153246 and A153141.

The defining properties are propagated by all recursive transformations of A089840 which themselves do not behave differently depending whether there are internal or terminal vertices in the neighborhood of any vertex (at least the ones given in A122201-A122204, A122283-A122290, A130400-A130403), so this sequence gives also the corresponding positions in those tables.

A. Karttunen, Table of n, a(n) for n = 0..175
A. Karttunen, C-program for computing the initial terms of this sequence

Subset of A153829. Cf. also A153831, A153826, A153827, A153828, A153832, A153833.

A153250 Array A(x,y): A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ... formed by growing a bud (a single V-node) on the y-th leaf of the binary tree A014486(x).

Original entry on oeis.org

1, 0, 2, 0, 3, 4, 0, 0, 5, 6, 0, 0, 6, 7, 9, 0, 0, 0, 8, 10, 11, 0, 0, 0, 0, 11, 12, 14, 0, 0, 0, 0, 14, 13, 15, 16, 0, 0, 0, 0, 0, 15, 16, 17, 19, 0, 0, 0, 0, 0, 0, 19, 18, 20, 23, 0, 0, 0, 0, 0, 0, 0, 20, 21, 24, 25, 0, 0, 0, 0, 0, 0, 0, 0, 22, 25, 26, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 27, 29, 30

Offset: 0

Antti Karttunen, Dec 22 2008

Note: the leaf positions are indexed so that the rightmost one in the tree is leaf 0, etc., up to the leftmost one, which is the leaf with index A072643(x). In this manner, terms on each row stay in monotone order. Row n (starting from row 0) contains A072643(n)+1 nonzero terms and then an infinite number of zeros after that. A153249 gives only the nonzero terms. Can be used to compute "fleeing tree" sequences for Catalan bijections. See comments at A153246.

			Top left corner of array:
1,  0,  0,  0,  0, ...
2,  3,  0,  0,  0, ...
4,  5,  6,  0,  0, ...
6,  7,  8,  0,  0, ...
9,  10, 11, 14, 0, ...
11, 12, 13, 15, 0, ...
14, 15, 16, 19, 0, ...
By inserting a bud (\/) at leaf position 1 of binary tree A014486(2) (leaf positions numbered for clarification):
....1....0
.....\../
..2...\/
...\../
....\/
we obtain a binary tree:
.......
.\../..
..\/...
...\../
....\/
.\../
..\/
which is the 5th binary tree encoded by A014486. Thus A(2,1)=5.

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

Cf. A002262, A025581.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

Formula

A153830 Index sequence to A089840: positions of bijections that preserve A127302 (the non-oriented form of binary trees) and whose behavior does not depend on whether there are internal or terminal nodes (leaves) in the neighborhood of any vertex.

Views

Author

Keywords

Comments

Links

Crossrefs

A153250 Array A(x,y): A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ... formed by growing a bud (a single V-node) on the y-th leaf of the binary tree A014486(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A153247 Number of fleeing trees computed for Catalan bijection A123493.

Views

Author

Keywords

Comments

Crossrefs

Extensions