login
Permutation of nonnegative integers: A059893-conjugate of A153152.
19

%I #16 Jan 13 2024 10:11:45

%S 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,

%T 22,23,18,19,17,16,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,40,

%U 41,42,43,44,45,46,47,36,37,38,39,34,35,33,32,96,97,98,99,100,101,102

%N Permutation of nonnegative integers: A059893-conjugate of A153152.

%C 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.

%C 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

%H A. Karttunen, <a href="/A153142/b153142.txt">Table of n, a(n) for n = 0..2047</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e 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.

%o (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)))))))

%o (Python)

%o def ok(n): return n&(n - 1)==0

%o def a153152(n): return n if n<2 else (n + 1)/2 if ok(n + 1) else n + 1

%o def A(n): return (int(bin(n)[2:][::-1], 2) - 1)/2

%o def msb(n): return n if n<3 else msb(n/2)*2

%o def a059893(n): return A(n) + msb(n)

%o def a(n): return 0 if n==0 else a059893(a153152(a059893(n))) # _Indranil Ghosh_, Jun 09 2017

%o (R)

%o maxlevel <- 5 # by choice

%o a <- 1

%o for(m in 1:maxlevel){

%o a[2^(m+1) - 1] <- 2^m

%o a[2^(m+1) - 2] <- 2^m + 1

%o for (k in 0:(2^m-2)){

%o a[2^(m+1) + 2*k ] <- 2*a[2^m + k]

%o a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1}

%o }

%o a <- c(0, a)

%o # _Yosu Yurramendi_, Aug 30 2020

%Y 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.

%K nonn,base

%O 0,3

%A _Antti Karttunen_, Dec 20 2008