[seqfan] Lattice Squares

franktaw at netscape.net franktaw at netscape.net
Sat Jul 18 18:28:35 CEST 2009


(I have changed the subject line.  When completely changing the 
subject, don't leave the old subject line.  Better, don't use "reply" 
for such a message; compose an entirely new message.  David, this means 
you.)

Richard, you appear to be assuming that the squares are aligned with 
the lattice.  If we don't make this assumption, there are two more for 
n=2:

.X...
....X
.....
X....
...X.

and its mirror image.

Franklin T. Adams-Watters


-----Original Message-----
From: Richard Mathar <mathar at strw.leidenuniv.nl>
...
dr> From: David Radcliffe <dradcliffe at gmail.com>
dr> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
dr> Subject: [seqfan] Re: Recaman observation
dr> ...
dr> I wrote a program to find the number of squares whose vertices have
dr> integer coordinates
dr> less than or equal to n in absolute value, with one vertex in each
dr> quadrant. (In particular,
dr> there are no vertices on the coordinate axes.) It appears that the
dr> number is=A0A014820(n-1).
dr> Is this correct?
dr> ...

I get A005900, that is n*(2*n^2+1)/3. The first distinctive case is n=2,
where I get only 6=A005900(1), not 8=A014820(0), squares:

.....
.x.x.
.....
.x.x.
.....

.....
x..x.
.....
.....
x..x.

.....
.x..x
.....
.....
.x..x

x..x.
.....
.....
x..x.
.....

x...x
.....
.....
.....
x...x

.x..x
.....
.....
.x..x
.....

The formula is obtained by looking at the number of possibilities for 
the
x coordinate in the upper right quadrant, which is x from 1 to n.
The number of possibilities for the y coordinate in the upper right 
(N-E)
quadrant
is also from 1 to n. We count squares as a function of these two 
coordinates.
  From the symmetry of the problem, one can place the (x,y) either on the
main diagonal, or place them in one of the octants (x<>y, NNE or ENE) 
and
multiply
their count by 2. So a(n)= 2*triangularoctants+ondiag.
  For the triangularoctants number loop over

     for(x=1..n)
        for(y=x+1..n)
           for(s=y+1..n+x)
              1
where the outer loop places the x in the North-East octant (not on 
axes), the
loop
over y places the point anywhere in this octant but not on axes, and 
the loop
over s (the side length) recognizes that the size of the square is 
limited
 from below by y (distance to the horizontal axis because one point is 
forced
into
the S-E quadrant) and from above by x (because the N-W point must stay 
in the
n-by-n square). This evaluates to
=
     for(x=1..n)
        for(y=x+1..n)
           n+x-y
=
     for(x=1..n)
        (n-x)*(n-1+x)/2
= n*(2*n-1)*(n-1)/6  = triangularoctants.

The case where the point in the N-E quadrant is on the diagonal is
     for(x=1..n)
        y=x (no loop)
           for(s=y+1..n+x)
              1
=
     for(x=1..n)
        y=x (no loop)
           n+x-y
=
     for(x=1..n)
        n
=
     n^2 = ondiag

In total a(n)=2*n*(2*n-1)*(n-1)/6+n^2 = n*(2*n^2+1)/3.

Richard J. Mathar http://www.strw.leidenuniv.nl/~mathar




More information about the SeqFan mailing list