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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A129594 Involution of nonnegative integers induced by the conjugation of the partition encoded in the run lengths of binary expansion of n. 18
0, 1, 3, 2, 4, 7, 6, 5, 11, 12, 15, 8, 9, 14, 13, 10, 20, 27, 28, 19, 16, 31, 24, 23, 22, 25, 30, 17, 18, 29, 26, 21, 43, 52, 59, 36, 35, 60, 51, 44, 47, 48, 63, 32, 39, 56, 55, 40, 41, 54, 57, 38, 33, 62, 49, 46, 45, 50, 61, 34, 37, 58, 53, 42, 84, 107, 116, 75, 68, 123 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

This sequence is based on the fact that compositions (i.e. ordered partitions) can be mapped 1-to-1 to partitions by taking the partial sums of the list where one is subtracted from each composant except the first. (See table A227189 where the parts for each partition are listed).

The inverse process, from partitions to compositions, occurs by inserting the first (i.e. smallest) element of a partition sorted into ascending order to the front of the list obtained by adding one to the first differences of the elements.

Compositions map bijectively to nonnegative integers by assigning each run of k consecutive 1's (or 0's) in binary expansion of n with summand k in the composition.

The graph of this sequence is quite interesting.

LINKS

Antti Karttunen, Table of n, a(n) for n = 0..1023

Antti Karttunen, Python-program for computing this and related sequences.

A. Karttunen et al., Run-length encoding, OEIS Wiki.

Index entries for sequences that are permutations of the natural numbers

EXAMPLE

a(8) = 11, as 8 is 1000 in binary, mapping to composition 3+1 (we scan the binary expansion from the least to the most significant end), which maps to partition 3+3, whose conjugate-partition is 2+2+2, yielding composition 2+1+1, which maps to binary 1011, 11 in decimal. a(13) = 14, as 13 is 1101 in binary, mapping to composition 1+1+2, which maps to the partition 1+1+2, whose conjugate-partition is 1+3, yielding composition 1+3, which maps to binary 1110, 14 in decimal. a(11) = 8 and a(14) = 13, as taking the conjugate of a partition is a self-inverse operation.

PROG

(MIT/GNU Scheme)

(define (A129594 n) (if (zero? n) n (ascpart_to_binexp (conjugate-partition (binexp_to_ascpart n)))))

(define (conjugate-partition ascpart) (let loop ((conjpart (list)) (ascpart ascpart)) (cond ((null? ascpart) conjpart) (else (loop (cons (length ascpart) conjpart) (delete-matching-items! (map -1+ ascpart) zero?))))))

(define (binexp_to_ascpart n) (let ((runlist (reverse! (binexp->runcount1list n)))) (PARTSUMS (cons (car runlist) (map -1+ (cdr runlist))))))

(define (ascpart_to_binexp ascpart) (runcount1list->binexp (reverse! (cons (car ascpart) (map 1+ (DIFF ascpart))))))

(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 (DIFF a) (map - (cdr a) (reverse! (cdr (reverse a)))))

(define (PARTSUMS a) (cdr (reverse! (fold-left (lambda (psums n) (cons (+ n (car psums)) psums)) (list 0) a))))

CROSSREFS

a(n) = A075158(A122111(1+A075157(n)) - 1). See A129595 for another kind of encoding of integer partitions.

Sequences related to partitions encoded in this way:

Cf. A227189 (parts of partitions listed on separate rows of the array).

Cf. A005811 (number of parts in the partition).

Cf. A136480 (for n>= 1, the smallest part).

Cf. A227185 (the largest part).

Cf. A227183 (sum of parts).

Cf. A227184 (product of parts).

Note that this permutation maps between A005811 and A227185 as follows: A005811(n) = A227185(a(n)) and vice versa: A227185(n) = A005811(a(n)). On the other hand, it keeps A227183 fixed, as A227183(n) = A227183(a(n)).

Cf. also A226062.

Sequence in context: A212952 A246259 A105025 * A214416 A170950 A276954

Adjacent sequences:  A129591 A129592 A129593 * A129595 A129596 A129597

KEYWORD

nonn,look

AUTHOR

Antti Karttunen, May 01 2007

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 17:30 EST 2017. Contains 295959 sequences.