A153152 -id:A153152 - cp's OEIS frontend

A153142 Permutation of nonnegative integers: A059893-conjugate of A153152.

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

Offset: 0

Antti Karttunen, Dec 20 2008

This sequence can be also obtained by starting complementing n's binary expansion from the second most significant bit, continuing towards lsb-end until the first 0-bit is reached, which is the last bit to be complemented.

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

			29 = 11101 in binary. By complementing bits in (zero-based) positions 3, 2 and 1 we get 10011 in binary, which is 19 in decimal, thus a(29)=19.

Inverse: A153141. a(n) = A059893(A153152(A059893(n))) = A059894(A153151(A059894(n))). Differs from A003188 for the first time at n=10, where a(10)=14 while A003188(10)=15. Cf. also A072376. Corresponds to A069768 in the group of Catalan bijections.

def ok(n): return n&(n - 1)==0
def a153152(n): return n if n<2 else (n + 1)/2 if ok(n + 1) 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(a153152(a059893(n))) # Indranil Ghosh, Jun 09 2017

maxlevel <- 5 # by choice
a <- 1
for(m in 1:maxlevel){
  a[2^(m+1) - 1] <- 2^m
  a[2^(m+1) - 2] <- 2^m + 1
  for (k in 0:(2^m-2)){
    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 30 2020

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

Original entry on oeis.org

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)

A153151 Rotated binary decrementing: For n<2 a(n) = n, if n=2^k, a(n) = 2*n-1, otherwise a(n) = n-1.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 20 2008

Without the initial 0, a(n) is the lexicographically minimal sequence of distinct positive integers such that all values of a(n) mod n are distinct and nonnegative. - Ivan Neretin, Apr 27 2015
A002487(n)/A002487(n+1), n > 0, runs through all the reduced nonnegative rationals exactly once. A002487 is the Stern's sequence. Permutation from denominators (A002487(n+1))
1   2 1   3 2 3 1   4  3  5  2  5  3  4  1
where labels  are
1   2 3   4 5 6 7   8  9 10 11 12 13 14 15
to numerators (A002487(n))
1   1 2   1 3 2 3   1  4  3  5  2  5  3  4
where changed labels  are
1   3 2   7 4 5 6  15  8  9 10 11 12 13 14
Thus, b(n) = A002487(n+1), b(a(n)) = A002487(n), n>0. - Yosu Yurramendi, Jul 07 2016

Inverse: A153152.

Cf. A059893, A059894, A153141, A153142.

a := n -> if n < 2 then n elif convert(convert(n, base, 2), `+`) = 1 then 2*n-1 else n-1 fi: seq(a(n), n=0..70); # Peter Luschny, Jul 16 2016

Table[Which[n < 2, n, IntegerQ[Log[2, n]], 2 n - 1, True, n - 1], {n, 0, 70}] (* Michael De Vlieger, Apr 27 2015 *)

def ok(n): return n&(n - 1)==0
def a(n): return n if n<2 else 2*n - 1 if ok(n) else n - 1 # Indranil Ghosh, Jun 09 2017

nmax <- 126 # by choice
a <- c(1,3,2)
for(n in 3:nmax) a[n+1] <- n
for(m in 0:floor(log2(nmax))) a[2^m] <- 2^(m+1) - 1
a <- c(0, a)
# Yosu Yurramendi, Sep 05 2020

a(n) = A059893(A153141(A059893(n))) = A059894(A153142(A059894(n))).

A316472 Inverse permutation to A316385.

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Jul 04 2018

			A316385(42) = 50 hence a(50) = 42.

Cf. A000523, A053645, A059893, A153142, A316385.

b1(n) = my(b=binary(n)); fromdigits(concat(b[1], Vecrev(vector(#b-1, k, b[k+1]))), 2); \\ A059893
b2(n) = if(n < 2, n, if((n + 1) == 2^logint(n + 1, 2), (n + 1) / 2, n + 1)) \\ A153152
a(n) = my(A = 2^logint(n, 2), B = b1(b2(b1(n))) - A); (2 * B + 1) * A / 2 ^ (if(B == 0, -1, logint(B, 2)) + 1) \\ Mikhail Kurkov, Sep 09 2023 [verification needed]

a(n) = (2*b(n) + 1)*2^(L(n) - L(b(n)) - 1) where b(n) = A053645(A153142(n)) and where L(n) = A000523(n) for n > 0 with L(0) = -1. - Mikhail Kurkov, Sep 09 2023 [verification needed]

cp's OEIS Frontend

A153142 Permutation of nonnegative integers: A059893-conjugate of A153152.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

Formula

A153151 Rotated binary decrementing: For n<2 a(n) = n, if n=2^k, a(n) = 2*n-1, otherwise a(n) = n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

R

Formula

A316472 Inverse permutation to A316385.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula