A336434 Square array read by descending antidiagonals T(n,k): In the binary expansion of n, reverse the order of the bits in the same position as the active bits in A057716(k).

2, 4, 1, 1, 2, 3, 4, 4, 6, 4, 8, 2, 5, 1, 6, 1, 2, 6, 2, 5, 5, 8, 8, 10, 1, 3, 3, 7, 1, 2, 9, 4, 5, 6, 7, 8, 8, 2, 10, 4, 12, 3, 7, 8, 10, 1, 2, 3, 4, 5, 6, 7, 8, 12, 9, 8, 8, 10, 8, 12, 12, 14, 8, 9, 10, 11, 16, 4, 9, 4, 9, 6, 13, 1, 12, 12, 14, 12

Offset: 1

Author

Davis Smith, Jul 21 2020

Keywords

• nonn
• tabl
• base

Comments

T(n,k) is the swapping of the positions of the bits in n according to the active bits in K, where K = A057716(k). The bit in the same position as the first active bit in K switches positions with the bit in the same position as the last active bit in K, the bit in the same position as the second active bit in K switches with the one in the same as the second to last position, and so on until all have swapped (without repeating).

Any sequence, f, of the form "reverse the order of the a-th, b-th, ... and z-th bits in n" can be expressed as f(n) = T(n,k), where A057716(k) = 2^a + 2^b + ... 2^z. As a result, this operation combines 1 or more bit-swapping operations, which could be useful for bit-manipulation in computer programming.

Examples

			The binary expansion of 18 is 10010_2 and the active bits in the binary expansion of A057716(22) = 27 = 11011_2 are 0, 1, 3, and 4. So, to get T(18,22), we swap the 0th and 4th bits and then the 1st and 3rd bits, which gives us T(18,22) = 9.
Square array T(n,k) begins:
  \k   1   2   3   4   5   6   7   8   9  10 ...
  n\
   1|  2   4   1   4   8   1   8   1   8   1 ...
   2|  1   2   4   2   2   8   2   2   2   8 ...
   3|  3   6   5   6  10   9  10   3  10   9 ...
   4|  4   1   2   1   4   4   4   8   4   4 ...
   5|  6   5   3   5  12   5  12   9  12   5 ...
   6|  5   3   6   3   6  12   6  10   6  12 ...
   7|  7   7   7   7  14  13  14  11  14  13 ...
   8|  8   8   8   8   1   2   1   4   1   2 ...
   9| 10  12   9  12   9   3   9   5   9   3 ...
  10|  9  10  12  10   3  10   3   6   3  10 ...
		

Links

• Davis Smith, Table of n, a(n) for n = 1..5050; the first 100 antidiagonals of the array
• S. E. Anderson, Bit Twiddling Hacks.

Crossrefs

Cf. A000120, A003987, A030101, A030308, A057716, A059893, A070939, A080412 (column k=1), A133457.

Programs

PARI

A336434(n,k)={my(K=k+#binary(k+#binary(k)), P=select(Z->bittest(K,Z),[0..#binary(K)-1]), Q1=P[1..floor(#P/2)],Q2=Vecrev(P)[1..floor(#P/2)], Sum=vecsum(apply(p->if(bittest(n,Q1[p])!=bittest(n,Q2[p]), bitor(shift(1,Q1[p]),shift(1,Q2[p]))), [1..floor(#P/2)])));bitxor(n,Sum)}

Formula

T(n,k) = A003987(n, Sum_{m=1..floor(M/2)} A003987(A030308(n,A133457(K,m)), A030308(n,A133457(K,M - (m - 1))))* (2^A133457(K,m) + 2^A133457(K,M - (m - 1)))), where K = A057716(k) and M = A000120(A057716(k)).

When A057716(k) = 2^A070939(n) - 1, T(n,k) = A030101(n).

When A057716(k) = 2^(A070939(n) - 1) - 1, T(n,k) = A059893(n).