cp's OEIS Frontend

A166404 Self-inverse permutation of natural numbers obtained by exchanging the run lengths of adjacent runs of ones and zeros in the binary expansion of n, starting from the most significant run of 1's. (See the example lines).

%I A166404 #15 Dec 13 2023 19:12:10
%S A166404 0,1,2,3,6,5,4,7,14,13,10,11,12,9,8,15,30,29,26,27,22,21,20,23,28,25,
%T A166404 18,19,24,17,16,31,62,61,58,59,54,53,52,55,46,45,42,43,44,41,40,47,60,
%U A166404 57,50,51,38,37,36,39,56,49,34,35,48,33,32,63,126,125,122,123,118,117
%N A166404 Self-inverse permutation of natural numbers obtained by exchanging the run lengths of adjacent runs of ones and zeros in the binary expansion of n, starting from the most significant run of 1's. (See the example lines).
%H A166404 A. Karttunen, <a href="/A166404/b166404.txt">Table of n, a(n) for n = 0..65535</a>
%H A166404 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A166404 68 in binary is 1000100, so it consists of runs of 1, 3, 1 and 2 bits of the same value (alternatively 1 or 0) counted from the most significant end. Swapping these (the first with the second, the third with the fourth, etc.) gives the run lengths of [3,1,2,1], and the reconstructed binary string looks now as 1110110, which is 118 in binary. Thus a(68)=118.
%e A166404 Likewise, 67 in binary is 1000011, so it consists of runs of 1, 4 and 2 counted from the most significant end. Now we can swap just the first and second of these runs, with the remaining third run staying as it is, so we get run lengths of [4,1,2], and the reconstructed binary string looks now as 1111011, which is 123 in binary. Thus a(67)=123.
%o A166404 (MIT/GNU Scheme)
%o A166404 (define (A166404 n) (let ((runlens (binexp->runcount1list n))) (runcount1list->binexp (interleave (bisect runlens 1) (bisect runlens 0)))))
%o A166404 (define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))
%o A166404 (define (runcount1list->binexp lista) (let loop ((lista lista) (s 0) (state 1)) (cond ((null? lista) s) (else (loop (cdr lista) (+ (* s (expt 2 (car lista))) (* state (- (expt 2 (car lista)) 1))) (- 1 state))))))
%o A166404 (define (bisect lista parity) (let loop ((lista lista) (i 0) (z (list))) (cond ((null? lista) (reverse! z)) ((eq? i parity) (loop (cdr lista) (modulo (1+ i) 2) (cons (car lista) z))) (else (loop (cdr lista) (modulo (1+ i) 2) z)))))
%o A166404 (define (interleave a b) (let loop ((z (list)) (a a) (b b)) (cond ((and (null? a) (null? b)) (reverse! z)) ((null? a) (loop (cons (car b) z) a (cdr b))) ((null? b) (loop (cons (car a) z) (cdr a) b)) (else (loop (cons (car b) (cons (car a) z)) (cdr a) (cdr b))))))
%o A166404 (Python)
%o A166404 def a(n):
%o A166404     if n==0: return 0
%o A166404     x=bin(n)[2:]
%o A166404     r=[]
%o A166404     s=1
%o A166404     p=""
%o A166404     for i in range(1, len(x)):
%o A166404         if x[i - 1]==x[i]: s+=1
%o A166404         else:
%o A166404             r+=[s, ]
%o A166404             s=1
%o A166404     l=r+[s]
%o A166404     L=[]
%o A166404     if len(l)%2==0:
%o A166404         for i in range(0, len(l), 2): L+=[l[i + 1], l[i]]
%o A166404     else:
%o A166404         b=l[-1]
%o A166404         for i in range(0, len(l) - 1, 2): L+=[l[i + 1], l[i]]
%o A166404         L+=[b, ]
%o A166404     for i in range(len(L)):
%o A166404         if i%2==0: p+='1'*L[i]
%o A166404         else: p+='0'*L[i]
%o A166404     return int(p, 2)
%o A166404 print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 12 2017
%Y A166404 Cf. A056539, A166166.
%K A166404 nonn,base
%O A166404 0,3
%A A166404 _Antti Karttunen_, Oct 20 2009