 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  MultiSquares (Posted on 2008-08-28) 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.```

 See The Solution Submitted by brianjn Rating: 4.0000 (1 votes) Comments: ( Back to comment list | You must be logged in to post comments.) solution Comment 2 of 2 | There are (n-1)^2 1x1 squares, (n-2)^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 n-1, 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 n-1}(r^2) + Sigma{dx=1 to n-1}Sigma{dy = 1 to n - 1 - dx}((n - (dx+dy))^2)

`n         # of squares`
`1             02             13             64             205             506             1057             1968             3369             54010            825`

DEFDBL A-Z
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 On-Line 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 closed-form formula is

n^2*(n^2-1)/12

and they are called the 4-dimensional pyramidal numbers.

Actually, the program works just as well using:

DEFDBL A-Z
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 n-1}Sigma{dy = 1 to n - 1 - dx}((n - (dx+dy))^2)

 Posted by Charlie on 2008-08-28 12:50:02 Please log in:

 Search: Search body:
Forums (0)