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,5

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).

Links

Table of n, a(n) for n=0..76.

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.

Example

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  ...

Prog

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

Crossrefs

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

Sequence in context: A214776 A369415 A317575 * A146326 A276727 A267617

Adjacent sequences: A295650 A295651 A295652 * A295654 A295655 A295656

Keyword

nonn,tabl,base

Author

Rémy Sigrist, Nov 25 2017

Status

approved