A111500 Number of squares in an n X n grid of squares with diagonals.

1, 10, 31, 72, 137, 234, 367, 544, 769, 1050, 1391, 1800, 2281, 2842, 3487, 4224, 5057, 5994, 7039, 8200, 9481, 10890, 12431, 14112, 15937, 17914, 20047, 22344, 24809, 27450, 30271, 33280, 36481, 39882, 43487, 47304, 51337, 55594, 60079, 64800, 69761, 74970

Offset: 0

Author

Floor van Lamoen, Nov 16 2005

Keywords

• nonn
• easy

Comments

This sequence is the sum of the number of squares with horizontal/vertical sides (whose length is a positive integer), which is equal to Sum_{j=1..n} j^2 = (n*(n + 1)*(2*n + 1))/6, and the number of squares with diagonal sides (whose length is a multiple of sqrt(2)/2), which is Sum_{j=1..n} (A111746(n - 1)) = floor((n*(4*n^2 - 1))/6). - Marco Ripà, Jan 14 2024

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

Crossrefs

Cf. A000290, A100583, A111746.

Programs

Maple

seq(n^3+n^2/2-1/4+1/4*(-1)^n,n=1..65);

PARI

Vec((x^3+3*x^2+7*x+1) / ((x-1)^4*(x+1)) + O(x^100)) \\ Colin Barker, May 28 2015

Formula

a(n) = n^3 + n^2/2 - 1/4 + (1/4)*(-1)^n.

a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5) for n > 4. - Colin Barker, May 28 2015

G.f.: (x^3 + 3*x^2 + 7*x + 1) / ((x-1)^4*(x+1)). - Colin Barker, May 28 2015

From Marco Ripà, Jan 14 2024: (Start)

a(n) = Sum_{j=1..n} (A000290(j) + A111746(j-1)).

a(n) = floor(n^3 + n^2/2). (End)