login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 2
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, 18, 19, 24, 17, 16, 31, 62, 61, 58, 59, 54, 53, 52, 55, 46, 45, 42, 43, 44, 41, 40, 47, 60, 57, 50, 51, 38, 37, 36, 39, 56, 49, 34, 35, 48, 33, 32, 63, 126, 125, 122, 123, 118, 117 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

A. Karttunen, Table of n, a(n) for n = 0..65535

Index entries for sequences that are permutations of the natural numbers

EXAMPLE

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.

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.

PROG

(GNU/MIT Scheme:)

(define (A166404 n) (let ((runlens (binexp->runcount1list n))) (runcount1list->binexp (interleave (bisect runlens 1) (bisect runlens 0)))))

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

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

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

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

(Python)

def a(n):

    if n==0: return 0

    x=bin(n)[2:]

    r=[]

    s=1

    p=""

    for i in xrange(1, len(x)):

        if x[i - 1]==x[i]: s+=1

        else:

            r+=[s, ]

            s=1

    l=r+[s]

    L=[]

    if len(l)%2==0:

        for i in xrange(0, len(l), 2): L+=[l[i + 1], l[i]]

    else:

        b=l[-1]

        for i in xrange(0, len(l) - 1, 2): L+=[l[i + 1], l[i]]

        L+=[b, ]

    for i in xrange(len(L)):

        if i%2==0: p+='1'*L[i]

        else: p+='0'*L[i]

    return int(p, 2)

print [a(n) for n in xrange(0, 101)] # Indranil Ghosh, Jun 12 2017

CROSSREFS

Cf. A056539, A166166.

Sequence in context: A105726 A284460 A175949 * A166166 A106452 A254118

Adjacent sequences:  A166401 A166402 A166403 * A166405 A166406 A166407

KEYWORD

nonn,base

AUTHOR

Antti Karttunen, Oct 20 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 04:14 EST 2019. Contains 319323 sequences. (Running on oeis4.)