A239072 Maximum number of cells in an n X n square grid that can be painted such that no two orthogonally adjacent cells are painted and every unpainted cell can be reached from the edge of the grid by a series of orthogonal steps to unpainted cells.

0, 1, 2, 5, 7, 11, 15, 21, 26, 32, 39, 47, 55, 64, 74, 85, 95, 107, 119, 132, 146, 160, 175, 191, 207, 224, 242, 260, 279, 299, 319, 341, 362, 384, 407, 431, 455, 480, 506, 532, 559, 587, 615, 644, 674, 704, 735, 767, 799, 832, 866, 900, 935, 971, 1007, 1044

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.

a(n) is also Malen and Roldán's h_{(n+2)^2}, the maximum number of holes in a polyomino which is contained in the square of side length n+2. Indeed: without loss of generality, it can be assumed that such a polyomino includes all cells next to the boundary of the square and that all holes are of size 1, and then the holes in the polyomino can be identified with the painted cells in the grid. - Andrei Zabolotskii, Feb 20 2026

Links

Table of n, a(n) for n=0..55.

Greg Malen and Érika Roldán, Topology and Geometry of Crystallized Polyominoes, arXiv:1910.10342 [math.CO], 2019.

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).

Prog

(Python)
def a(n): # Malen and Roldán, Theorem 2.1
    return (n+1)**2//3-1 if n%3==2 else n*(n+2)//3 - ((n+1).bit_count()>1) # Andrei Zabolotskii, Feb 20 2026

Crossrefs

Cf. A239231, a similar sequence, with one extra criterion - that the unpainted cells should be contiguous.

Sequence in context: A032616 A006066 A084935 * A317242 A217302 A062409

Adjacent sequences: A239069 A239070 A239071 * A239073 A239074 A239075

Keyword

nonn

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

Terms a(26) and beyond from Andrei Zabolotskii, Feb 20 2026

Status

approved