A085582 -id:A085582 - cp's OEIS frontend

A000537 Sum of first n cubes; or n-th triangular number squared.

0, 1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025, 4356, 6084, 8281, 11025, 14400, 18496, 23409, 29241, 36100, 44100, 53361, 64009, 76176, 90000, 105625, 123201, 142884, 164836, 189225, 216225, 246016, 278784, 314721, 354025, 396900, 443556, 494209, 549081

Offset: 0

N. J. A. Sloane

Number of parallelograms in an n X n rhombus. - Matti De Craene (Matti.DeCraene(AT)rug.ac.be), May 14 2000
Or, number of orthogonal rectangles in an n X n checkerboard, or rectangles in an n X n array of squares. - Jud McCranie, Feb 28 2003. Compare A085582.
Also number of 2-dimensional cage assemblies (cf. A059827, A059860).
The n-th triangular number T(n) = Sum_{r=1..n} r = n(n+1)/2 satisfies the relations: (i) T(n) + T(n-1) = n^2 and (ii) T(n) - T(n-1) = n by definition, so that n^2*n = n^3 = {T(n)}^2 - {T(n-1)}^2 and by summing on n we have Sum_{ r = 1..n } r^3 = {T(n)}^2 = (1+2+3+...+n)^2 = (n*(n+1)/2)^2. - Lekraj Beedassy, May 14 2004
Number of 4-tuples of integers from {0,1,...,n}, without repetition, whose last component is strictly bigger than the others. Number of 4-tuples of integers from {1,...,n}, with repetition, whose last component is greater than or equal to the others.
Number of ordered pairs of two-element subsets of {0,1,...,n} without repetition.
Number of ordered pairs of 2-element multisubsets of {1,...,n} with repetition.
1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2.
a(n) is the number of parameters needed in general to know the Riemannian metric g of an n-dimensional Riemannian manifold (M,g), by knowing all its second derivatives; even though to know the curvature tensor R requires (due to symmetries) (n^2)*(n^2-1)/12 parameters, a smaller number (and a 4-dimensional pyramidal number). - Jonathan Vos Post, May 05 2006
Also number of hexagons with vertices in an hexagonal grid with n points in each side. - Ignacio Larrosa Cañestro, Oct 15 2006
Number of permutations of n distinct letters (ABCD...) each of which appears twice with 4 and n-4 fixed points. - Zerinvary Lajos, Nov 09 2006
With offset 1 = binomial transform of [1, 8, 19, 18, 6, ...]. - Gary W. Adamson, Dec 03 2008
The sequence is related to A000330 by a(n) = n*A000330(n) - Sum_{i=0..n-1} A000330(i): this is the case d=1 in the identity n*(n*(d*n-d+2)/2) - Sum_{i=0..n-1} i*(d*i-d+2)/2 = n*(n+1)*(2*d*n-2*d+3)/6. - Bruno Berselli, Apr 26 2010, Mar 01 2012
From Wolfdieter Lang, Jan 11 2013: (Start)
For sums of powers of positive integers S(k,n) := Sum_{j=1..n}j^k one has the recurrence S(k,n) = (n+1)*S(k-1,n) - Sum_{l=1..n} S(k-1,l), n >= 1, k >= 1.
This was used for k=4 by Ibn al-Haytham in an attempt to compute the volume of the interior of a paraboloid. See the Strick reference where the trick he used is shown, and the W. Lang link.
This trick generalizes immediately to arbitrary powers k. For k=3: a(n) = (n+1)*A000330(n) - Sum_{l=1..n} A000330(l), which coincides with the formula given in the previous comment by Berselli. (End)
Regarding to the previous contribution, see also Matem@ticamente in Links field and comments on this recurrences in similar sequences (partial sums of n-th powers). - Bruno Berselli, Jun 24 2013
A rectangular prism with sides A000217(n), A000217(n+1), and A000217(n+2) has surface area 6*a(n+1). - J. M. Bergot, Aug 07 2013, edited with corrected indices by Antti Karttunen, Aug 09 2013
A formula for the r-th successive summation of k^3, for k = 1 to n, is (6*n^2+r*(6*n+r-1)*(n+r)!)/((r+3)!*(n-1)!), (H. W. Gould). - Gary Detlefs, Jan 02 2014
Note that this sequence and its formula were known to (and possibly discovered by) Nicomachus, predating Ibn al-Haytham by 800 years. - Charles R Greathouse IV, Apr 23 2014
a(n) is the number of ways to paint the sides of a nonsquare rectangle using at most n colors. Cf. A039623. - Geoffrey Critzer, Jun 18 2014
For n > 0: A256188(a(n)) = A000217(n) and A256188(m) != A000217(n) for m < a(n), i.e., positions of first occurrences of triangular numbers in A256188. - Reinhard Zumkeller, Mar 26 2015
There is no cube in this sequence except 0 and 1. - Altug Alkan, Jul 02 2016
Also the number of chordless cycles in the complete bipartite graph K_{n+1,n+1}. - Eric W. Weisstein, Jan 02 2018
a(n) is the sum of the elements in the multiplication table [0..n] X [0..n]. - Michel Marcus, May 06 2021

			G.f. = x + 9*x^2 + 36*x^3 + 100*x^4 + 225*x^5 + 441*x^6 + ... - _Michael Somos_, Aug 29 2022

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 813.
Avner Ash and Robert Gross, Summing it up, Princeton University Press, 2016, p. 62, eq. (6.3) for k=3.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 110ff.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 155.
John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, pp. 36, 58.
Clifford Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Oxford University Press, 2001, p. 325.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
H. K. Strick, Geschichten aus der Mathematik II, Spektrum Spezial 3/11, p. 13.
D. Wells, You Are A Mathematician, "Counting rectangles in a rectangle", Problem 8H, pp. 240; 254, Penguin Books 1995.

T. D. Noe, Table of n, a(n) for n = 0..1000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Luciano Ancora, Sum of cubes of the first "n" natural numbers
Luciano Ancora, The Square Pyramidal Number and other figurate numbers
M. Azaola and F. Santos, The number of triangulations of the cyclic polytope C(n,n-4), Discrete Comput. Geom., 27 (2002), 29-48 (see Prop. 4.2(b)).
Marcel Berger, Encounter with a Geometer, Part II, Notices of the American Mathematical Society, Vol. 47, No. 3, (March 2000), pp. 326-340. [About the work of Mikhael Gromov.]
Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
blackpenredpen, Math for fun, how many rectangles?, Youtube video (2018).
Bikash Chakraborty, Proof Without Words: Sums of Powers of Natural numbers, arXiv:2012.11539 [math.HO], 2020.
Robert Dawson, On Some Sequences Related to Sums of Powers, J. Int. Seq., Vol. 21 (2018), Article 18.7.6.
Shel Kaphan, How to see that the difference between two successive squared triangular numbers is a cube
Sameen Ahmed Khan, Sums of the powers of reciprocals of polygonal numbers, Int'l J. of Appl. Math. (2020) Vol. 33, No. 2, 265-282.
Seon-Hong Kim and Kenneth B. Stolarsky, Translations and Extensions of the Nicomachean Identity, J. Int. Seq. (2024), Vol. 27, Issue 6, Art. No. 24.6.3. See p. 1.
Wolfdieter Lang, Ibn al-Haytham's trick.
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, JIS 12 (2009) 09.5.5.
Feihu Liu, Guoce Xin, and Chen Zhang, Ehrhart Polynomials of Order Polytopes: Interpreting Combinatorial Sequences on the OEIS, arXiv:2412.18744 [math.CO], 2024. See p. 13.
Henri Picciotto, Sum of Cubes, Proof without words.
C. A. Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Zentralblatt review
C. J. Pita Ruiz V., Some Number Arrays Related to Pascal and Lucas Triangles, J. Int. Seq. 16 (2013) #13.5.7.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Faulhaber's Formula
Wikipedia, Faulhaber's formula
Wikipedia, Squared triangular number
G. Xiao, Sigma Server, Operate on "n^3"
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Convolution of A000217 and A008458.
Cf. A000330, A000538, A006003.
Row sums of triangles A094414 and A094415.
Second column of triangle A008459.
Row 3 of array A103438.
Cf. A000578, A002415, A024166, A101102, A101094, A101097.
Cf. A236770 (see crossrefs).
Cf. A000290, A253169, A256188.
Cf. A000217, A000292, A000332, A000566, A035287, A039623, A053382, A053383, A059376, A059827, A059860, A085582, A127777, A176271.

List([0..40],n->(n*(n+1)/2)^2); # Muniru A Asiru, Dec 05 2018

a000537 = a000290 . a000217  -- Reinhard Zumkeller, Mar 26 2015

[(n*(n+1)/2)^2: n in [0..50]]; // Wesley Ivan Hurt, Jun 06 2014

a:= n-> (n*(n+1)/2)^2:
seq(a(n), n=0..40);

Accumulate[Range[0, 50]^3] (* Harvey P. Dale, Mar 01 2011 *)
f[n_] := n^2 (n + 1)^2/4; Array[f, 39, 0] (* Robert G. Wilson v, Nov 16 2012 *)
Table[CycleIndex[{{1, 2, 3, 4}, {3, 2, 1, 4}, {1, 4, 3, 2}, {3, 4, 1, 2}}, s] /. Table[s[i] -> n, {i, 1, 2}], {n, 0, 30}] (* Geoffrey Critzer, Jun 18 2014 *)
Accumulate @ Range[0, 50]^2 (* Waldemar Puszkarz, Jan 24 2015 *)
Binomial[Range[20], 2]^2 (* Eric W. Weisstein, Jan 02 2018 *)
LinearRecurrence[{5, -10, 10, -5, 1}, {0, 1, 9, 36, 100}, 20] (* Eric W. Weisstein, Jan 02 2018 *)
CoefficientList[Series[-((x (1 + 4 x + x^2))/(-1 + x)^5), {x, 0, 20}], x] (* Eric W. Weisstein, Jan 02 2018 *)

PARI
```
a(n)=(n*(n+1)/2)^2
```

def A000537(n): return (n*(n+1)>>1)**2 # Chai Wah Wu, Oct 20 2023

a(n) = (n*(n+1)/2)^2 = A000217(n)^2 = Sum_{k=1..n} A000578(k), that is, 1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2.
G.f.: (x+4*x^2+x^3)/(1-x)^5. - Simon Plouffe in his 1992 dissertation
a(n) = Sum ( Sum ( 1 + Sum (6*n) ) ), rephrasing the formula in A000578. - Xavier Acloque, Jan 21 2003
a(n) = Sum_{i=1..n} Sum_{j=1..n} i*j, row sums of A127777. - Alexander Adamchuk, Oct 24 2004
a(n) = A035287(n)/4. - Zerinvary Lajos, May 09 2007
This sequence could be obtained from the general formula n*(n+1)*(n+2)*(n+3)*...*(n+k)*(n*(n+k) + (k-1)*k/6)/((k+3)!/6) at k=1. - Alexander R. Povolotsky, May 17 2008
G.f.: x*F(3,3;1;x). - Paul Barry, Sep 18 2008
Sum_{k > 0} 1/a(k) = (4/3)*(Pi^2-9). - Jaume Oliver Lafont, Sep 20 2009
a(n) = Sum_{1 <= k <= m <= n} A176271(m,k). - Reinhard Zumkeller, Apr 13 2010
a(n) = Sum_{i=1..n} J_3(i)*floor(n/i), where J_ 3 is A059376. - Enrique Pérez Herrero, Feb 26 2012
a(n) = Sum_{i=1..n} Sum_{j=1..n} Sum_{k=1..n} min(i,j,k). - Enrique Pérez Herrero, Feb 26 2013 [corrected by Ridouane Oudra, Mar 05 2025]
a(n) = 6*C(n+2,4) + C(n+1,2) = 6*A000332(n+2) + A000217(n), (Knuth). - Gary Detlefs, Jan 02 2014
a(n) = -Sum_{j=1..3} j*Stirling1(n+1,n+1-j)*Stirling2(n+3-j,n). - Mircea Merca, Jan 25 2014
Sum_{n>=1} (-1)^(n+1)/a(n) = 4*(3-4*log(2)). - Vaclav Kotesovec, Feb 13 2015
a(n)*((s-2)*(s-3)/2) = P(3, P(s, n+1)) - P(s, P(3, n+1)), where P(s, m) = ((s-2)*m^2-(s-4)*m)/2 is the m-th s-gonal number. For s=7, 10*a(n) = A000217(A000566(n+1)) - A000566(A000217(n+1)). - Bruno Berselli, Aug 04 2015
From Ilya Gutkovskiy, Jul 03 2016: (Start)
E.g.f.: x*(4 + 14*x + 8*x^2 + x^3)*exp(x)/4.
Dirichlet g.f.: (zeta(s-4) + 2*zeta(s-3) + zeta(s-2))/4. (End)
a(n) = (Bernoulli(4, n+1) - Bernoulli(4, 1))/4, n >= 0, with the Bernoulli polynomial B(4, x) from row n=4 of A053382/A053383. See, e.g., the Ash-Gross reference, p. 62, eq. (6.3) for k=3. - Wolfdieter Lang, Mar 12 2017
a(n) = A000217((n+1)^2) - A000217(n+1)^2. - Bruno Berselli, Aug 31 2017
a(n) = n*binomial(n+2, 3) + binomial(n+2, 4) + binomial(n+1, 4). - Tony Foster III, Nov 14 2017
Another identity: ..., a(3) = (1/2)*(1*(2+4+6)+3*(4+6)+5*6) = 36, a(4) = (1/2)*(1*(2+4+6+8)+3*(4+6+8)+5*(6+8)+7*(8)) = 100, a(5) = (1/2)*(1*(2+4+6+8+10)+3*(4+6+8+10)+5*(6+8+10)+7*(8+10)+9*(10)) = 225, ... - J. M. Bergot, Aug 27 2022
Comment from Michael Somos, Aug 28 2022: (Start)
The previous comment expresses a(n) as the sum of all of the n X n multiplication table array entries.
For example, for n = 4:
     1  2  3  4
     2  4  6  8
     3  6  9 12
     4  8 12 16
This array sum can be split up as follows:
   +---+---------------+
   | 0 | 1   2   3   4 |    (0+1)*(1+2+3+4)
   |   +---+-----------+
   | 0 | 2 | 4   6   8 |    (1+2)*(2+3+4)
   |   |   +---+-------+
   | 0 | 3 | 6 | 9  12 |    (2+3)*(3+4)
   |   |   |   +---+---+
   | 0 | 4 | 8 |12 |16 |    (3+4)*(4)
   +---+---+---+---+---+
This kind of row+column sums was used by Ramanujan and others for summing Lambert series. (End)
a(n) = 6*A000332(n+4) - 12*A000292(n+1) + 7*A000217(n+1) - n - 1. - Adam Mohamed, Sep 05 2024

Edited by M. F. Hasler, May 02 2015

A113751 Number of diagonal rectangles with corners on an n X n grid of points.

Original entry on oeis.org

0, 0, 1, 8, 30, 88, 199, 408, 748, 1280, 2053, 3168, 4666, 6712, 9363, 12728, 16952, 22256, 28681, 36536, 45870, 56936, 69967, 85264, 102860, 123232, 146557, 173128, 203138, 237192, 275243, 318104, 365856, 418912, 477649, 542392, 613406, 691848

Offset: 1

T. D. Noe, Nov 09 2005

nonn

The diagonal rectangles are the ones whose sides are not parallel to the grid axes. All the rectangles can be reflected so that the slope of one side is >= 1. There are a total of A046657(n-1) these slopes. These slopes are the basis of the Mathematica program that counts the rectangles.

			a(3) = 1 because for the 3 X 3 grid, there is only one diagonal rectangle - a square having sides sqrt(2) units.
a(4) = 8 because for the 4 X 4 grid, there are 4 squares having sides sqrt(2) units, 2 squares having sides sqrt(5) units and 2 rectangles that are sqrt(2) by 2*sqrt(2) units.

Jinyuan Wang, Table of n, a(n) for n = 1..1000

Cf. A000537 (parallel rectangles on an n X n grid), A085582 (all rectangles on an n X n grid).

Table[n=m-1; slopes=Union[Flatten[Table[a/b, {b, n}, {a, b, n-b}]]]; rects=0; Do[b=Numerator[slopes[[i]]]; a=Denominator[slopes[[i]]]; base={a+b, a+b}; l=0; While[l++; k=l; While[extent=base+{b, a}(k-1)+{a, b}(l-1); extent[[1]]<=n && extent[[2]]<=n, pos={n+1, n+1}-extent; If[a==b && k==l, fact=1, If[pos[[1]]==pos[[2]], fact=2, fact=4]]; rects=rects+fact*Times@@pos; k++ ]; k>l], {i, Length[slopes]}]; rects, {m, 1, 42}]

a(n) = A085582(n) - A000537(n-1). [corrected by David Radcliffe, Feb 06 2020]

a(1) = 0 prepended by Jinyuan Wang, Feb 06 2020

A334581 Number of ways to choose 3 points that form an equilateral triangle from the A000292(n) points in a regular tetrahedral grid of side length n.

Original entry on oeis.org

0, 0, 4, 24, 84, 224, 516, 1068, 2016, 3528, 5832, 9256, 14208, 21180, 30728, 43488, 60192, 81660, 108828, 142764, 184708, 236088, 298476, 373652, 463524, 570228, 696012, 843312, 1014720, 1213096, 1441512, 1703352, 2002196, 2341848, 2726400, 3160272, 3648180

Offset: 0

Peter Kagey, May 06 2020

nonn

a(n) >= 4 * A269747(n).
a(n) >= 4 * A000389(n+3) = A210569(n+2).
a(n) >= 4 * (n-1) + 4 * a(n-1) - 6 * a(n-2) + 4 * a(n-3) - a(n-4) for n >= 4.

Peter Kagey, Table of n, a(n) for n = 0..1000 (Computed via Anders Kaseorg's program in the Stack Exchange link.)
Code Golf Stack Exchange, Triangles in a tetrahedron

Cf. A000292, A000389, A210569.
Cf. A000332 (equilateral triangles in triangular grid), A269747 (regular tetrahedra in a tetrahedral grid), A102698 (equilateral triangles in cube), A103158 (regular tetrahedra in cube).
Cf. A077435, A085582, A187452, A189412-A189418, A271910.

A334881 Number of squares in 3-dimensional space whose four vertices have coordinates (x,y,z) in the set {1,...,n}.

Original entry on oeis.org

0, 0, 6, 54, 240, 810, 2274, 5304, 10752, 19992, 34854, 57774, 91200, 139338, 206394, 296832, 417120, 575556, 779238, 1037514, 1359792, 1760694, 2251362, 2845140, 3554976, 4404876, 5416278, 6605946, 7996896, 9621678, 11500962, 13667772, 16143552, 18973608, 22190406

Offset: 0

Peter Kagey, May 14 2020

nonn

a(n) >= 3*n*A002415(n).

			For n = 5, one such square has vertex set {(2,1,1), (5,4,1), (4,5,5), (1,2,5)}.

Zachary Kaplan, Table of n, a(n) for n = 0..100
Zachary Kaplan, Python program
Mathematics Stack Exchange user Olivier Massicot, How many squares in a three-dimensional n X n X n cartesian grid?

Cf. A002415 (squares in square grid), A098928 (cubes in cube grid).

Cf. A000332, A077435, A085582, A102698, A103158, A187452, A189412-A189418, A269747, A271910, A334581.

a(7)-a(12) from Pontus von Brömssen, May 15 2020
a(13)-a(20) from Peter Kagey, Jul 29 2020 via Mathematics Stack Exchange link
Terms a(21) and beyond from Zachary Kaplan, Sep 01 2020, via Mathematics Stack Exchange link

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.

A289832 Triangle read by rows: T(n,k) = number of rectangles all of whose vertices lie on an (n+1) X (k+1) rectangular grid.

Original entry on oeis.org

1, 3, 10, 6, 20, 44, 10, 33, 74, 130, 15, 49, 110, 198, 313, 21, 68, 152, 276, 443, 640, 28, 90, 200, 364, 592, 866, 1192, 36, 115, 254, 462, 756, 1113, 1550, 2044, 45, 143, 314, 570, 935, 1385, 1944, 2586, 3305, 55, 174, 380, 688, 1129, 1680, 2370, 3172, 4081, 5078

Offset: 1

Hector J. Partridge, Jul 13 2017

T(n,k) is the number of rectangles (including squares) that can be drawn on an (n+1) X (k+1) grid.
The diagonal of T(n,k) is the number of rectangles in a square lattice (A085582), i.e., T(n,n) = A085582(n+1).
Column k=1 equals A000217.
Column k=2 equals A140229 for n >= 3 as the only oblique rectangles are squares of side length sqrt(2), leading to the same formula.

			Triangle T(n,k) begins:
n/k  1    2    3    4     5     6     7     8     9    10
1    1
2    3   10
3    6   20   44
4   10   33   74  130
5   15   49  110  198   313
6   21   68  152  276   443   640
7   28   90  200  364   592   866  1192
8   36  115  254  462   756  1113  1550  2044
9   45  143  314  570   935  1385  1944  2586  3305
10  55  174  380  688  1129  1680  2370  3172  4081  5078
e.g., there are T(3,3) =  44 rectangles in a 4 X 4 lattice:
There are A096948(3,3) = 36 rectangles whose sides are parallel to the axes;
There are 4 squares with side length sqrt(2);
There are 2 squares with side length sqrt(5);
There are 2 rectangles with side lengths sqrt(2) X 2 sqrt(2).

Cf. A000217, A085582, A140229, A096948.

from math import gcd
def countObliques(a,b,c,d,n,k):
    if(gcd(a, b) == 1): #avoid double counting
        boundingBox={'width':(b * c) + (a * d),'height':(a * c) + (b * d)}
        if(boundingBox['width']A096948
    ret=(n*(n-1)*k*(k-1))/4
    #oblique rectangles
    ret+=sum(countObliques(a,b,c,d,n,k) for a in range(1,n) \
                                        for b in range(1,n) \
                                        for c in range(1,k) \
                                        for d in range(1,k))
    return ret
Tnk=[[totalRectangles(n+1,k+1) for k in range(1, n+1)] for n in range(1, 20)]
print(Tnk)

cp's OEIS Frontend

A000537 Sum of first n cubes; or n-th triangular number squared.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A113751 Number of diagonal rectangles with corners on an n X n grid of points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A334581 Number of ways to choose 3 points that form an equilateral triangle from the A000292(n) points in a regular tetrahedral grid of side length n.

Views

Author

Keywords

Comments

Links

Crossrefs

A334881 Number of squares in 3-dimensional space whose four vertices have coordinates (x,y,z) in the set {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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