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
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
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, Dec 20 2008
STATUS
approved