A354702 -id:A354702 - cp's OEIS frontend

A354703 T(w,h) = w*h - A354702(w,h) is a lower bound on the gain in the number of not covered grid points from an optimally positioned and rotated cover versus a just translated cover, where T(w,h) and A354702 are triangles read by rows.

1, 1, 2, 1, 2, 2, 2, 3, 3, 4, 2, 3, 2, 3, 4, 2, 4, 3, 4, 4, 4, 3, 5, 3, 6, 4, 6, 9, 3, 5, 4, 5, 4, 4, 7, 7, 3, 6, 3, 6, 4, 6, 9, 6, 9, 3, 6, 4, 5, 4, 5, 7, 6, 6, 4, 4, 7, 5, 7, 5, 6, 10, 7, 9, 5, 9, 4, 8, 5, 8, 5, 8, 12, 8, 12, 8, 12, 16, 4, 8, 5, 7, 4, 6, 10, 6, 9, 4, 8, 12, 7

Offset: 1

Hugo Pfoertner, Jun 15 2022

			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, 2, 2; |  |  |   |  |   |  |   |   |  |
   4 |  2, 3, 3, 4; |  |   |  |   |  |   |   |  |
   5 |  2, 3, 2, 3, 4; |   |  |   |  |   |   |  |
   6 |  2, 4, 3, 4, 4, 4;  |  |   |  |   |   |  |
   7 |  3, 5, 3, 6, 4, 6,  9; |   |  |   |   |  |
   8 |  3, 5, 4, 5, 4, 4,  7, 7;  |  |   |   |  |
   9 |  3, 6, 3, 6, 4, 6,  9, 6,  9; |   |   |  |
  10 |  3, 6, 4, 5, 4, 5,  7, 6,  6, 4;  |   |  |
  11 |  4, 7, 5, 7, 5, 6, 10, 7,  9, 5,  9;  |  |
  12 |  4, 8, 5, 8, 5, 8, 12, 8, 12, 8, 12, 16; |
  13 |  4, 8, 5, 7, 4, 6, 10, 6,  9, 4,  8, 12, 7
.
T(4,3) = 3, because the optimally positioned and rotated 4 X 3 rectangle
covers A354702(4,3) = 9 grid points, whereas a translated, but unrotated 4 X 3 rectangle covers 4*3 = 12 grid points. 4*3 - 9 = 3.
  + . . . . + . . . . + . . . . + . . . . + . . . . + . . . . +
  .         .         .         .         .         .         .
  .         .         .         .         .         .         .
  .         .         .         .       O .         .         .
  .         .         .         .    ~   \.         .         .
  + . . . . + . . . . + . . . . o . . . . \ . . . . + . . . . +
  .         .         .         .         .\        .         .
  .         .         .    ~    .         . o       .         .
  .         .         o         .         .  \      .         .
  .         .     ~   .         .         .   \     .         .
  + . . . . + o . . . 1 . . . . 2 . . . . 3 . .\. . + . . . . +
  .     ~   .         .         .         .     \   .         .
  . O       .         .         .         .      o  .         .
  .  \      .         .         .         .       \ .         .
  .   \     .         .         .         .        \.         .
  + . .\. . 4 . . . . 5 . . . . 6 . . . . 7 . . . . \ . . . . +
  .     o   .         .         .         .         .\        .
  .      \  .         .         .         .         . O       .
  .       \ .         .         .         .      ~  .         .
  .        \.         .         .         .  o      .         .
  + . . . . \ . . . . 8 . . . . 9 . . . . + . . . . + . . . . +
  .         .o        .         .       ~ .         .         .
  .         . \       .         .   o     .         .         .
  .         .  \      .       ~ .         .         .         .
  .         .   \     .   o     .         .         .         .
  + . . . . + . .\. . ~ . . . . + . . . . + . . . . + . . . . +
  .         .     O   .         .         .         .         .
  .         .         .         .         .         .
  .     O---------o---------o---------o---------O   .
  .     |   .         .         .         .     |   .
  + . . | . 1 . . . . 2 . . . . 3 . . . . 4 . . | . +
  .     |   .         .         .         .     |   .
  .     |   .         .         .         .     |   .
  .     o   .         .         .         .     o   .
  .     |   .         .         .         .     |   .
  + . . | . 5 . . . . 6 . . . . 7 . . . . 8 . . | . +
  .     |   .         .         .         .     |   .
  .     |   .         .         .         .     |   .
  .     o   .         .         .         .     o   .
  .     |   .         .         .         .     |   .
  + . . | . 9 . . . .10 . . . .11 . . . .12 . . | . +
  .     |   .         .         .         .     |   .
  .     |   .         .         .         .     |   .
  .     O---------o---------o---------o---------O   .
  .         .         .         .         .         .
  + . . . . + . . . . + . . . . + . . . . + . . . . +

Hugo Pfoertner, Table of n, a(n) for n = 1..210, rows 1..20 of triangle, flattened

Cf. A354702, A354492 (diagonal).

Cf. A354704, A354705 (similar, but for maximizing the number of covered points).

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. */

A355242 T(w,h) is the minimum integer slope >= 1 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 integer slope satisfying this condition exists.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 2, 1, 3, 3, 1, 2, 1, 2, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1

Offset: 1

Hugo Pfoertner, Jun 25 2022

T(17,13) = -1 is the first occurrence of the situation that it is not possible to reach the upper limit A354702(17,13) = 215 with a rectangle whose long side has an integer slope. (17 X 13)-rectangles with integer slope cannot cover less than 216 grid points. To achieve 215 grid points requires a slope of 3/2, i.e. A355241(17,13) = 3. See the linked file for related illustrations.

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

Hugo Pfoertner, Table of n, a(n) for n = 1..210, rows 1..20 of triangle, flattened
Hugo Pfoertner, (17 X 13)-rectangles with minimum number of covered grid points

Cf. A354702.

A355241 is similar, but with slopes chosen from the list 1/2, 1, 3/2, 2, ... .

A354704 T(w,h) is a lower bound for the maximum number of grid points in a square grid covered by an arbitrarily positioned and rotated rectangle of width w and height h, excluding the trivial case of an axis-parallel unshifted cover, where T(w,h) is a triangle read by rows.

Original entry on oeis.org

2, 3, 5, 5, 8, 13, 6, 10, 15, 18, 8, 12, 20, 24, 32, 9, 14, 23, 27, 36, 41, 10, 17, 25, 30, 40, 45, 53, 12, 19, 30, 36, 48, 54, 60, 72, 13, 21, 33, 39, 52, 59, 68, 78, 89, 15, 23, 38, 45, 60, 68, 75, 90, 98, 113, 16, 25, 40, 48, 64, 72, 81, 96, 105, 120, 128, 17, 28, 43, 52, 68, 77, 88, 102, 114, 128, 137, 149

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. See A354702 for more information.

			The triangle begins:
    \ h  1   2   3   4   5   6   7    8    9   10   11   12
   w \ ----------------------------------------------------
   1 |   2;  |   |   |   |   |   |    |    |    |    |    |
   2 |   3,  5;  |   |   |   |   |    |    |    |    |    |
   3 |   5,  8, 13;  |   |   |   |    |    |    |    |    |
   4 |   6, 10, 15, 18;  |   |   |    |    |    |    |    |
   5 |   8, 12, 20, 24, 32;  |   |    |    |    |    |    |
   6 |   9, 14, 23, 27, 36, 41;  |    |    |    |    |    |
   7 |  10, 17, 25, 30, 40, 45, 53;   |    |    |    |    |
   8 |  12, 19, 30, 36, 48, 54, 60,  72;   |    |    |    |
   9 |  13, 21, 33, 39, 52, 59, 68,  78,  89;   |    |    |
  10 |  15, 23, 38, 45, 60, 68, 75,  90,  98, 113;   |    |
  11 |  16, 25, 40, 48, 64, 72, 81,  96, 105, 120, 128;   |
  12 |  17, 28, 43, 52, 68, 77, 88, 102, 114, 128, 137, 149

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

Cf. A293330, A354702, A354705, A354706 (diagonal), A354707, A355244.

Cf. A123690 (similar problem with circular disks).

PARI
```
\\ See links in A354702 and A355244.
```

A354705 T(w,h) = (w+1)*(h+1) - A354704(w,h) is an upper bound for the deficit in the number of grid points covered by an optimally positioned and rotated cover compared to the excluded singular case of an axis-parallel, unshifted cover, where T(w,h) and A354704 are triangles read by rows.

Original entry on oeis.org

2, 3, 4, 3, 4, 3, 4, 5, 5, 7, 4, 6, 4, 6, 4, 5, 7, 5, 8, 6, 8, 6, 7, 7, 10, 8, 11, 11, 6, 8, 6, 9, 6, 9, 12, 9, 7, 9, 7, 11, 8, 11, 12, 12, 11, 7, 10, 6, 10, 6, 9, 13, 9, 12, 8, 8, 11, 8, 12, 8, 12, 15, 12, 15, 12, 16, 9, 11, 9, 13, 10, 14, 16, 15, 16, 15, 19, 20

Offset: 1

Hugo Pfoertner, Jun 15 2022

See A354707 for an interpretation of the diagonal terms.

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

Hugo Pfoertner, Table of n, a(n) for n = 1..210, rows 1..20 of triangle, flattened

Cf. A354707 (diagonal).

Cf. A354702, A354703 (similar, but for minimizing the number of covered points), A354704.

A354492 Diagonal of A354703.

Original entry on oeis.org

1, 2, 2, 4, 4, 4, 9, 7, 9, 4, 9, 16, 7, 16, 8, 14, 9, 12, 23, 13, 21, 8, 17, 32, 20, 28

Offset: 1

Hugo Pfoertner, Jun 22 2022

a(n)-n is an indicator of whether the free space between the covered grid points and the perimeter of the square is relatively large. a(n)-n > 0 for n = 7, 12, 14, 19, 24, 26, ... . A comparison with the linked illustrations from A354702 shows that in all these cases the covering square is rotated by Pi/4 and that the next outer diagonal rows of grid points are very close to the perimeter of the covering square.

In these cases it is favorable if the difference from n*sqrt(2) to the next larger integer is as small as possible. This also fits with 7 and 12 being terms in A084068. Since A084068(5) = 41, it is expected that a record of a(n)-n will occur at a(41) = 41^2 - A354702(41,41) = 1681 - 1624 = 57 and a(n)-n = 16.

Hugo Pfoertner, Illustrations of diagonal terms A354702(1,1)..A354702(25,25).
Hugo Pfoertner, Illustration of a(26).

Cf. A084068, A293330, A354702, A354703.

A354707 is the analogous sequence, but for the problem of maximizing the number of grid points covered.

cp's OEIS Frontend

A354703 T(w,h) = w*h - A354702(w,h) is a lower bound on the gain in the number of not covered grid points from an optimally positioned and rotated cover versus a just translated cover, where T(w,h) and A354702 are triangles read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A354704 T(w,h) is a lower bound for the maximum number of grid points in a square grid covered by an arbitrarily positioned and rotated rectangle of width w and height h, excluding the trivial case of an axis-parallel unshifted cover, where T(w,h) is a triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A354705 T(w,h) = (w+1)*(h+1) - A354704(w,h) is an upper bound for the deficit in the number of grid points covered by an optimally positioned and rotated cover compared to the excluded singular case of an axis-parallel, unshifted cover, where T(w,h) and A354704 are triangles read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A354492 Diagonal of A354703.

Views

Author

Keywords

Comments

Links

Crossrefs