A plane surface is marked with points in a square gridded format.
How many squares, using the points as their vertices, can be drawn within a grid of:
1. 6 x 6 points,
2. 7 x 7 points and
3. n x n points?
 
In this 3 x 3 array:
. . .
. . .
. . .
there are 6.
The 5th envelopes them all and
the 6th uses the outer midpoints
of the grid as its vertices.

There are (n1)^2 1x1 squares, (n2)^2 2x2 squares, ..., 1^2=1 nxn square.
Then there are diagonal squares of various slope. Categorizing the slopes by the Delta x and Delta y of the top left sloping side, Delta x can be anywhere from 1 to n1, with Delta y being anywhere from 1 to n  1  DeltaX. The resulting tilted square then occupies DeltaX + DeltaY rows and columns, as the upper right sloping side of the square interchanges deltaX and deltaY, and can therefore be treated like an orthogonal square of side DeltaX + DeltaY.
So we get Sigma{r=1 to n1}(r^2) + Sigma{dx=1 to n1}Sigma{dy = 1 to n  1  dx}((n  (dx+dy))^2)
n # of squares
1 0
2 1
3 6
4 20
5 50
6 105
7 196
8 336
9 540
10 825
DEFDBL AZ
FOR n = 1 TO 10
tot = 0
FOR r = 1 TO n  1
tot = tot + r * r
NEXT
FOR dx = 1 TO n  1
FOR dy = 1 TO n  1  dx
r = dx + dy
tot = tot + (n  r) * (n  r)
NEXT dy
NEXT dx
PRINT n, tot
NEXT
The OnLine Encyclopedia of Integer Sequences (Sloane) lists this as sequence A002415. One of its many definitions is
a(n) = number of squares with corners on an n X n grid. See also A024206, A108279.
and its closedform formula is
n^2*(n^21)/12
and they are called the 4dimensional pyramidal numbers.
Actually, the program works just as well using:
DEFDBL AZ
FOR n = 1 TO 10
tot = 0
FOR dx = 0 TO n  1
FOR dy = 1 TO n  1  dx
r = dx + dy
tot = tot + (n  r) * (n  r)
NEXT dy
NEXT dx
PRINT n, tot
NEXT
corresponding to
Sigma{dx=0 to n1}Sigma{dy = 1 to n  1  dx}((n  (dx+dy))^2)

Posted by Charlie
on 20080828 12:50:02 