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

Author

Antti Karttunen, Apr 18 2005

Keywords

• nonn
• look
• base

Comments

Keyword "look" refers especially to the scatterplot image by Rémy Sigrist, which has a strong resemblance to an FPGA architecture diagram. - Antti Karttunen, Dec 25 2024

Examples

			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.
		

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 related to binary expansion of n
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

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

Programs

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))))))