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,3

Comments

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

Links

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

Index entries for sequences that are permutations of the natural numbers

Example

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.

Prog

(MIT/GNU Scheme) (define (a153142 n) (if (< n 2) n (let loop ((maskbit (a072376 n)) (z n)) (cond ((zero? maskbit) z) ((zero? (modulo (floor->exact (/ n maskbit)) 2)) (+ z maskbit)) (else (loop (floor->exact (/ maskbit 2)) (- z maskbit)))))))
(Python)
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
(R)
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

Crossrefs

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.

Sequence in context: A304084 A276442 A233275 * A154447 A003188 A269401

Adjacent sequences: A153139 A153140 A153141 * A153143 A153144 A153145

Keyword

nonn,base

Author

Antti Karttunen, Dec 20 2008

Status

approved