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

Author

Leroy Quet, Sep 07 2009

Keywords

• base
• nonn
• look

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)

Examples

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

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

Crossrefs

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

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

Programs

Maple

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

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<Kevin Ryde, Oct 07 2020

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

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

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