OFFSET
0,3
COMMENTS
This sequence has implications for constructing Steiner trees for square unit arrays of dots: an orthogonal-only tree for an m X m dot array would need m^2-1 units. The value of a(m-1) tells you how many (1+sqrt(3)) 'X' shapes you can place in the grid, each saving (2-sqrt(3)) units.
Unfortunately this doesn't generally lead to the minimal Steiner tree.
An upper bound for this sequence is (((n+1)^2)-1)/3, which is reached iff n = 2^k-1.
The value of a(n)/n^2 (the painted cells as a proportion of all of the cells) converges extremely slowly to 1/3.
This sequence is related to the sequence of Heyawake numbers A239231, which has the additional criterion that the unpainted area should be contiguous. For sufficiently large Heyawake grids, this sequence forms the central (n-4) X (n-4) square of the Heyawake grid.
EXAMPLE
For example, if n=6, the painted cells could be A1, A3, A5, B2, B6, C1, C3, C5, D6, E1, E3, E5, F2, F4, F6 (15 cells in all).
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Elliott Line, Mar 10 2014
EXTENSIONS
Some values corrected, incorrect formula and values removed by Elliott Line, Aug 21 2014
a(12), a(16), a(22), a(24), a(25) have been corrected by Elliott Line at the suggestion of Greg Malen, Sep 02 2020
STATUS
approved