|
| |
|
|
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.)
|
|
3
|
|
|
|
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 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.
|
|
|
LINKS
|
|
|
|
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 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.
|
|
|
PROG
|
(MIT/GNU 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))))))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
base,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
