This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A166166 Write n in binary with each run (of either digit b) of the k-th longest distinct run-length replaced with a run of digit b of a length equal to that of the k-th shortest distinct run-length. Convert back to decimal for a(n). (See comment.) 2
0, 1, 2, 3, 6, 5, 4, 7, 14, 27, 10, 25, 12, 19, 8, 15, 30, 119, 108, 13, 102, 21, 100, 113, 28, 11, 76, 9, 24, 71, 16, 31, 62, 495, 952, 59, 54, 435, 52, 57, 910, 411, 42, 409, 50, 403, 904, 481, 60, 55, 44, 51, 38, 307, 36, 49, 56, 39, 568, 35, 48, 271, 32, 63, 126 (list; graph; refs; listen; history; text; internal format)



This sequence is a self-inverse permutation of the positive integers.

Clarification of definition: Let b(k) be the k-th largest distinct run-length (considering both runs of 0's and of 1's) in binary n. Let r be the number of distinct run-lengths in binary n. Rewrite binary n by replacing each run (of any given digit) of length b(k) with a run (of that same digit) of length b(r+1-k). Convert the resulting binary number to decimal to get a(n).

A binary number alternates between "runs" each completely of 1's and runs completely of 0's. No two runs of the same digit are consecutive.


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

Index entries for sequences that are permutations of the natural numbers


134 in binary is 10000110. So there is a run of length 1, followed by a run of length 4, followed by a run of length 2, followed finally by a run of length 1. The distinct run-lengths, written in order from smallest to largest, are therefore (1,2,4). So a(134) is the decimal equivalent of the binary number made by writing four 1's (since the first run in binary 134 is of the shortest length, and the longest run is of length 4), followed by one 0 (since the second run in binary 134 is of the longest length, and the shortest run is of length 1), followed by a run of two 1's (since the third run in binary 134 is of the second largest length, and the second shortest length is also 2), followed finally by a run of four 0's; getting a(134) is the decimal equivalent of binary 11110110000, which is 1968.


(GNU/MIT Scheme:)

(define (A166166 n) (let* ((runlens (binexp->runcount1list n)) (rlsorted (uniq (sort runlens <))) (lenrls (length rlsorted))) (let loop ((rl runlens) (s 0) (b 1)) (cond ((null? rl) s) (else (let* ((nrl (list-ref rlsorted (- lenrls 1 (nthmemq (car rl) rlsorted)))) (p2 (expt 2 nrl))) (loop (cdr rl) (+ (* s p2) (* b (-1+ p2))) (- 1 b))))))))

(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 (uniq lista) (let loop ((lista lista) (z (list))) (cond ((null? lista) (reverse! z)) ((and (pair? z) (equal? (car z) (car lista))) (loop (cdr lista) z)) (else (loop (cdr lista) (cons (car lista) z))))))

(define (nthmemq elem lista) (let loop ((lista lista) (i 0)) (cond ((null? lista) #f) ((eq? (car lista) elem) i) (else (loop (cdr lista) (1+ i))))))


Cf. A056539, A166404.

Sequence in context: A284460 A175949 A166404 * A106452 A254118 A056895

Adjacent sequences:  A166163 A166164 A166165 * A166167 A166168 A166169




Leroy Quet, Oct 08 2009


Sequence extended by Ray Chandler, Oct 18 2009. Scheme-code added, as well as term a(0)=0 prepended (without affecting the offset of the following terms) by Antti Karttunen, Oct 20 2009



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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 22 22:34 EDT 2017. Contains 290952 sequences.