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

FORMULA

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

KEYWORD

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