A295653 Square array T(n, k), n >= 0, k >= 0, read by antidiagonals upwards: T(n, k) = the (k+1)-th nonnegative number m such that n AND m = 0 (where AND denotes the bitwise AND operator).

0, 0, 1, 0, 2, 2, 0, 1, 4, 3, 0, 4, 4, 6, 4, 0, 1, 8, 5, 8, 5, 0, 2, 2, 12, 8, 10, 6, 0, 1, 8, 3, 16, 9, 12, 7, 0, 8, 8, 10, 8, 20, 12, 14, 8, 0, 1, 16, 9, 16, 9, 24, 13, 16, 9, 0, 2, 2, 24, 16, 18, 10, 28, 16, 18, 10, 0, 1, 4, 3, 32, 17, 24, 11, 32, 17, 20

Offset: 0

Author

Rémy Sigrist, Nov 25 2017

Keywords

• nonn
• tabl
• base

Comments

This sequence has similarities with A126572: here we check for common bits in binary representations, there for common primes in prime factorizations.

For any n >= 0 and k >= 0:

- T(0, k) = k,

- T(1, k) = 2*k,

- T(2, k) = A042948(k),

- T(3, k) = 4*k,

- T(4, k) = A047476(k),

- T(5, k) = A047467(k),

- T(2^n - 1, k) = 2^n * k,

- T(n, 0) = 0,

- T(n, 1) = A006519(n+1),

- T(n, k + 2^A080791(n)) = T(n, k) + 2^A029837(n+1) (i.e. each row is linear),

- A000120(T(n, k)) = A000120(k).

Examples

			Square array begins:
n\k  0   1   2   3   4   5   6   7   8   9  ...
0:   0   1   2   3   4   5   6   7   8   9  ...
1:   0   2   4   6   8  10  12  14  16  18  ...
2:   0   1   4   5   8   9  12  13  16  17  ...
3:   0   4   8  12  16  20  24  28  32  36  ...
4:   0   1   2   3   8   9  10  11  16  17  ...
5:   0   2   8  10  16  18  24  26  32  34  ...
6:   0   1   8   9  16  17  24  25  32  33  ...
7:   0   8  16  24  32  40  48  56  64  72  ...
8:   0   1   2   3   4   5   6   7  16  17  ...
9:   0   2   4   6  16  18  20  22  32  34  ...
		

Crossrefs

Cf. A000120, A006519, A029837, A042948, A047467, A047476, A080791, A126572.

Programs

PARI

T(n,k) = if (n==0, k, n%2, 2*T(n\2,k), 2*T(n\2,k\2) + (k%2))

Formula

For any n >= 0 and k >= 0:

- T(0, k) = k,

- T(2*n + 1, k) = 2*T(n, k),

- T(2*n, 2*k) = 2*T(n, k),

- T(2*n, 2*k + 1) = 2*T(n, k) + 1.

For any n >= 0, T(n, k) ~ 2^A000120(n) * k as k tends to infinity.