A154446 -id:A154446 - cp's OEIS frontend

A154448 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state a, rewriting bits from the second most significant bit toward the least significant end.

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

Offset: 0

Antti Karttunen, Jan 17 2009

This permutation of natural numbers is induced by the first generator of group 2861 mentioned on page 144 of "Classification of groups generated by 3-state automata over a 2-letter alphabet" paper. It can be computed by starting scanning n's binary expansion rightward from the second most significant bit, complementing every bit down to and including A) either the first 0-bit at even distance from the most significant bit or B) the first 1-bit at odd distance from the most significant bit.

			25 = 11001 in binary, the first zero-bit at odd distance from the msb is immediately at where we start (at the second most significant bit), so we complement it and fix the rest, yielding 10001 (17 in binary), thus a(25)=17.

Antti Karttunen, Table of n, a(n) for n = 0..2047
Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, and Sunic, Classification of groups generated by 3-state automata over a 2-letter alphabet, arXiv:0803.3555 [math.GR], 2008, p. 144.
Index entries for sequences that are permutations of the natural numbers

Inverse: A154447. a(n) = A054429(A154447(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154446. Corresponds to A154458 in the group of Catalan bijections.

maxlevel <- 5 # by choice
a <- 1
for(m in 0:maxlevel) {
  for(k in 0:(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
  }
  x <- floor(2^(m+2)/3)
  a[2*x    ] <- 2*a[x] + 1
  a[2*x + 1] <- 2*a[x]
}
(a <- c(0, a))
# Yosu Yurramendi, Oct 12 2020

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

A154442 Permutation of nonnegative integers: the inverse of A154441.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154441. a(n) = A153141(A154444(n)) = A054429(A154446(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154452 in the group of Catalan bijections.

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

A154440 Permutation of nonnegative integers: the inverse of A154439.

Original entry on oeis.org

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, 31, 30, 24, 25, 26, 27, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 56, 57, 58, 59, 62, 63, 60, 61, 48, 49, 50, 51, 52, 53, 54, 55, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154439. a(n) = A153141(A154446(n)) = A054429(A154444(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154442-A154448. Corresponds to A154450 in the group of Catalan bijections.

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

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154446. a(n) = A154439(A153141(n)) = A054429(A154441(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154455 in the group of Catalan bijections.

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

A154456 Signature permutation of a Catalan bijection: The inverse of A154455.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

nonn

This automorphism of rooted plane binary trees switches the two descendant trees for every other vertex as it descends along the 000... ray, starting swapping already at the root. Specifically, *A154456 = psi(A154446), where the isomorphism psi is given in A153141 (see further comments there).

Inverse: A154455. a(n) = A069768(A154450(n)) = A057163(A154452(A057163(n))). Cf. A069770, A154454.

Differs from A082346 and A122328 for the first time at n=26, where a(26)=49, while A082346(26)=A122328(26)=50. Differs from A129611 for the first time at n=91, where a(91)=196, while A129611(91)=195.

A154447 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state b, rewriting bits from the second most significant bit toward the least significant end.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

This permutation of natural numbers is induced by the second generator of group 2861 mentioned on page 144 of "Classification of groups generated by 3-state automata over a 2-letter alphabet" paper. It can be computed by starting scanning n's binary expansion rightward from the second most significant bit, complementing every bit down to and including A) either the first 0-bit at odd distance from the most significant bit or B) the first 1-bit at even distance from the most significant bit.

			25 = 11001 in binary, the first zero-bit at odd distance from the msb is at position 1 (distance 3) and the first one-bit at even distance from the msb is at position 0 (distance 4), thus we stop at the former, after complementing the bits 3-1, which gives us 10111 (23 in binary), thus a(25)=23.

A. Karttunen, Table of n, a(n) for n = 0..2047
Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, Sunic, Classification of groups generated by 3-state automata over a 2-letter alphabet, arXiv:0803.3555 [math.GR], 2008, p. 144.
Index entries for sequences that are permutations of the natural numbers

Inverse: A154448. a(n) = A054429(A154448(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154446. Corresponds to A154457 in the group of Catalan bijections.

maxlevel <- 5 # by choice
a <- 1
for(m in 0:maxlevel) {
  for(k in 0:(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
  }
  x <- floor(2^m*5/3)
  a[2*x    ] <- 2*a[x] + 1
  a[2*x + 1] <- 2*a[x]
}
(a <- c(0, a))
# Yosu Yurramendi, Oct 12 2020

cp's OEIS Frontend

A154448 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state a, rewriting bits from the second most significant bit toward the least significant end.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

R

Extensions

A154442 Permutation of nonnegative integers: the inverse of A154441.

Views

Author

Keywords

Links

Crossrefs

Extensions

A154440 Permutation of nonnegative integers: the inverse of A154439.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A154456 Signature permutation of a Catalan bijection: The inverse of A154455.

Views

Author

Keywords

Comments

Links

Crossrefs

A154447 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state b, rewriting bits from the second most significant bit toward the least significant end.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

R