A113751 -id:A113751 - cp's OEIS frontend

A085582 The number of rectangles (orthogonal or not) with corners on an n X n grid of points.

0, 1, 10, 44, 130, 313, 640, 1192, 2044, 3305, 5078, 7524, 10750, 14993, 20388, 27128, 35448, 45665, 57922, 72636, 89970, 110297, 133976, 161440, 192860, 228857, 269758, 316012, 367974, 426417, 491468, 564120, 644640, 733633, 831674, 939292

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 06 2003

nonn

			a(3) = 10 because on the 3 X 3 grid there are four 1 X 1 rectangles, two 1 X 2s, two 2 X 1's, one 2 X 2 and one 45-degree rectangle, sqrt(2) X sqrt(2).

David Radcliffe, Table of n, a(n) for n = 1..1000
David Radcliffe, Python script to calculate a(n)

Cf. A000537, A002415, A113751 (diagonal rectangles on an n X n grid).

a(n) = A000537(n-1) + A113751(n). - T. D. Noe, Nov 09 2005 [corrected by David Radcliffe, Feb 06 2020]

a(n) = n*(n-1)^2*(2n-1)/6 + 2*Sum_{a,b>0, 0David Radcliffe, Feb 06 2020

Edited by Don Reble, Nov 05 2005

A338886 a(n) is the number of positive integers k such that there exists a diagonal lattice rectangle touching all four sides of an n X k rectangle.

Original entry on oeis.org

0, 1, 1, 2, 3, 3, 5, 6, 7, 9, 12, 11, 15, 15, 16, 19, 24, 20, 28, 25, 29, 30, 36, 33, 44, 40, 42, 41, 51, 44, 59, 52, 55, 57, 69, 56, 76, 68, 71, 73, 89, 72, 92, 81, 89, 90, 107, 86, 115, 101, 107, 101, 129, 103, 126, 117, 122, 126, 147, 113, 153, 136, 148

Offset: 1

Peter Kagey, Nov 14 2020

nonn

A diagonal lattice rectangle is a rectangle with integer coordinates and no side parallel to the x-axis.

This sequence gives the row lengths of A338885.

			For n = 5 there are a(5) = 3 different y-values that appear in the coordinates of diagonal lattice rectangles that touch the x-axis, the y-axis, and the line x = 5. An example of each, listed by vertices counterclockwise:
   y_max = 4: (4,4), (0,2), (1,0), (5,2);
   y_max = 5: (4,5), (0,4), (1,0), (5,1);
   y_max = 7: (3,7), (0,6), (2,0), (5,1).

Peter Kagey, Table of n, a(n) for n = 1..1000
Code Golf Stack Exchange, Rectangles in rectangles

Cf. A085582, A113751, A338885, A338887.

a(n) >= A338887(n).

A122225 (1/4)*number of nonsquare rectangles with corners on an n X n grid of points.

Original entry on oeis.org

1, 6, 20, 52, 111, 214, 376, 620, 967, 1452, 2096, 2952, 4047, 5422, 7128, 9236, 11773, 14834, 18450, 22704, 27675, 33460, 40090, 47708, 56383, 66214, 77276, 89748, 103647, 119206, 136476, 155592, 176681, 199858, 225224, 253104, 283555, 316692

Offset: 3

Hugo Pfoertner, Sep 29 2006

nonn

			a(3)=1 because there are 4 rectangles that can be formed on the square grid [0,1,2] X [0,1,2]: {(0 0),(0 1),(2 0),(2 1)}, {(0 0),(0 2),(1 0),(1 2)}, {(0 1),(0 2),(2 1),(2 2)}, {(1 0),(1 2),(2 0),(2 2)}.

Jon E. Schoenfield, Table of n, a(n) for n = 3..500
Jon E. Schoenfield, QBasic program

Cf. A000537, A002415, A085582, A113751.

a(n) = (A085582(n) - A002415(n))/4.

Corrected and extended by Jon E. Schoenfield, Oct 08 2006

A338885 Irregular triangle read by rows in which the n-th row lists all numbers k such that there exists a diagonal lattice rectangle touching all four sides of an n X k rectangle.

Original entry on oeis.org

2, 3, 4, 5, 4, 5, 7, 6, 9, 10, 5, 7, 8, 11, 13, 7, 8, 10, 13, 16, 17, 6, 9, 11, 12, 15, 19, 21, 6, 8, 10, 11, 14, 17, 22, 25, 26, 7, 9, 10, 11, 13, 14, 16, 17, 19, 25, 29, 31, 9, 12, 13, 15, 18, 20, 21, 28, 33, 36, 37, 7, 8, 11, 12, 13, 14, 15, 17, 20, 22, 23

Offset: 2

Peter Kagey, Nov 14 2020

A diagonal lattice rectangle is a rectangle with integer coordinates and no side parallel to the x-axis.
Conjecture: The smallest number in the n-th row is A228286(n).
Conjecture: The largest number in the n-th row is A033638(n).

			Table begins:
   n | n-th row
-----+------------------------------------------------
   2 | 2
   3 | 3
   4 | 4,  5
   5 | 4,  5,  7
   6 | 6,  9, 10
   7 | 5,  7,  8, 11, 13
   8 | 7,  8, 10, 13, 16, 17
   9 | 6,  9, 11, 12, 15, 19, 21
  10 | 6,  8, 10, 11, 14, 17, 22, 25, 26
  11 | 7,  9, 10, 11, 13, 14, 16, 17, 19, 25, 29, 31
  12 | 9, 12, 13, 15, 18, 20, 21, 28, 33, 36, 37
For n = 6, three of the diagonal lattice rectangles that touch the y-axis, x-axis, and line x = 6 are:
(2 ,6), (0,2), (4,0), (6,4);
(2, 9), (0,8), (4,0), (6,1); and
(3,10), (0,9), (3,0), (6,1);
which have maximum y-values of 6, 9, and 10 respectively.

Peter Kagey, Table of n, a(n) for n = 2..11808 (first 100 rows, flattened)
Code Golf Stack Exchange, Rectangles in rectangles

Cf. A033638, A085582, A113751, A228286.

Cf. A338886 (row lengths).

A285956 Number of orthogonal rectangles with vertices on an n X n square grid of points but with no vertices on the grid's diagonals.

Original entry on oeis.org

0, 0, 0, 0, 2, 10, 30, 102, 204, 444, 740, 1300, 1950, 3030, 4242, 6090, 8120, 11032, 14184, 18504, 23130, 29250, 35750, 44110, 52932, 64020, 75660, 90012, 105014, 123214, 142170, 164850, 188400, 216240, 245072, 278800, 313650, 354042, 395694, 443574, 492860, 549100, 606900, 672420, 739662

Offset: 0

Rick L. Shepherd, Apr 29 2017

nonn

Given an order-n magic square with n >= 4, the least number of cells that can be changed to create a new square with all sums of rows, columns, and diagonals preserved is four; the four changed cells must correspond to the vertices of one of these a(n) rectangles. Of course the same sum-preserving property occurs in these cases even when the original n X n square of numbers is not a magic square. Perhaps curiously at first glance, a 3 X 3 (magic) square requires at least six cells to be changed to preserve all the sums (reflection in the central row, column, or either diagonal has the same effect as changing exactly six cells).

Cf. A000537 (orthogonal rectangles without this grid-diagonal restriction), A085582 (rectangles, orthogonal or not, also unrestricted), A113751 (rectangles, non-orthogonal, also unrestricted).

{a(n)= my(c = 0, np1 = n + 1);
for(i1 = 1, n - 1, for(i2 = i1 + 1, n, for(j1 = 1, n - 1,
  if(i1 == j1 || i1 + j1 == np1 || i2 == j1 || i2 + j1 == np1,
    continue,
    for(j2 = j1 + 1, n,
      if(i1 <> j2 && i1 + j2 <> np1 &&
         i2 <> j2 && i2 + j2 <> np1, c++)))))); c}

Conjectures from Colin Barker, May 03 2017: (Start)
G.f.: 2*x^4*(1 + 3*x + 3*x^2 + 17*x^3) / ((1 - x)^5*(1 + x)^3).
a(n) = (n^4 - 10*n^3 + 33*n^2 - 34*n) / 4 for n even.
a(n) = (n^4 - 10*n^3 + 37*n^2 - 58*n + 30) / 4 for n odd.
a(n) = 2*a(n-1) + 2*a(n-2) - 6*a(n-3) + 6*a(n-5) - 2*a(n-6) - 2*a(n-7) + a(n-8) for n>7.
(End)

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

A085582 The number of rectangles (orthogonal or not) with corners on an n X n grid of points.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A338886 a(n) is the number of positive integers k such that there exists a diagonal lattice rectangle touching all four sides of an n X k rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A122225 (1/4)*number of nonsquare rectangles with corners on an n X n grid of points.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A338885 Irregular triangle read by rows in which the n-th row lists all numbers k such that there exists a diagonal lattice rectangle touching all four sides of an n X k rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A285956 Number of orthogonal rectangles with vertices on an n X n square grid of points but with no vertices on the grid's diagonals.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

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