A354704 -id:A354704 - cp's OEIS frontend

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.

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.

A354706 Diagonal of A354704.

Original entry on oeis.org

2, 5, 13, 18, 32, 41, 53, 72, 89, 113, 128, 149, 181, 205, 242, 265, 313, 338, 373, 421, 450, 512, 545, 584, 648, 697

Offset: 1

Hugo Pfoertner, Jun 19 2022

a(n) is a lower bound for the maximum number of grid points in a square grid covered by an arbitrarily positioned and rotated square of side length n, excluding the trivial case of an axis-parallel unshifted square.

Grid points must be strictly inside the covering square, i.e., grid points on the perimeter of the square are not allowed.

			For examples see the figures in the linked file.

Hugo Pfoertner, Illustrations of the terms a(1)..a(22).

Cf. A293330, A354704, A354705, A354707.

a(n) = A354704(n,n).

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

Hugo Pfoertner, Jun 29 2022

			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. A354704, A354706.

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

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.

Original entry on oeis.org

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

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.

Original entry on oeis.org

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

A354707 Diagonal of A354705.

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

Hugo Pfoertner, Jun 21 2022

a(n)-n is an indicator of whether there is still space between the covered grid points and the best possible placed square towards its perimeter. a(n)-n <= 0 for n = 3, 5, 10, 15, 17, 20, 22, ... . A comparison with the linked illustrations from A354706 shows that in all these cases the covering square is rotated by Pi/4 and only slightly exceeds diagonal rows of grid points on all its edges.

Hugo Pfoertner, Illustrations of diagonal terms A354704(1,1)..A354704(22,22).

Cf. A354704, A354705, A354706.

A354492 is the analogous sequence, but for the problem of minimizing the number of grid points covered.

A372917 a(n) is the number of distinct rectangles with area n whose vertices lie on points of a unit square grid.

Original entry on oeis.org

1, 2, 1, 3, 2, 3, 1, 4, 2, 5, 1, 5, 2, 3, 3, 5, 2, 5, 1, 8, 2, 3, 1, 7, 3, 5, 2, 5, 2, 9, 1, 6, 2, 5, 3, 8, 2, 3, 3, 11, 2, 6, 1, 5, 5, 3, 1, 9, 2, 8, 3, 8, 2, 6, 3, 7, 2, 5, 1, 15, 2, 3, 3, 7, 5, 6, 1, 8, 2, 9, 1, 11, 2, 5, 5, 5, 2, 9, 1, 14, 3, 5, 1, 10, 5, 3

Offset: 1

Felix Huber, Jun 08 2024

nonn

A rectangle in the square unit grid has the sides W = w*sqrt(r) and H = h*sqrt(r). The area is therefore n = w*h*r. Let r be a squarefree divisor of n that can be written as the sum of two squares x^2 + y^2. The number of distinct rectangles is then the sum of the number of ways for each value of r to decompose n/r into two factors w and h (with w >= h).

			See also the linked illustrations of the terms a(4) = 3, a(8) = 4, a(15) = 3.
n = 4 has the three divisors 1, 2, 4. Since 4 is not squarefree, r can have the values 1 or 2. For r = 1 = 1^2 + 0^2 there are two rectangles (2,2), (4,1). For r = 2 = 1^2 + 1^2 and n/r = 4/2 = 2 = w*h there is the rectangle (2*sqrt(2), 1*sqrt(2)). That's a total of a(4) = 3 distinct rectangles.
n = 8 has the four divisors 1, 2, 4, 8. Since 4 and 8 are not squarefree, r can have the values 1 or 2. For r = 1 = 1^2 + 0^2 there are two rectangles (4,2), (8,1). For r = 2 = 1^2 + 1^2 and n/r = 8/2 = 4 = w*h there are the rectangles (4*sqrt(2), 1*sqrt(2)) and (2*sqrt(2), 2*sqrt(2)). That's a total of a(8) = 4 distinct rectangles.
n = 15 has the four divisors 1, 3, 5, 15. They are all squarefree, but 3 and 15 cannot be written as a sum of two squares, r can only have the values 1 or 5. For r = 1 = 1^2 + 0^2 there are two rectangles (5,3), (15,1). For r = 5 = 2^2 + 1^2 and n/r = 15/5 = 3 = w*h there is the rectangles (3*sqrt(5), 1*sqrt(5)). That's a total of a(15) = 3 distinct rectangles.

Felix Huber, Table of n, a(n) for n = 1..10000
Felix Huber, Illustrations of terms a(4), a(8), a(15)

Cf. A001481, A005117, A038548, A085582, A113751, A122225, A285956, A330805, A354704, A372915.

A372917:= proc(n)
    local f,i,prod;
    f:=ifactors(n)[2];
    prod:=1;
    for i from 1 to numelems(f) do
        if f[i][1] mod 4 = 3 then
            prod:=prod*(1*f[i][2]+1);
        else
            prod:=prod*(2*f[i][2]+1);
        end if;
    end do;
    return round(prod/2);
end proc;
seq(A372917(n),n=1..86);

a(n) = my(f=factor(n)); prod(i=1,#f[,1], if(f[i,1]%4==3,1,2)*f[i,2] + 1) \/ 2; \\ Kevin Ryde, Jun 09 2024

a(n) = ceiling(Product_{i=1..omega(n)}(k[i]*e[i] + 1)/2), with k[i] = 2 if p[i] mod 4 = 3 and k[i] = 1 else, where p[i]^e[i] is the prime factorization of n.

cp's OEIS Frontend

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

A354706 Diagonal of A354704.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

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

A354707 Diagonal of A354705.

Views

Author

Keywords

Comments

Links

Crossrefs

A372917 a(n) is the number of distinct rectangles with area n whose vertices lie on points of a unit square grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula