|
%I #19 May 05 2016 18:06:36
%S 1,3,6,10,14,18,23,29,36,44,52,60,68,76
%N Maximal number of 1's in an n X n {0,1} Toeplitz matrix with property that no four 1's form a square with sides parallel to the edges of the matrix.
%C Label the entries in the left edge and top row (reading from the bottom left to the top right) with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where the matrix contains 1's. Then the matrix has the no-subsquare property iff S contains no three-term arithmetic progression.
%e n, a(n), example of optimal S:
%e 1, 1, [1]
%e 2, 3, [1, 2]
%e 3, 6, [1, 3, 4]
%e 4, 10, [1, 2, 4, 5]
%e 5, 14, [2, 3, 5, 6]
%e 6, 18, [3, 4, 6, 7]
%e 7, 23, [1, 5, 7, 8, 10]
%e 8, 29, [1, 2, 7, 8, 10, 11]
%e 9, 36, [1, 3, 4, 9, 10, 12, 13]
%e 10, 44, [1, 2, 4, 5, 10, 11, 13, 14]
%e 11, 52, [2, 3, 5, 6, 11, 12, 14, 15]
%e 12, 60, [3, 4, 6, 7, 12, 13, 15, 16]
%e 13, 68, [4, 5, 7, 8, 13, 14, 16, 17]
%e 14, 76, [5, 6, 8, 9, 14, 15, 17, 18]
%e ...
%e For example, the line 5, 14, [2, 3, 5, 6] corresponds to the Toeplitz matrix
%e 11000
%e 01100
%e 10110
%e 11011
%e 01101
%e and the value a(5) = 14.
%Y This is a lower bound on A227133.
%Y See A269746 for the analogous sequence for a triangular grid.
%Y Cf. A003002.
%K nonn,more
%O 1,2
%A _Warren D. Smith_ and _N. J. A. Sloane_, Mar 19 2016
%E a(14) from _N. J. A. Sloane_, May 05 2016
|
