A165199 a(n) is obtained by flipping every second bit in the binary representation of n starting at the second-most significant bit and on downwards.

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

Offset

0,3

Comments

This is a self-inverse permutation of the positive integers.

Old name was: a(0) = 0, and for n>=1, let b(n,m) be the m-th 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,m-1) then b(a(n),m) does not = b(a(n),m-1); and if b(n,m) does not = b(n,m-1) then b(a(n), m) = b(a(n),m-1), for all m where 2 <= m <= number binary digits in n.

From Emeric Deutsch, Oct 06 2020: (Start)

a(n) is the index of the composition that is the conjugate of the composition with index n.

The index of a composition is defined to be the positive integer whose binary form has run-lengths (i.e., runs of 1's, runs of 0's, etc. from left to right) equal to the parts of the composition. Example: the composition 1,1,3,1 has index 46 since the binary form of 46 is 101110.

a(18) = 24. Indeed, since the binary form of 18 is 10010, the composition with index 18 is 1,2,1,1 (the run-lengths of 10010); the conjugate of 1,2,1,1 is 2,3 and so the binary form of a(18) is 11000; consequently, a(18) = 24. (End)

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

a(12) = 9 because 12 = 1100_2 and 1100_2 XOR 0101_2 = 1001_2 = 9.

Maple

a:= n-> Bits[Xor](n, iquo(2^(1+ilog2(n)), 3)):
seq(a(n), n=0..100);  # Alois P. Heinz, Oct 07 2020

Prog

(Scheme, with memoizing definec-macro)
(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^m-1)){
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
(PARI) for(k=0, 67, my(b(n)=vector(#digits(n, 2), i, !(i%2))); print1(bitxor(k, fromdigits(b(k), 2)), ", ")) \\ Hugo Pfoertner, Oct 07 2020
(PARI) a(n) = if(n, bitxor(n, 2<<logint(n, 2)\3), 0); \\ Kevin Ryde, Oct 07 2020

Crossrefs

Cf. A000035, A000523, A075157, A075158, A241909, A243353, A245443, A245444.

{A001477, A129594, A165199, A056539} form a 4-group.

Sequence in context: A371961 A354225 A154445 * A371962 A268825 A245812

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

New name from Kevin Ryde, Oct 07 2020

Status

approved