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
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
Cf.
A123690 (similar problem with circular disks).
Original entry on oeis.org
2, 4, 3, 7, 4, 8, 11, 9, 11, 8, 16, 20, 15, 20, 14, 24, 11, 23, 27, 20, 34, 17, 31, 41, 28, 32
Offset: 1
A354492 is the analogous sequence, but for the problem of minimizing the number of grid points covered.
A355244
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 lower bound for the maximum number of covered grid points A354704(w,d) can be achieved by a suitable translation of the rectangle, where T(w,h) and A354704 are triangles read by rows. T(w,h) = -1 if no slope satisfying this condition exists.
Original entry on oeis.org
1, 1, 1, 1, 2, 2, 1, 3, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 6, 2, 2, 2, 1, 6, 2, 6, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 6, 2, 1, 2, 2, 1, 3, 2, -1, 2, 2, 3, 2, 1, 2, -1, 3, 2, 1, 2, 2, 2, 2, 6, 2, 1, 2, 2, 1, 2
Offset: 1
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, 2, 2; | | | | | | | | | |
4 | 1, 3, 2, 2; | | | | | | | | |
5 | 1, 1, 2, 2, 2; | | | | | | | |
6 | 1, 1, 2, 2, 2, 2; | | | | | | |
7 | 1, 6, 2, 2, 2, 1, 6; | | | | | |
8 | 2, 6, 2, 2, 2, 2, 2, 2; | | | | |
9 | 1, 1, 2, 2, 2, 1, 1, 2, 1; | | | |
10 | 2, 1, 2, 2, 2, 2, 2, 2, 2, 2; | | |
11 | 2, 1, 2, 2, 2, 2, 6, 2, 1, 2, 2; | |
12 | 1, 3, 2,-1, 2, 2, 3, 2, 1, 2,-1, 3; |
13 | 2, 1, 2, 2, 2, 2, 6, 2, 1, 2, 2, 1, 2
.
The first linked illustration shows examples where 2 slopes lead to the same number of covered grid points, where then the smallest multiple of 1/2 is used as a term in the sequence.
The second illustration shows the two examples where it is not possible to cover the maximum number of grid points with a rectangle whose side slope is an integer multiple of 1/2.
- Hugo Pfoertner, Table of n, a(n) for n = 1..210, rows 1..20 of triangle, flattened
- Hugo Pfoertner, Illustrations of T(4,2) = 3, T(7,6) = T(9,6) = T(13,12) = 1.
- Hugo Pfoertner, Illustrations of T(12,4) = T(12,11) = -1.
- Hugo Pfoertner, PARI program
Cf.
A355241 (similar, but with number of covered grid points minimized).
-
/* 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 A354704(w,k) is reached for the first time as a result. If the slope parameter is not specified, the program attempts to approximate A354704(w,k) and determine a location of the rectangle that maximizes the free margin between the peripheral grid points and the perimeter of the rectangle. */
Showing 1-3 of 3 results.
Comments