|
%I #87 Mar 03 2018 09:48:28
%S 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,
%T 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,
%U 19,8,23,6,23,8,19,10,11,12,11,26,9,40,14,14,40,9,26
%N 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.
%C When computing T(n, k), we have three situations:
%C - 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,
%C - 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,
%C - 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.
%H Rémy Sigrist, <a href="/A294977/a294977.gp.txt">PARI program for A294977</a>
%F T(n, n) = n.
%F T(n, 1) = n.
%F T(n, k) = T(k, n).
%F T(T(n, k), k) = T(n, k) (for any fixed n > 0, the function k -> T(n, k) is a projection).
%F A165819(n) = T(n, 2*n-1).
%F A165820(n) = T(n, n^2).
%F A165821(n) = T(n, A000040(n)).
%F A165822(n) = T(n, A000045(n)).
%F T(n, k) >= n with equality iff the binary representation of k appears in the binary representation of n.
%F T(n, k) >= max(n, k).
%F T(n, k) <= min(A163621(n, k), A163621(k, n)) with equality iff the binary representations of n and of k do not overlap.
%e Array T(n, k) begins (in decimal):
%e n\k| 1 2 3 4 5 6 7 8 9 10 11 12
%e ---+------------------------------------------------------------
%e 1| 1 2 3 4 5 6 7 8 9 10 11 12
%e 2| 2 2 6 4 5 6 14 8 9 10 11 12
%e 3| 3 6 3 12 11 6 7 24 19 26 11 12
%e 4| 4 4 12 4 20 12 28 8 9 20 44 12
%e 5| 5 5 11 20 5 13 23 40 37 10 11 44
%e 6| 6 6 6 12 13 6 14 24 25 26 22 12
%e 7| 7 14 7 28 23 14 7 56 39 58 23 28
%e 8| 8 8 24 8 40 24 56 8 72 40 88 24
%e Array T(n, k) begins (in binary):
%e n\k| 1 10 11 100 101 110 111 1000 1001 1010
%e ----+---------------------------------------------------------------------------
%e 1| 1 10 11 100 101 110 111 1000 1001 1010
%e 10| 10 10 110 100 101 110 1110 1000 1001 1010
%e 11| 11 110 11 1100 1011 110 111 11000 10011 11010
%e 100| 100 100 1100 100 10100 1100 11100 1000 1001 10100
%e 101| 101 101 1011 10100 101 1101 10111 101000 100101 1010
%e 110| 110 110 110 1100 1101 110 1110 11000 11001 11010
%e 111| 111 1110 111 11100 10111 1110 111 111000 100111 111010
%e 1000| 1000 1000 11000 1000 101000 11000 111000 1000 1001000 101000
%o (PARI) See Links section.
%Y Cf. A000040, A000045, A163621, A165819, A165820, A165821, A165822.
%K nonn,base,tabl
%O 1,2
%A _Rémy Sigrist_, Mar 02 2018
|
