A269745 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.

1, 3, 6, 10, 14, 18, 23, 29, 36, 44, 52, 60, 68, 76

Offset: 1

Author

Warren D. Smith and N. J. A. Sloane, Mar 19 2016

Keywords

• nonn
• more

Comments

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.

Examples

			n, a(n), example of optimal S:
1, 1, [1]
2, 3, [1, 2]
3, 6, [1, 3, 4]
4, 10, [1, 2, 4, 5]
5, 14, [2, 3, 5, 6]
6, 18, [3, 4, 6, 7]
7, 23, [1, 5, 7, 8, 10]
8, 29, [1, 2, 7, 8, 10, 11]
9, 36, [1, 3, 4, 9, 10, 12, 13]
10, 44, [1, 2, 4, 5, 10, 11, 13, 14]
11, 52, [2, 3, 5, 6, 11, 12, 14, 15]
12, 60, [3, 4, 6, 7, 12, 13, 15, 16]
13, 68, [4, 5, 7, 8, 13, 14, 16, 17]
14, 76, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 14, [2, 3, 5, 6] corresponds to the Toeplitz matrix
11000
01100
10110
11011
01101
and the value a(5) = 14.
		

Crossrefs

This is a lower bound on A227133.

See A269746 for the analogous sequence for a triangular grid.

Cf. A003002.

Extensions

a(14) from N. J. A. Sloane, May 05 2016