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

[hv at crypt.org]

I wrote:
: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 done that now, and fixed some bugs; that gets me up to n=17, and
n=18 should take about 4 hours (though due to hardware instability
that may take me a few attempts - I'd be delighted if someone else
could run it).

n A051602(n) min-span max-span (iterations) time
 5  1 2x2 2x2 (1) 0.00s
 6  2 3x2 3x3 (3) 0.00s
 7  3 3x3 3x3 (6) 0.00s
 8  4 3x3 4x3 (21) 0.00s
 9  6 3x3 3x3 (78) 0.00s
10  7 4x3 4x3 (499) 0.00s
11  8 4x3 5x4 (3012) 0.00s
12 11 4x4 4x4 (24040) 0.01s
13 13 4x4 4x4 (185246) 0.13s
14 15 4x4 4x4 (1671581) 1.19s
15 17 4x4 5x4 (15040077) 11.58s
16 20 4x4 5x4 (150691667) 122.22s
17 22 5x4 5x5 (1530354556) 1353.26s

Here are the two distinct solutions I find for n=17:

xxxx.
xxxxx
xxxxx
.xxx.

..x..
xxxx.
xxxxx
xxxx.
.xxx.

I've made the code available at:
  https://github.com/hvds/seq/tree/master/A051602

It should hopefully compile without problems if you have gcc; with other
compilers you'll need to change the optimization options in the Makefile,
but it shouldn't need much more than that.

Hugo