A105726 Involution of nonnegative integers. A deeply recursive variant of A056539.

0, 1, 2, 3, 6, 5, 4, 7, 14, 9, 10, 13, 12, 11, 8, 63, 126, 17, 22, 25, 26, 21, 18, 29, 28, 19, 20, 27, 24, 23, 64, 31, 62, 129, 46, 49, 54, 41, 38, 57, 58, 37, 42, 53, 50, 45, 34, 253, 252, 35, 44, 51, 52, 43, 36, 59, 56, 39, 40, 55, 192, 191, 32, 15, 30, 65, 382, 385, 110

Offset

0,3

Links

Paul Tek, Table of n, a(n) for n = 0..10000

Rémy Sigrist, Scatterplot of (n, a(n)) such that n, a(n) < 2^20

Index entries for sequences that are permutations of the natural numbers

Example

By definition a(0)=0 and a(1)=1.
a(2)=2, as 2 = 10 in binary, thus its run counts are (1 1), which reversed yields the same (1 1), from which we collect a binary number 10, i.e. 2 in decimal.
a(4)=6, as 4 = 100 in binary, thus its run counts are (1 2), which reversed and each element mapped through a itself yields (2 1), which are run counts of binary number 110, i.e. 6 in decimal.
a(16)=126, as 16 = 10000 in binary, thus its run counts are (1 4), which reversed yields (4 1) and a(4)=6 and a(1)=1, thus we find that the run counts (6 1) form a binary 1111110 i.e. 126 in decimal.

Prog

(Scheme): (define (A105726 n) (cond ((< n 2) n) (else (runcount1list->binexp (map A105726 (reverse! (binexp->runcount1list n))))))) (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))))))

Crossrefs

Differs from its "shallow" version A056539 first time at n=15, where A056539(15)=15, but here a(15)=63.

Sequence in context: A106451 A357523 A056539 * A336962 A342102 A284460

Adjacent sequences: A105723 A105724 A105725 * A105727 A105728 A105729

Keyword

nonn,base

Author

Antti Karttunen, Apr 18 2005

Status

approved