[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