# [seqfan] Re: Recaman observation

Richard Mathar mathar at strw.leidenuniv.nl
Sat Jul 18 15:13:53 CEST 2009

As a followup to http://list.seqfan.eu/pipermail/seqfan/2009-July/001911.html

dr> Return-Path: <seqfan-bounces at list.seqfan.eu>
dr> X-Original-To: mathar at strw.leidenuniv.nl
dr> Delivered-To: mathar at strw.leidenuniv.nl
dr> Date: Fri, 17 Jul 2009 21:59:43 -0500
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> 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