A227308 -id:A227308 - cp's OEIS frontend

A227133 Given a square grid with side n consisting of n^2 cells (or points), a(n) is the maximum number of points that can be painted so that no four of the painted ones form a square with sides parallel to the grid.

1, 3, 7, 12, 17, 24, 32, 41, 51, 61, 73, 85, 98

Offset: 1

Heinrich Ludwig, Jul 06 2013

a(1) through a(9) were found by an exhaustive computational search for all solutions. This sequence is complementary to A152125: A152125(n) + A227133(n) = n^2.
A064194(n) is a lower bound on a(n) (see the comments in A047999). - N. J. A. Sloane, Jan 18 2016
a(11) >= 71 (by extending the n=10 solution towards the southeast). - N. J. A. Sloane, Feb 12 2016
a(11) >= 73, a(12) >= 85, a(13) >= 98, a(14) >= 112, a(15) >= 127, a(16) >= 142 (see links). These lower bounds were obtained using tabu search and simulated annealing via the Ascension Optimization Framework. - Peter Karpov, Feb 22 2016; corrected Jun 04 2016
Note that n is the number of cells along each edge of the grid. The case n=1 corresponds to a single square cell, n=2 to a 2 X 2 array of four square cells. The standard chessboard is the case n=8. It is easy to get confused and to think of the case n=2 as a 3 X 3 grid of dots (the vertices of the squares in the grid). Don't think like that! - N. J. A. Sloane, Apr 03 2016
a(12) = 85 and a(13) = 98 were obtained with a MIP model, solved with Gurobi in 141 days on 32 cores. - Simon Felix, Nov 22 2019
a(17) >= 158, a(18) >= 174, a(19) >= 192, a(20) >= 210. These lower bounds were obtained using simulated annealing. - Dmitry Kamenetsky, Dec 07 2024

			n=9. A maximum of a(9) = 51 points (X) of 81 can be painted while 30 (.) must be left unpainted. The following 9 X 9 square is an example:
     . X X X X X . X .
     X . X . . X X X X
     X X . . X . X . X
     X . . X X X X . .
     X X X . X . . X X
     X . X X X . . . X
     . X X . . X X . X
     X X . X . X . X X
     . X X X X X X X .
Here there is no subsquare with all vertices = X and having sides parallel to the axes.

Dmitry Kamenetsky, Best known solutions for n = 17..20
Peter Karpov, InvMem, Item 20 [Link added by _N. J. A. Sloane_, Feb 24 2016]
Peter Karpov, Ascension Optimization Framework [Link added by _N. J. A. Sloane_, Feb 24 2016]
Peter Karpov, Best configurations known for n = 11..16
Giovanni Resta, Illustration of a(2)-a(10)
Giovanni Resta, Individual illustration for a(8)

Cf. A152125 (the complementary problem), A000330, A240443 (when all squares must be avoided, not just those aligned with the grid).
See also A047999, A064194.
For a lower bound see A269745.
For analogs that avoid triangles in the square grid see A271906, A271907.
For an equilateral triangular grid analog see A227308 (and A227116).
For the three-dimensional analog see A268239.

a[n_] := Block[{m, qq, nv = n^2, ne}, qq = Flatten[1 + Table[n*x + y + {0, s, s*n, s*(n + 1)}, {x, 0, n-2}, {y, 0, n-2}, {s, Min[n-x, n-y] -1}], 2]; ne = Length@qq; m = Table[0, {ne}, {nv}]; Do[m[[i, qq[[i]]]] = 1, {i, ne}]; Total@ Quiet@ LinearProgramming[Table[-1, {nv}], m, Table[{3, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; Array[a,8] (* Giovanni Resta, Jul 14 2013 *)

a(10) from Giovanni Resta, Jul 14 2013
a(11) from Paul Tabatabai using integer programming, Sep 25 2018
a(12)-a(13) from Simon Felix using integer programming, Nov 22 2019

A227116 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be removed from the grid, so that, if 3 of the remaining points are chosen, they do not form an equilateral triangle with sides parallel to the grid.

Original entry on oeis.org

0, 1, 2, 4, 7, 9, 14, 18, 23, 29, 36, 44, 52, 61, 71

Offset: 1

Heinrich Ludwig, Jul 01 2013

This is the complementary problem to A227308.

Numbers found by an exhaustive computational search for all solutions (see history).

			n = 11: at least a(11) = 36 points (.) out of the 66 have to be removed, leaving 30 (X) behind:
              .
             X X
            X . X
           X . . X
          X . . . X
         X . . . . X
        . X X . X X .
       . X . X X . X .
      . . X X . X X . .
     X . . . . . . . . X
    . X X X . . . X X X .
There is no equilateral subtriangle with all vertices = X and sides parallel to the whole triangle.

Heinrich Ludwig, Illustration of a(2)..a(15)
Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Cf. A227308, A152125, A227133

a(n) + A227308(n) = n(n+1)/2.

Added a(12), a(13), Heinrich Ludwig, Sep 02 2013
Added a(14), Giovanni Resta, Sep 19 2013
a(15) from Heinrich Ludwig, Oct 27 2013

A240443 Maximal number of points that can be placed on an n X n square grid so that no four of them are vertices of a square with any orientation.

Original entry on oeis.org

1, 3, 6, 10, 15, 21, 27, 34, 42, 50

Offset: 1

Heinrich Ludwig, May 07 2014

a(10) >= 50, a(11) >= 58. - Robert Israel, Apr 08 2016
a(12) >= 67. - Robert Israel, Apr 12 2016
a(13) >= 76, a(14) >= 86, a(15) >= 95, a(16) >= 106. - Peter Karpov, Jun 04 2016

			On a 9 X 9 grid a maximum of 42 points (x) can be placed so that no four of them are vertices of an (arbitrarily oriented) square. An example:
     x x . . x . x . x
     . x . . x x x x .
     x x x . . x . . x
     x . x x x . . x x
     . . . . x x . . .
     . x . x x . . . x
     x x x . x . . . x
     x . x . . . . x x
     x . . x x x x x .

Robert Israel, Illustration showing a(10) >= 50
Robert Israel, Illustration showing a(11) >= 58
Robert Israel, Illustration showing a(12) >= 67
Peter Karpov, Maximal density subsquare-free arrangements / #Optimization #OpenProblem / 2016.02.22, giving lower bounds for a(1)-a(16).
Peter Karpov, Best configurations known for n = 13 .. 16
Giovanni Resta, Illustration of a(8) and a(9)
Dominik Stadlthanner, Python program
Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Cf. A227133 (where we are concerned only with subsquares oriented parallel to the sides of the grid), A240114, A227308, A240444.

a(10) from Dominik Stadlthanner using integer programming, Apr 08 2020

A240114 Maximal number of points that can be placed on a triangular grid of side n so that no three of them are vertices of an equilateral triangle in any orientation.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 14, 17, 20, 22, 25, 28, 31, 34

Offset: 1

Heinrich Ludwig, Apr 01 2014

Placing points on a triangular grid of side n, there are A000332(n + 3) triangles to be avoided.
The number k(n) of maximal solutions (reflections and rotations not counted) varies greatly: k(n) = 1, 1, 1, 1, 1, 3, 13, 129, 15, 2, 63, 3, 20, 1, ...
From Elijah Beregovsky, Nov 20 2022: (Start)
a(n) >= 3n-11.
This lower bound is given by the construction seen in the example section.
Conjecture: for n >= 11, a(n) = 3n-11. (End)

			On a triangular grid of side 15, 34 points (X) can be placed so that no three of them form an equilateral triangle, regardless of its orientation.
                   X
                  . .
                 . X .
                X . X .
               . X . . X
              X . . . X .
             . X . . . . X
            X . . . . . X .
           . X . . . . . . X
          X . . . . . . . X .
         . X . . . . . . . . X
        X . . . . . . . . . X .
       . X . . . . . . . . . . X
      . . . . . . . . . . . . X .
     . . X X X X X X X X X X X . .

Cf. A227308, A227116, A227133, A000332.

a(14) from Heinrich Ludwig, Jun 20 2014

a(15) from Heinrich Ludwig, Jun 21 2016

A243207 Triangle T(n, k) = Numbers of inequivalent (mod D_3) ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 2, 4, 3, 1, 3, 10, 20, 25, 11, 3, 4, 22, 77, 186, 266, 221, 86, 14, 5, 41, 223, 881, 2344, 4238, 4885, 3451, 1296, 220, 7, 1, 7, 72, 552, 3146, 12907, 38640, 83107, 126701, 132236, 90214, 37128, 8235, 775, 24, 8, 116, 1196, 9264, 53307, 232861, 773930

Offset: 1

Heinrich Ludwig, Jun 01 2014

The triangle T(n, k) is irregularly shaped: 1 <= k <= A227308(n). First row corresponds to n = 1.

The maximal number of points that can be placed on a triangular grid of side n so that no three of them form an equilateral triangle with sides parallel to the grid is given by A227308(n).

			The triangle begins:
  1;
  1,  1;
  2,  4,   3,   1;
  3, 10,  20,  25,   11,    3;
  4, 22,  77, 186,  266,  221,   86,   14;
  5, 41, 223, 881, 2344, 4238, 4885, 3451, 1296, 220, 7, 1;
  ...
There is T(6, 12) = 1 way to place 12 points (x) on the grid obeying the rule in the definition of the sequence:
           .
          x x
         x . x
        x . . x
       x . . . x
      . x x x x .

Heinrich Ludwig, Table of n, a(n) for n = 1..153

Cf. A227308, A243211, A239572, A234247, A231655, A243141, A001399 (column 1), A227327 (column 2), A243208 (column 3), A243209 (column 4), A243210 (column 5).

A243211 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 6, 15, 15, 3, 1, 10, 45, 107, 128, 63, 10, 1, 15, 105, 428, 1062, 1566, 1276, 507, 69, 1, 21, 210, 1282, 5160, 13971, 25191, 29235, 20508, 7747, 1251, 42, 1, 1, 28, 378, 3198, 18591, 77124, 231090, 498097, 759117, 792942, 540361, 222597, 49053

Offset: 1

Heinrich Ludwig, Jun 09 2014

The triangle T(n, k) is irregularly shaped: 0 <= k <= A227308(n). First row corresponds to n = 1.

The maximal number of points that can be placed on a triangular grid of side n so that no three of them form an equilateral triangle with sides parallel to the grid is given by A227308(n).

			The triangle begins:
  1,  1;
  1,  3,   3;
  1,  6,  15,   15,    3;
  1, 10,  45,  107,  128,    63,    10,
  1, 15, 105,  428, 1062,  1566,  1276,   507,    69,
  1, 21, 210, 1282, 5160, 13971, 25191, 29235, 20508, 7747, 1251, 42, 1;
  ...
There is T(6, 12) = 1 way to place 12 points (x) on the grid obeying the rule in the definition of the sequence:
           .
          x x
         x . x
        x . . x
       x . . . x
      . x x x x .

Heinrich Ludwig, Table of n, a(n) for n = 1..165

Cf. A227308, A243207, A084546, A234251, A239567, A240439, A194136, A000217 (column 2), A050534 (column 3), A243212 (column 4), A243213 (column 5), A243214 (column 6).

A269746 Maximal number of 1's in an equilateral triangle of 0's and 1's with n points on each side, the entries being constant on vertical lines, with property that no three 1's form a triangle with sides parallel to the edges of the triangle.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 13, 16, 20, 24, 28, 32, 36, 40

Offset: 1

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

The triangle is oriented with apex at the top and horizontal base.

Label the entries in the top left and right edges with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where these edges contains 1's. Then the matrix has the no-subtriangle property iff S contains no three-term arithmetic progression.

			n, a(n), example of optimal S:
1, 1, [1]
2, 2, [1, 2]
3, 4, [1, 3, 4]
4, 6, [1, 2, 4, 5]
5, 8, [2, 3, 5, 6]
6, 10, [3, 4, 6, 7]
7, 13, [1, 5, 7, 8, 10]
8, 16, [1, 2, 7, 8, 10, 11]
9, 20, [1, 3, 4, 9, 10, 12, 13]
10, 24, [1, 2, 4, 5, 10, 11, 13, 14]
11, 28, [2, 3, 5, 6, 11, 12, 14, 15]
12, 32, [3, 4, 6, 7, 12, 13, 15, 16]
13, 36, [4, 5, 7, 8, 13, 14, 16, 17]
14, 40, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 8, [2, 3, 5, 6] corresponds to the triangle
....1....
...0.1...
..1.1.0..
.1.0.1.0.
0.1.1.0.0
and the value a(5) = 8.
It is a plausible conjecture that any optimal solution S here is also an optimal solution to the square grid version in A269745, and vice versa. (The square grid being obtained by reflecting the triangle in its base.)

This is a lower bound on A227308.

Cf. A003002, A269745.

cp's OEIS Frontend

A227133 Given a square grid with side n consisting of n^2 cells (or points), a(n) is the maximum number of points that can be painted so that no four of the painted ones form a square with sides parallel to the grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A227116 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be removed from the grid, so that, if 3 of the remaining points are chosen, they do not form an equilateral triangle with sides parallel to the grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A240443 Maximal number of points that can be placed on an n X n square grid so that no four of them are vertices of a square with any orientation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A240114 Maximal number of points that can be placed on a triangular grid of side n so that no three of them are vertices of an equilateral triangle in any orientation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A243207 Triangle T(n, k) = Numbers of inequivalent (mod D_3) ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A243211 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A269746 Maximal number of 1's in an equilateral triangle of 0's and 1's with n points on each side, the entries being constant on vertical lines, with property that no three 1's form a triangle with sides parallel to the edges of the triangle.

Views

Author

Keywords

Comments

Examples

Crossrefs