cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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.

Original entry on oeis.org

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

Views

Author

Heinrich Ludwig, Jul 06 2013

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

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.

Programs

  • Mathematica
    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 *)

Extensions

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

A271906 Size of the largest subset S of the points of an n X n square grid such that no three of the points of S form a right isosceles triangle.

Original entry on oeis.org

1, 2, 4, 6, 9, 11, 14, 17, 20, 23, 26
Offset: 1

Views

Author

Giovanni Resta and N. J. A. Sloane, Apr 22 2016

Keywords

Comments

S must not contain 3 points A,B,C such that angle ABC = 90 degrees and |AB| = |BC|.
For example, this configuration is forbidden:
O B O O
O O O C
A O O O
O O O O
a(12) >= 29. - Robert Israel, Apr 22 2016
a(13) >= 32, a(14) >= 36, a(15) >= 38 (see pictures in Links). Note that a(14) >= 36 breaks the pattern of increasing by 3 at each step. - Giovanni Resta, Apr 23 2016

Examples

			Illustration for a(3) = 4:
   X X X
   O O O
   O X O
Illustration for a(8) = 17:
   O X O O O O O X
   X O O O O O O X
   O O O X O O O X
   O O X O O O O X
   O O O O O O O X
   O O O O O O O X
   O O O O O O X O
   X X X X X X O O

Links

Crossrefs

Cf. A271907, A227133.

Programs

  • Mathematica
    d[n_,a_,b_] := Block[{x1, y1, x2, y2}, x1 = Mod[a-1, n]; y1 = Floor[(a-1)/n];x2 = Mod[b-1, n]; y2 = Floor[(b-1)/n]; (x1-x2)^2 + (y1-y2)^2]; isorQ[n_,a_, b_,c_] := Block[{k = Sort[{d[n,a,b], d[n,b,c], d[n, a, c]}]}, k[[1]] == k[[2]] && 2 k[[1]] == k[[3]]]; sol[n_] := sol[n] = Block[{m, L={}, nv=n^2, ne}, Do[If[ isorQ[n, x, y, z], AppendTo[L, {x,y,z}]], {x, n^2}, {y, x-1}, {z, y-1}]; ne = Length@L; m = Table[0, {ne}, {nv}]; Do[m[[i, L[[i]]]] = 1, {i, ne}]; Quiet@ LinearProgramming[ Table[-1, {nv}], m, Table[{2, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; a[n_] := Total[sol[n]]; Do[Print@ MatrixForm@ Partition[ sol@n, n], {n,6}]; Array[a,6]

A271914 Symmetric array read by antidiagonals: T(n,k) (n>=1, k>=1) = maximal number of points that can be chosen in an n X k rectangular grid such that no three distinct points form an isosceles triangle.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 4, 4, 4, 4, 5, 4, 4, 4, 5, 6, 5, 5, 5, 5, 6, 7, 6, 6, 6, 6, 6, 7, 8, 7, 8, 7, 7, 8, 7, 8, 9, 8, 8, 8, 8, 8, 8, 8, 9, 10, 9, 10, 9, 9, 9, 9, 10, 9, 10
Offset: 1

Views

Author

Rob Pratt and N. J. A. Sloane, Apr 24 2016

Keywords

Comments

It is conjectured that T(n,k) <= n+k-1.
The array is symmetric: T(n,k) = T(k,n).
The main diagonal T(n,n) appears to equal 2n-2 for n>1. (This diagonal is presently A271907, but if it really is 2n-2 that entry may be recycled.)
The triangle must have nonzero area (three collinear points don't count as a triangle).

Examples

			The array begins:
   1,  2,  3,  4,  5,  6,  7,  8,  9, 10, ...
   2,  2,  4,  4,  5,  6,  7,  8,  9, 10, ...
   3,  4,  4,  5,  6,  8,  8, 10, 10, 12, ...
   4,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
   5,  5,  6,  7,  8,  9, 10, 12, 12, 14, ...
   6,  6,  8,  8,  9, 10, 11, 12, 12, 14, ...
   7,  7,  8,  9, 10, 11, 12, 13, 14, 16, ...
   8,  8, 10, 10, 12, 12, 13, 14, 16, 16, ...
   9,  9, 10, 11, 12, 12, 14, 16, 16, 18, ...
  10, 10, 12, 12, 14, 14, 16, 16, 18, 18, ...
  ...
As a triangle:
   1,
   2,  2,
   3,  2,  3,
   4,  4,  4,  4,
   5,  4,  4,  4,  5,
   6,  5,  5,  5,  5,  6,
   7,  6,  6,  6,  6,  6,  7,
   8,  7,  8,  7,  7,  8,  7,  8,
   9,  8,  8,  8,  8,  8,  8,  8,  9,
  10,  9, 10,  9,  9,  9,  9, 10,  9, 10,
  ...
Illustration for T(2,3) = 4:
XOX
XOX
Illustration for T(2,5) = 5:
XXXXX
OOOOO
Illustration for T(3,5) = 6 (this left edge + top edge construction - or a slight modification of it - works in many cases):
OXXXX
XOOOO
XOOOO
Illustration for T(3,6) = 8:
XXOOXX
OOOOOO
XXOOXX
Illustration for T(3,8) = 10:
OXXXXXXO
XOOOOOOX
XOOOOOOX
Illustration for T(6,9) = 12:
OXOOOOOOX
OOXXXXXXO
OOOOOOOOO
OXOOOOOOX
OXOOOOOOX
OOOOOOOOO
From _Bob Selcoe_, Apr 24 2016 (Start)
Two symmetric illustrations for T(6,9) = 12:
Grid 1:
X X O O O O O X X
O O O O O O O O O
O O O O O O O O O
O X X X O X X X O
X O O O O O O O X
O O O O O O O O O
Grid 2:
X O O O O O O O X
X O O O O O O O X
O O O O O O O O O
O X X X O X X X O
X O O O O O O O X
O O O O O O O O O
(Note that a symmetric solution is obtained for T(5,9) = 12 by removing row 6)
(End)

Links

Crossrefs

Cf. A271910.
Main diagonal is A271907.

Formula

From Chai Wah Wu, Nov 30 2016: (Start)
T(n,k) >= max(n,k).
T(n,max(k,m)) <= T(n,k+m) <= T(n,k) + T(n,m).
T(n,1) = n.
T(n,2) = n for n > 3.
For n > 4, T(n,3) >= n+1 if n is odd and T(n,3) >= n+2 if n is even.
Conjecture: For n > 4, T(n,3) = n+1 if n is odd and T(n,3) = n+2 if n is even.
Conjecture: If n is even, then T(n,k) <= n+k-2 for k >= 2n.
(End)
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.