A072376 -id:A072376 - cp's OEIS frontend

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.

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

A257697 a(n)=0 for n <= 1; for n >= 2, a(n) = largest number that can be obtained by rotating non-msb bits of binary expansion of n (with A080541 or A080542), without the most significant bit of n: a(n) = A053645(A256999(n)).

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 2, 3, 0, 4, 4, 6, 4, 6, 6, 7, 0, 8, 8, 12, 8, 10, 12, 14, 8, 12, 10, 14, 12, 14, 14, 15, 0, 16, 16, 24, 16, 20, 24, 28, 16, 20, 20, 26, 24, 26, 28, 30, 16, 24, 20, 28, 20, 26, 26, 30, 24, 28, 26, 30, 28, 30, 30, 31, 0, 32, 32, 48, 32, 40, 48, 56, 32, 36, 40, 50, 48, 52, 56, 60, 32, 40, 36, 52, 40, 42, 50, 58, 48, 50, 52, 54, 56, 58, 60

Offset: 0

Antti Karttunen, May 16 2015

For each n, apart from powers of 2, a(n) gives the lexicographically largest representative from the equivalence class of binary necklaces obtained by successively rotating (with A080541 or A080542) all the other bits than the most significant bit in the binary representation of n.

Antti Karttunen, Table of n, a(n) for n = 0..8192

Cf. A000079, A053645, A072376, A080541, A080542, A256999.

(define (A257697 n) (A053645 (A256999 n)))

a(n) = A053645(A256999(n)).
Other identities and observations:
For all n >= 0, a(n) >= A053645(n).
Apart from powers of 2 (A000079), for any other n, a(n) >= A072376(n).

A373095 a(n) = a[n/4] + a[n/8] + a[n/16] + ..., where a(0) = 0, a(1) = 1, and [ ] = floor.

Original entry on oeis.org

0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5

Offset: 0

Clark Kimberling, May 28 2024

nonn

Every term is a Fibonacci number (A000045), and every nonnegative Fibonacci number occurs.

			a(20) = a(5) + a(2) + a(1) = 1 + 0 + 1 = 2.

Cf. A000045, A005187, A072376 (sum starts with a[n/2]), A373096, A373097.

a[0] = 0; a[1] = 1;
a[n_] := a[n] = Sum[a[Floor[n/2^k]], {k, 2, n}]
Table[a[n], {n, 0, 570}]

The initial 16 terms (0s and 1s) are followed by 16 twos, then 32 threes, then 64 fives,... . Specifically, for m>=3, there are 2^(m+1) F(m)'s.

cp's OEIS Frontend

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

A257697 a(n)=0 for n <= 1; for n >= 2, a(n) = largest number that can be obtained by rotating non-msb bits of binary expansion of n (with A080541 or A080542), without the most significant bit of n: a(n) = A053645(A256999(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A373095 a(n) = a[n/4] + a[n/8] + a[n/16] + ..., where a(0) = 0, a(1) = 1, and [ ] = floor.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula