A355242 -id:A355242 - cp's OEIS frontend

A354702 T(w,h) is an upper bound for the minimum number of grid points in a square grid covered by an arbitrarily positioned and rotated rectangle of width w and height h, where T(w,h) is a triangle read by rows.

0, 1, 2, 2, 4, 7, 2, 5, 9, 12, 3, 7, 13, 17, 21, 4, 8, 15, 20, 26, 32, 4, 9, 18, 22, 31, 36, 40, 5, 11, 20, 27, 36, 44, 49, 57, 6, 12, 24, 30, 41, 48, 54, 66, 72, 7, 14, 26, 35, 46, 55, 63, 74, 84, 96, 7, 15, 28, 37, 50, 60, 67, 81, 90, 105, 112, 8, 16, 31, 40, 55, 64, 72, 88, 96, 112, 120, 128

Offset: 1

Hugo Pfoertner, Jun 15 2022

Grid points must lie strictly within the covering rectangle, i.e., grid points on the perimeter of the rectangle are not allowed.
These upper bounds were determined by an extensive random search, the results of which were stable. The proof that none of these bounds can be improved should be possible with a constructive technique such as integer linear programming applied to all combinatorially possible positions of the rectangle relative to the lattice.
A simple random search is implemented in the attached PARI program, which enables a plausibility check of the results for small covering rectangles. It also provides results for the maximum problem. Additional methods were used to obtain the results shown. In particular, angular orientations of the rectangle along connecting lines between all pairs of lattice points and extreme positions of the rectangle, where lattice points are very close to the corners of the rectangle, were investigated, using adjacent terms in A000404.

			The triangle begins:
    \ h 1   2   3   4   5   6   7   8   9   10   11   12
   w \ -------------------------------------------------
   1 |  0;  |   |   |   |   |   |   |   |    |    |    |
   2 |  1,  2;  |   |   |   |   |   |   |    |    |    |
   3 |  2,  4,  7;  |   |   |   |   |   |    |    |    |
   4 |  2,  5,  9, 12;  |   |   |   |   |    |    |    |
   5 |  3,  7, 13, 17, 21;  |   |   |   |    |    |    |
   6 |  4,  8, 15, 20, 26, 32;  |   |   |    |    |    |
   7 |  4,  9, 18, 22, 31, 36, 40;  |   |    |    |    |
   8 |  5, 11, 20, 27, 36, 44, 49, 57;  |    |    |    |
   9 |  6, 12, 24, 30, 41, 48, 54, 66, 72;   |    |    |
  10 |  7, 14, 26, 35, 46, 55, 63, 74, 84,  96;   |    |
  11 |  7, 15, 28, 37, 50, 60, 67, 81, 90, 105, 112;   |
  12 |  8, 16, 31, 40, 55, 64, 72, 88, 96, 112, 120, 128

Hugo Pfoertner, Table of n, a(n) for n = 1..210, rows 1..20 of triangle, flattened
Hugo Pfoertner, Illustrations of the initial terms up to T(5,5).
Hugo Pfoertner, PARI program

Cf. A293330 (diagonal).
Cf. A354492, A354703, A354704, A354705, A355241, A355242.
Cf. A291259 (similar problem for circular disks).
Cf. A000404 (used to check extreme positions of grid points).

PARI
```
\\ See link.
```
PARI
```
\\ See also program link in A355241.
```

A355241 T(w,h)/2 is the minimum slope >= 1/2 that can be chosen as orientation of a w X h rectangle such that the upper bound for the minimum number of covered grid points A354702(w,d) can be achieved by a suitable translation of the rectangle, where T(w,h) and A354702 are triangles read by rows. T(w,h) = -1 if no slope satisfying this condition exists.

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 6, 2, 2, 1, 1, 6, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 1, 6, 1, 2, 1, 2, 2, 1, 2, 6, 2, 2, 2, 2, 2, 2, 1, 1, 6, 6, 2, 1, 2, 1, 2, 2, 1, 2, 6, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 6, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 6, 2, 2, 1, 2, 2, 2, 2, 2

Offset: 1

Hugo Pfoertner, Jun 27 2022

No example of T(w,h) = -1 is known for w <= 20, i.e., the upper bound A354702(w,h) can always be achieved using a slope that is an integer multiple of 1/2. In the range w <= 20, T(17,13) = 3 is the only occurrence of the required slope 3/2.

For some rectangle dimensions it is possible to reach the value of A354702(w,h) with different slopes. In the simplest case, e.g., with the slopes 1/2 (T(w,h)=1) and 1 (A355242(w,h)=1). The linked file shows examples for some pairs of values (w,h) and the case of (10,10) with 3 different slopes.

			The triangle begins:
    \ h 1  2  3  4  5  6  7  8  9 10 11 12 13
   w \ --------------------------------------
   1 |  1; |  |  |  |  |  |  |  |  |  |  |  |
   2 |  1, 2; |  |  |  |  |  |  |  |  |  |  |
   3 |  1, 1, 1; |  |  |  |  |  |  |  |  |  |
   4 |  2, 2, 1, 1; |  |  |  |  |  |  |  |  |
   5 |  2, 2, 1, 1, 6; |  |  |  |  |  |  |  |
   6 |  2, 2, 1, 1, 6, 2; |  |  |  |  |  |  |
   7 |  2, 2, 1, 2, 2, 2, 2; |  |  |  |  |  |
   8 |  2, 2, 1, 1, 6, 1, 2, 1; |  |  |  |  |
   9 |  2, 2, 1, 2, 6, 2, 2, 2, 2; |  |  |  |
  10 |  2, 2, 1, 1, 6, 6, 2, 1, 2, 1; |  |  |
  11 |  2, 2, 1, 2, 6, 2, 2, 1, 2, 1, 2; |  |
  12 |  2, 2, 1, 2, 6, 2, 2, 1, 2, 2, 2, 2; |
  13 |  2, 2, 1, 2, 6, 2, 2, 1, 2, 2, 2, 2, 2

Hugo Pfoertner, Table of n, a(n) for n = 1..210, rows 1..20 of triangle, flattened
Hugo Pfoertner, Different slopes with the same number of grid points covered.
Hugo Pfoertner, PARI program

Cf. A354702, A355242.

A355244 is similar, but for maximizing the number of covered grid points.

/* See Pfoertner link. The program can be used to validate the given terms by calling it successively with the slope parameter k, starting with k = 1/2, 2/2=1, 3/2, (4/2 = 2 already covered by 1/2 via symmetry), 5/2, 6/2=3 for the desired rectangle size w X h , until the number of grid points given by A354702(w,k) is reached for the first time as a result. Without specifying the slope parameter, the program tries to approximate A354702(w,k) and determine a position of the rectangle maximizing the free space between peripheral grid points and the rectangle. */

cp's OEIS Frontend

A354702 T(w,h) is an upper bound for the minimum number of grid points in a square grid covered by an arbitrarily positioned and rotated rectangle of width w and height h, where T(w,h) is a triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI