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