A282939 Maximum number of straight lines required to draw the boundary of any polyomino with n squares.

0, 4, 4, 6, 8, 12, 12, 14, 16, 20, 20, 22, 24, 28, 28, 30, 32, 36, 36, 38, 40, 44, 44, 46, 48, 52, 52, 54, 56, 60, 60, 62, 64, 68, 68, 70, 72, 76, 76, 78, 80, 84, 84, 86, 88, 92, 92, 94, 96, 100, 100, 102, 104, 108, 108, 110, 112

Offset

0,2

Comments

For n >= 7, polyominoes can have holes whose boundaries are also included.

An n-omino in the shape of a "staircase" has 2n boundary edges, so a(n) >= 2n.

If we "join" copies of the X pentomino (sharing one square) then we can do better than the above lower bound. This gives us a(4k+1) >= 8k+4, for any k >= 0.

It appears that a(n) = 2*n+2 for n (mod 4) == 1, otherwise a(n) = 2*n, which coincides with the lower bounds above. - Lars Blomberg, Nov 09 2017

The conjecture that a(n) = 2*n+2 for n (mod 4) == 1, otherwise a(n) = 2*n, is proven. See link. - John Mason, Jun 08 2021

Links

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

John Mason, Proof of conjecture

Example

For n=1, we have the monomino (single square), so a(1)=4.
For n=2, we have the domino, so a(2)=4.
For n=3, we have the L tromino, so a(3)=6.
For n=4, we have the T and S tetrominoes, so a(4)=8.
For n=5, we have the X pentomino, so a(5)=12.

Crossrefs

Sequence in context: A338895 A090682 A011982 * A175216 A053639 A100090

Adjacent sequences: A282936 A282937 A282938 * A282940 A282941 A282942

Keyword

nonn

Author

Dmitry Kamenetsky, Feb 25 2017

Extensions

a(7)-a(19) from Lars Blomberg, Nov 09 2017

Status

approved