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