

A165199


a(0) = 0, and for n>=1, let b(n,m) be the mth digit, reading left to right, of binary n. (b(n, 1) is the most significant binary digit, which is 1.) Then a(n) is such that b(a(n),1)=1; and if b(n,m)=b(n,m1) then b(a(n),m) does not = b(a(n),m1); and if b(n,m) does not = b(n,m1) then b(a(n), m) = b(a(n),m1), for all m where 2 <= m <= number binary digits in n.


5



0, 1, 3, 2, 6, 7, 4, 5, 13, 12, 15, 14, 9, 8, 11, 10, 26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 23, 20, 21, 53, 52, 55, 54, 49, 48, 51, 50, 61, 60, 63, 62, 57, 56, 59, 58, 37, 36, 39, 38, 33, 32, 35, 34, 45, 44, 47, 46, 41, 40, 43, 42, 106, 107, 104, 105, 110, 111, 108
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This is a selfinverse permutation of the positive integers.


LINKS

Antti Karttunen, Table of n, a(n) for n = 0..1023
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers


FORMULA

From Antti Karttunen, Jul 22 2014: (Start)
a(0) = 0, and for n >= 1, a(n) = 2*a(floor(n/2)) + A000035(n+A000523(n)).
As a composition of related permutations:
a(n) = A056539(A129594(n)) = A129594(A056539(n)).
a(n) = A245443(A193231(n)) = A193231(A245444(n)).
a(n) = A075158(A243353(n)1) = A075158((A241909(1+A075157(n)))  1).
(End)
a(n) = A258746(A054429(n)) = A054429(A258746(n)), n > 0.  Yosu Yurramendi, Mar 29 2017


EXAMPLE

12 in binary is 1100. Generating a(12): the leftmost binary digit is 1. In 1100, the 2nd digit from the left equals the first, so the second digit from the left of binary a(12) does not equal the first; so we have 10 as the two leftmost digits in binary a(12). The third digit from the left of binary 12 does not equal the second, so the third digit from the left of binary a(12) equals the second; therefore the leftmost 3 digits of a(12) in binary are 100. And finally, the rightmost digit of binary 12 equals the 3rd from the left, so the rightmost digit of binary a(12) does not equal the 3rd from the left of binary a(12). Therefore a(12) in binary is 1001. And a(12) is the decimal equivalent of this, which is 9.


PROG

(Scheme, with memoizing definecmacro)
(definec (A165199 n) (if (zero? n) n (+ (* 2 (A165199 (floor>exact (/ n 2)))) (A000035 (+ (A000523 n) n)))))
;; Antti Karttunen, Jul 22 2014
(R)
maxrow < 8 # by choice
a < 1
for(m in 0: maxrow) for(k in 0:(2^m1)){
a[2^(m+1) + k] = a[2^(m+1)  1  k] + 2^(m+1)
a[2^(m+1) + 2^m + k] = a[2^(m+1)  1  k] + 2^m
}
(a < c(0, a))
# Yosu Yurramendi, Apr 04 2017


CROSSREFS

Cf. A000035, A000523, A075157, A075158, A241909, A243353, A245443, A245444.
{A001477, A129594, A165199, A056539} form a 4group.
Sequence in context: A154446 A154442 A154445 * A268825 A245812 A268826
Adjacent sequences: A165196 A165197 A165198 * A165200 A165201 A165202


KEYWORD

base,nonn,look


AUTHOR

Leroy Quet, Sep 07 2009


EXTENSIONS

Extended by Ray Chandler, Sep 10 2009
a(0) = 0 prepended by Antti Karttunen, Jul 22 2014


STATUS

approved



