A342639 Square array T(n, k), n, k >= 0, read by antidiagonals; T(n, k) = g(f(n) + f(k)) where g maps the complement, say s, of a finite set of nonnegative integers to the value Sum_{e >= 0 not in s} 2^e, f is the inverse of g, and "+" denotes the Minkowski sum.

0, 1, 1, 0, 3, 0, 3, 1, 1, 3, 0, 7, 2, 7, 0, 1, 1, 3, 3, 1, 1, 0, 3, 0, 15, 0, 3, 0, 7, 1, 5, 3, 3, 5, 1, 7, 0, 15, 2, 7, 0, 7, 2, 15, 0, 1, 1, 7, 3, 1, 1, 3, 7, 1, 1, 0, 3, 0, 31, 4, 11, 4, 31, 0, 3, 0, 3, 1, 1, 3, 7, 5, 5, 7, 3, 1, 1, 3, 0, 7, 2, 7, 0, 15, 6, 15, 0, 7, 2, 7, 0

Offset: 0

Author

Rémy Sigrist, Mar 17 2021

Keywords

• nonn
• tabl
• base

Comments

In other words:

- we consider the set S of sets s of nonnegative integers whose complement is finite,

- the function g encodes the "missing integers" in binary:

g(A001477 \ {1, 4}) = 2^1 + 2^4 = 18

- the function f is the inverse of g:

f(42) = f(2^1 + 2^3 + 2^5) = A001477 \ {1, 3, 5},

- the Minkowski sum of two sets, say U and V, is the set of sums u+v where u belongs to U and v belongs to V,

- the Minkowski sum is stable over S,

- and T provides an encoding for this operation.

This sequence has connections with A067138; here we consider complements of finite sets of nonnegative integers, there finite sets of nonnegative integers.

Examples

			Array T(n, k) begins:
  n\k|   0   1   2   3   4   5   6    7   8   9  10  11  12  13  14   15
  ---+------------------------------------------------------------------
    0|   0   1   0   3   0   1   0    7   0   1   0   3   0   1   0   15
    1|   1   3   1   7   1   3   1   15   1   3   1   7   1   3   1   31
    2|   0   1   2   3   0   5   2    7   0   1   2  11   0   5   2   15
    3|   3   7   3  15   3   7   3   31   3   7   3  15   3   7   3   63
    4|   0   1   0   3   0   1   4    7   0   1   0   3   0   9   4   15
    5|   1   3   5   7   1  11   5   15   1   3   5  23   1  11   5   31
    6|   0   1   2   3   4   5   6    7   0   9   2  11   4  13   6   15
    7|   7  15   7  31   7  15   7   63   7  15   7  31   7  15   7  127
    8|   0   1   0   3   0   1   0    7   0   1   0   3   0   1   8   15
    9|   1   3   1   7   1   3   9   15   1   3   1   7   1  19   9   31
   10|   0   1   2   3   0   5   2    7   0   1  10  11   0   5  10   15
   11|   3   7  11  15   3  23  11   31   3   7  11  47   3  23  11   63
   12|   0   1   0   3   0   1   4    7   0   1   0   3   8   9  12   15
   13|   1   3   5   7   9  11  13   15   1  19   5  23   9  27  13   31
   14|   0   1   2   3   4   5   6    7   8   9  10  11  12  13  14   15
   15|  15  31  15  63  15  31  15  127  15  31  15  63  15  31  15  255
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10010
• Wikipedia, Minkowski addition

Crossrefs

Cf. A038712, A067138, A133457, A135481, A342640, A342641, A342642.

Programs

PARI

T(n,k) = { my (v=0); for (x=0, #binary(n)+#binary(k), my (f=0); for (y=0, x, if (!bittest(n,y) && !bittest(k,x-y), f=1; break)); if (!f, v+=2^x)); return (v) }

Formula

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

T(m, T(n, k)) = T(T(m, n), k).

T(n, 0) = A135481(n).

T(n, 1) = A038712(n+1).

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

T(n, n) = A342640(n).