[seqfan] Re: How many squares can you make from n points in the plane?

[hv at crypt.org]

I'm looking at a slightly different computational approach: rather than
assuming a limit on the grid size, I assume that any maximal selection
can be generated by starting with a unit square, and then repeatedly
extending it with additional squares, always adding either 1 or 2 points
at a time. (Ie, I look for all triplets of points to see if they can
be three of a square, and at all pairs of points to see if they can be
one edge of a square.)

I think it may be possible to prove this assumption is safe, though it's
probably beyond my own capabilities; I note that this also can generate
only integer coordinates.

My rudimentary code for this verifies up to n=14; I'll need to speed it
up some to go much further (but that should be easy to do).

I've also added checks on the smallest and greatest grid size of maximal
configurations, those look like this:

n A051602(n) min-span max-span
6 2 3x2 3x2
7 3 3x3 3x3
8 4 3x3 4x3
9 6 3x3 3x3
10 7 4x3 4x3
11 8 4x3 (4x4 or 5x3)
12 11 4x4 4x4
13 13 4x4 4x4
14 15 4x4 4x4

Note that the max-span results for n=11 have two possibilities:

maximum 4x4:
.xx.
xxxx
xxx.
.xx.

maximum 5x3:
.xxx.
xxxxx
.xxx.

Hugo