|
| |
|
|
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.
|
|
6
|
|
|
|
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 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.
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
|
a(0) = 0, and for n >= 1, a(n) = 2*a(floor(n/2)) + A000035(n+A000523(n)).
As a composition of related permutations:
(End)
|
|
|
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)):
|
|
|
PROG
|
(Scheme, with memoizing definec-macro)
(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))
(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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
