

A166166


Write n in binary with each run (of either digit b) of the kth longest distinct runlength replaced with a run of digit b of a length equal to that of the kth shortest distinct runlength. 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)



OFFSET

0,3


COMMENTS

This sequence is a selfinverse permutation of the positive integers.
Clarification of definition: Let b(k) be the kth largest distinct runlength (considering both runs of 0's and of 1's) in binary n. Let r be the number of distinct runlengths 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+1k). 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.


LINKS

A. Karttunen, Table of n, a(n) for n = 0..65535
Index entries for sequences that are permutations of the natural numbers


EXAMPLE

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 runlengths, 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.


PROG

(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 (listref 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) (prevbit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prevbit) (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))))))


CROSSREFS

Cf. A056539, A166404.
Sequence in context: A284460 A175949 A166404 * A106452 A254118 A056895
Adjacent sequences: A166163 A166164 A166165 * A166167 A166168 A166169


KEYWORD

base,nonn


AUTHOR

Leroy Quet, Oct 08 2009


EXTENSIONS

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


STATUS

approved



