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.

%I A354702 #28 Jan 03 2025 18:39:37
%S A354702 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,
%T A354702 5,11,20,27,36,44,49,57,6,12,24,30,41,48,54,66,72,7,14,26,35,46,55,63,
%U A354702 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
%N 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.
%C A354702 Grid points must lie strictly within the covering rectangle, i.e., grid points on the perimeter of the rectangle are not allowed.
%C A354702 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.
%C A354702 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.
%H A354702 Hugo Pfoertner, <a href="/A354702/b354702.txt">Table of n, a(n) for n = 1..210</a>, rows 1..20 of triangle, flattened
%H A354702 Hugo Pfoertner, <a href="/A354702/a354702.pdf">Illustrations of the initial terms up to T(5,5)</a>.
%H A354702 Hugo Pfoertner, <a href="/A354702/a354702_1.gp.txt">PARI program</a>
%e A354702 The triangle begins:
%e A354702     \ h 1   2   3   4   5   6   7   8   9   10   11   12
%e A354702    w \ -------------------------------------------------
%e A354702    1 |  0;  |   |   |   |   |   |   |   |    |    |    |
%e A354702    2 |  1,  2;  |   |   |   |   |   |   |    |    |    |
%e A354702    3 |  2,  4,  7;  |   |   |   |   |   |    |    |    |
%e A354702    4 |  2,  5,  9, 12;  |   |   |   |   |    |    |    |
%e A354702    5 |  3,  7, 13, 17, 21;  |   |   |   |    |    |    |
%e A354702    6 |  4,  8, 15, 20, 26, 32;  |   |   |    |    |    |
%e A354702    7 |  4,  9, 18, 22, 31, 36, 40;  |   |    |    |    |
%e A354702    8 |  5, 11, 20, 27, 36, 44, 49, 57;  |    |    |    |
%e A354702    9 |  6, 12, 24, 30, 41, 48, 54, 66, 72;   |    |    |
%e A354702   10 |  7, 14, 26, 35, 46, 55, 63, 74, 84,  96;   |    |
%e A354702   11 |  7, 15, 28, 37, 50, 60, 67, 81, 90, 105, 112;   |
%e A354702   12 |  8, 16, 31, 40, 55, 64, 72, 88, 96, 112, 120, 128
%o A354702 (PARI) \\ See link.
%o A354702 (PARI) \\ See also program link in A355241.
%Y A354702 Cf. A293330 (diagonal).
%Y A354702 Cf. A354492, A354703, A354704, A354705, A355241, A355242.
%Y A354702 Cf. A291259 (similar problem for circular disks).
%Y A354702 Cf. A000404 (used to check extreme positions of grid points).
%K A354702 nonn,tabl
%O A354702 1,3
%A A354702 _Hugo Pfoertner_, Jun 15 2022