A294977 Square array T(n, k) read by antidiagonals, n > 0 and k > 0: T(n, k) is the smallest positive integer that, when written in binary, contains both binary n and binary k as substrings.

1, 2, 2, 3, 2, 3, 4, 6, 6, 4, 5, 4, 3, 4, 5, 6, 5, 12, 12, 5, 6, 7, 6, 11, 4, 11, 6, 7, 8, 14, 6, 20, 20, 6, 14, 8, 9, 8, 7, 12, 5, 12, 7, 8, 9, 10, 9, 24, 28, 13, 13, 28, 24, 9, 10, 11, 10, 19, 8, 23, 6, 23, 8, 19, 10, 11, 12, 11, 26, 9, 40, 14, 14, 40, 9, 26

Offset: 1

Author

Rémy Sigrist, Mar 02 2018

Keywords

• nonn
• base
• tabl

Comments

When computing T(n, k), we have three situations:

- the binary representation of n appears in the binary representation of k or vice versa; then T(n, k) = max(n, k); for example T(1, 2) = 2,

- otherwise a strict suffix of the binary representation of n equals a strict prefix of the binary representation of k or vice versa; then max(n, k) < T(n, k) < min(A163621(n, k), A163621(k, n)); for example T(2, 3) = 6,

- otherwise the binary representations of n and of k do not overlap; then T(n, k) = min(A163621(n, k), A163621(k, n)); for example T(10, 12) = 172.

Examples

			Array T(n, k) begins (in decimal):
  n\k|    1    2    3    4    5    6    7    8    9   10   11   12
  ---+------------------------------------------------------------
    1|    1    2    3    4    5    6    7    8    9   10   11   12
    2|    2    2    6    4    5    6   14    8    9   10   11   12
    3|    3    6    3   12   11    6    7   24   19   26   11   12
    4|    4    4   12    4   20   12   28    8    9   20   44   12
    5|    5    5   11   20    5   13   23   40   37   10   11   44
    6|    6    6    6   12   13    6   14   24   25   26   22   12
    7|    7   14    7   28   23   14    7   56   39   58   23   28
    8|    8    8   24    8   40   24   56    8   72   40   88   24
Array T(n, k) begins (in binary):
   n\k|     1    10     11    100     101    110      111    1000     1001    1010
  ----+---------------------------------------------------------------------------
     1|     1    10     11    100     101    110      111    1000     1001    1010
    10|    10    10    110    100     101    110     1110    1000     1001    1010
    11|    11   110     11   1100    1011    110      111   11000    10011   11010
   100|   100   100   1100    100   10100   1100    11100    1000     1001   10100
   101|   101   101   1011  10100     101   1101    10111  101000   100101    1010
   110|   110   110    110   1100    1101    110     1110   11000    11001   11010
   111|   111  1110    111  11100   10111   1110      111  111000   100111  111010
  1000|  1000  1000  11000   1000  101000  11000   111000    1000  1001000  101000
		

Links

• Rémy Sigrist, PARI program for A294977

Crossrefs

Cf. A000040, A000045, A163621, A165819, A165820, A165821, A165822.

Programs

PARI

See Links section.

Formula

T(n, n) = n.

T(n, 1) = n.

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

T(T(n, k), k) = T(n, k) (for any fixed n > 0, the function k -> T(n, k) is a projection).

A165819(n) = T(n, 2*n-1).

A165820(n) = T(n, n^2).

A165821(n) = T(n, A000040(n)).

A165822(n) = T(n, A000045(n)).

T(n, k) >= n with equality iff the binary representation of k appears in the binary representation of n.

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

T(n, k) <= min(A163621(n, k), A163621(k, n)) with equality iff the binary representations of n and of k do not overlap.