How many perfect squares can be made from integer vertices?

Question

within x = [0,13] and y = [0,13] ? like when you have square's vertices of (1,0), (0,1), (1,2) and (2,1).
How many rectangles with integer vertices (include the squares)?
Show work on both answers.

Before you complain the question is too easy, then further your research into the 3D. Within x = [0,13], y = [0,13] and z = [0,13] (first octant), find the number of perfect cubes with integer vertices (all 8 of them). Then find the integral cuboids (include the cubes).
Show work.

Answer 1

I got for the number of squares inside x = [0, n] and y = [0, n] /n = 1, 2, 3, . ./ the following:

n*1² + (n-1)*2² + (n-2)*3² + . . + 3*(n-2)² + 2*(n-1)² + 1*n²

For n = 13 there are

13*1² + 12*2² + 11*3² + . . + 3*11² + 2*12² + 1*13² = 3185 squares.



First, let us count how many squares are with sides, parallel to grid lines - one nxn-size, 4=2² (n-1)x(n-1)-size, 9=3² (n-2)x(n-2)-size etc., finally n² 1x1-size

/we have k+1 ways to choose the horizontal and k+1 ways

the vertical projection of (n-k)x(n-k)-size square/.



Next, a square with side √(s'² + s"²) where s' + s" = s ≤ n can be embedded into a sxs-side square of the above type, for example

(1,0), (0,1), (1,2), (2,1).can be embedded into (0,0), (0,2), (2,2), (2,0);

(0,1), (1,3), (3,2), (2,0) and (1,0), (3,1), (2,3) and (0,2)

can be embedded into (0,0), (0,3), (3,3) and (3,0).

If s' = s" the embedding square contains 1 square (connecting its midpoints), otherwise contains 2 squares, symmetric with respect to the line y=x (swapped x and y coordinates). Counting the embedding squares yields the above expression.



(Continued past the weekend) I thought it over and was going to submit further explanation of the above embedding process with the explicit formula and an illustration with the single square for n=1, 6 squares for n=2 and 20 for n=3, but when I came later and read JB's answer with both the formula and picture, I must confess I felt a professional envy (in the good sense of that word).

Superb animation, this is indeed a work of computer art I haven't seen here in Y!A!



Anyway, it's very easy to show that the rectangles with sides, parallel to the grid lines are

n² (n+1)² / 4

That was a question from the early days of MS Windows how many possible widows are on screen with a given resolution - the rectangle structure is described by the 2 diagonally opposite points, so we have n+1 ways to choose the 1st abscissa /0,1, . . , n/, same for the 1st ordinate, then the 2nd point shouldn't be on the same horizontal and vertical grid lines - thus we count every rectangle 4 times.

But to count all rectangles using the embedding approach above is somewhat difficult - the number of the embedded rectangles depends on the sizes, maybe another approach will be more fruitful.



Another difficulties are in the case of cubes. Since the square has 4 sides and 4 vertexes, drawing 4 lines through vertexes, parallel to the coordinate axes, we get an embedding square. But the cube has 8 vertexes and 6 faces and if we try for example to embed the cube, spanned on the vectors

(3, 4, 0), (-4, 3, 0) and (0, 0, 5)

its embedding solid is a cuboid, not a cube, so that approach doesn't look very promising.



I am not sure I'll have enough time (please extend the expiration) to examine this extremely interesting question thoroughly, let's hope JB or somebody else will succeed or will provide some useful links.



(Final edit - Question 2: How Many Rectangles, Including Squares)

2a) As noted above, there are 13² *14² / 4 = 8281 rectangles with sides, parallel to the grid lines;



2b) All other squares and rectangles with sides, multiple of √2 can be embedded into squares of type 2a) with side length 1, 2, . . , 13; the relationship between the side length and number of embedded rectangles is:

side length: 1 2 3 4 5 6 . 7. 8 . 9 10 11 12 13

embedded: 0 1 4 5 8 9 12 13 16 17 20 21 24

The number of all rectangles of type 2b) is then

1*12² + 4*11² + 5*10² + 8*9² + 9*8² + 12*7² + 13*6² + 16*5² + 17*4² + 20*3² + 21*2² + 24*1² = 4368



2c) Rectangles whose embedding rectangle is not a square remain:

embedded embedding number of

rectangle . .rectangle . . embedded

sides . . . . . sides . . . . . rectangles

√5 x 2√5 . . 5 x 4 . . . . . . 4*90

√5 x 3√5 . . 7 x 5 . . . . . . 4*63

√5 x 4√5 . . 9 x 6 . . . . . . 4*40

√5 x 5√5 . . 11 x 7 . . . . . 4*21

√5 x 6√5 . . 13 x 8 . . . . . 4*6

2√5 x 3√5 . . 8 x 7 . . . . . 4*42

2√5 x 4√5 . 10 x 8 . . . . . 4*24

2√5 x 5√5 . 12 x 9 . . . . . 4*10

3√5 x 4√5 . 11 x 10 . . . . 4*12

3√5 x 5√5 . 13 x 11 . . . . 4*3

√10 x 2√10 . 7 x 5 . . . . . 4*63

√10 x 3√10 . 10 x 6 . . . . 4*32

√10 x 4√10 . 13 x 7 . . . . 4*7

2√10 x 3√10 11 x 9 . . . . 4*15

√13 x 2√13 . . 8 x 7 . . . . 4*42

√13 x 3√13 . . 11 x 9 . . . 4*15

2√13 x 3√13 . 13 x 12 . . 4*2

√17 x 2√17 . . 9 x 6 . . . . 4*40

√17 x 3√17 . . 13 x 7 . . . 4*7

5 x 10 . . . . . . . 11 x 10 . . 4*12

√26 x 2√26 . . . 11 x 7 . . . 4*21

√29 x 2√29 . . . 12 x 9 . . . 4*10

√34 x 2√34 . . . 13 x 11 . . 4*3

√37 x 2√37 . . . 13 x 8 . . . 4*6

The side length of the embedded rectangles is a square root of a sum of small naturals from

√(1² + 2²) to √(1² + 6²) /√2 and its multiples included in 2b) above/

The number of embedding a x b rectangles is 2*(14-a)*(14-b) /both a x b and b x a/, each containing 2 embedded (in the 1st column), so the total number of rectangles of type 2c) is the sum of the numbers in the 3rd column above:2344



Total number of rectangles: 8281 + 4368 + 2344 = 14993.

See an illustration of some of above cases:

http://farm4.static.flickr.com/3032/3093095845_2b21f25030_o.gif

Now it is my turn to be happy since this agrees with JB's answer.

Thank You very much for the time You gave me to finish my answer (quite possibly a more efficient enumerating approach would do the job easier) - this was one of the greatest questions I have seen here in Y!A!

Answer 2

Someone asked this same question for squares in an 8 by 8 grid here before and I wrote a program to count the squares and generate a picture. In that case there were 540 squares. I changed n=8 to n=13 and re-ran the program and found 3185 squares this time. I am pleased that this answer agrees with Duke's. I put a pdf file with the (vector) picture in it at this link:



http://www.buddenbooks.com/jb/squares_in_13_by_13_grid.pdf



You can zoom and see detail, and watch while the picture is regenerated. A jpg version of this is over 200K but this pdf file (created with ghostscript) is only 19K.



Also, I took a look at Duke's expression, and found that it can be summed in closed form giving the number of squares in an n by n grid as:



n(n+1)²(n+2) / 12



You can check that for n=8 this gives 540 squares and for n=13 it gives 3185 squares.



I'm not sure I'll have a chance to check out the rectangles problem, but will add more here if I do.



EDIT: I just checked and found that the sequence of the number of squares in an n by n grid is in OEIS. You can find it here:

http://www.research.att.com/~njas/sequences/A002415



EDIT2: I modified my program to count rectangles and it found that there are 14993 rectangles in the 13 by 13 grid.



Here is the list [grid size, number of rectangles] for grids from 1 to 13: [1,1], [2,10], [3,44], [4,130], [5,313], [6,640], [7,1192], [8,2044], [9,3305], [10,5078], [11,7524], [12,10750], [13,14993]. I then typed the sequence into OEIS and got a hit here:

http://www.research.att.com/~njas/sequences/A085582

which corroborates these calculations.



I did not look at cubes in a cube.



EDIT3: OEIS has the sequence for cubes with corners on a grid. You can see it here:



http://www.research.att.com/~njas/sequences/A098928

http://www.research.att.com/~njas/sequences/table?a=98928&fmt=4



Note that what in this problem we call n=1, they call n=2 so their sequence is offset by 1. Their sequence stops at the place we here would call n=10, for which they give 4469 cubes. So this problem for n=13 is still open.

Answer 3

the easiest way to do this is 1 dimension at a time.



Let's start with 1-dimension!



How many lines can we fit between 0 and 13, that connect two integer vertices?



Length 1: 13 segments (trivial)

Length 2: 12

Length 3: 11



and so on....



Now for 2 dimensions...

Squares with..

Area 1^2: 13^2

Area 2^2: 12^2

Etc...



Basically the answer is just going to be the summation from 1 to 13 of x^n, where n is the dimension you're in.

Answer 4

i think the first answer is



C(14,2) x C(14,2). C is for combinations.



For every square you need 2 distinct points in the X axis. These must be combined with another 2 distinct Y points.



The number of distinct 2 points combination in any of the axes is C(14,4) .

We are multiplying one set into the other so,



C(14,2) x C(14,2)

Answer 5

You sure take the fun out of Friday morning!