Different squares on an n X n lattice

[David Wilson]

I get

1 3 5 8 11 15 18 23 28 33 38 45 51 58 65 73 80 89 97 107 116 126 134 146
158 169 180 192 204 218 228 243 257 270 285 302 316 331 346 364 379 397
414 433 451 468 484 505 523 544 563 584 603 625 646 669 691 713 733 759

This confirms all submitted results.  Essentially I computed

a(n) = |{ x^2+y^2 : 0 <= x <= y and x+y < n}| - 1.

This counts squares with vertices on the n x n grid, distinct up to length 
of side.

If instead, we compute

a(n) = |{ (x, y) : 0 <= x <= y and x+y < n}| - 1.

we get the sequence

1 3 5 8 11 15 19 24 29 35 41 48 55 63 71 80 89 99 109 120 131 143 155
168 181 195 209 224 239 255 271 288 305 323 341 360 379 399 419 440 461
483 505 528 551 575 599 624 649 675 701 728 755 783 811 840 869 899 929

This counts squares with vertices on the n x n grid, distinct up to 
translation.
The first sequence considers square with vector edge (0, 5) equivalent to 
one
with vector edge (3, 4), since both have side 5, whereas the later counts 
them
as distinct, since they are not translations of one another.  This accounts 
for the
discrepancy starting at a(8).

----- Original Message ----- 
From: "Hugo Pfoertner" <all at abouthugo.de>
To: <seqfan at ext.jussieu.fr>; <njas at research.att.com>
Sent: Monday, June 06, 2005 3:23 PM
Subject: Different squares on an n X n lattice


> Seqfans, Neil,
>
> yesterday I had submitted the new sequence
>
> http://www.research.att.com/projects/OEIS?Anum=A108279
>
> (Neil, please keep it, ignoring my request sent by personal E-mail)
>
> %S A108279
> 1,3,5,8,11,15,18,23,28,33,38,45,51,58,65,73,80,89,97,107,116,126,134,
> %T A108279 146,158,169
> %N A108279 Number of different sizes occurring among the
> [etc]
>
> In a hasty over-reaction to a comment my German friend Rainer Rosenthal
> made in a discussion in the German mathematical newsgroup in a thread on
> square-avoiding lattice colorings I had asked Neil to cancel this
> sequence, because there was a deviation from Rainer's results starting
> at a(8)=18 (he suggested a(8)=19). In the meantime I've checked my
> program and couldn't find an error.
>
> The source code is at
> http://www.randomwalk.de/scimath/nxncol.for
>
> Can someone here try to check at least the correctness of a(8)=18?
>
> Thanks
>
> Hugo Pfoertner