cp's OEIS Frontend

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

%I A153142 #16 Jan 13 2024 10:11:45
%S A153142 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 A153142 22,23,18,19,17,16,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,40,
%U A153142 41,42,43,44,45,46,47,36,37,38,39,34,35,33,32,96,97,98,99,100,101,102
%N A153142 Permutation of nonnegative integers: A059893-conjugate of A153152.
%C A153142 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 A153142 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 A153142 A. Karttunen, <a href="/A153142/b153142.txt">Table of n, a(n) for n = 0..2047</a>
%H A153142 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A153142 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 A153142 (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 A153142 (Python)
%o A153142 def ok(n): return n&(n - 1)==0
%o A153142 def a153152(n): return n if n<2 else (n + 1)/2 if ok(n + 1) else n + 1
%o A153142 def A(n): return (int(bin(n)[2:][::-1], 2) - 1)/2
%o A153142 def msb(n): return n if n<3 else msb(n/2)*2
%o A153142 def a059893(n): return A(n) + msb(n)
%o A153142 def a(n): return 0 if n==0 else  a059893(a153152(a059893(n))) # _Indranil Ghosh_, Jun 09 2017
%o A153142 (R)
%o A153142 maxlevel <- 5 # by choice
%o A153142 a <- 1
%o A153142 for(m in 1:maxlevel){
%o A153142   a[2^(m+1) - 1] <- 2^m
%o A153142   a[2^(m+1) - 2] <- 2^m + 1
%o A153142   for (k in 0:(2^m-2)){
%o A153142     a[2^(m+1) + 2*k    ] <- 2*a[2^m + k]
%o A153142     a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1}
%o A153142 }
%o A153142 a <- c(0, a)
%o A153142 # _Yosu Yurramendi_, Aug 30 2020
%Y A153142 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 A153142 nonn,base
%O A153142 0,3
%A A153142 _Antti Karttunen_, Dec 20 2008