login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 5
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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.

LINKS

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

Rémy Sigrist, PARI program for A294977

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.

EXAMPLE

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

PROG

(PARI) See Links section.

CROSSREFS

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

Sequence in context: A239495 A298210 A045772 * A091256 A003990 A287958

Adjacent sequences:  A294974 A294975 A294976 * A294978 A294979 A294980

KEYWORD

nonn,base,tabl

AUTHOR

Rémy Sigrist, Mar 02 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 04:44 EDT 2019. Contains 324217 sequences. (Running on oeis4.)