cp's OEIS Frontend

A355477 Maximum number of skew-tetrominoes that can be packed into an n X n square.

%I A355477 #55 Sep 17 2023 01:29:18
%S A355477 0,0,1,3,4,8,9,14,16,23,25,33,36,46,49,60,64,77,81,96,100
%N A355477 Maximum number of skew-tetrominoes that can be packed into an n X n square.
%C A355477 Skew-tetrominoes are tiles of the form:
%C A355477    ___
%C A355477   |_  |_
%C A355477     |___|
%C A355477 together with all rotations/reflections of this shape.
%C A355477 It is not hard to see that skew-tetrominoes cannot completely tile an n X n square, so a(n) < n^2/4.
%C A355477 The odd terms are easily understood: a(2m+1) = m^2.
%C A355477 A straightforward (greedy) construction shows that m^2 skew-tetrominoes (all with the same orientation) can be packed into a (2m+1) X (2m) rectangle. Therefore a(2m+1) >= m^2.
%C A355477 On the other hand, we also have a(2m+1) <= m^2: Consider all cells with indices of the form (2i, 2j); there are m^2 such cells in a (2m+1) X (2m+1) square. Moreover, any valid placement of a skew-tetromino must cover one of these cells, so a(2m+1) <= m^2.
%C A355477 The behavior of a(2m) appears more subtle; the initial terms satisfy a(2m) = m^2 - floor(m/2), but this formula breaks down at a(20) = 96 (not 95).
%C A355477 Additional terms:
%C A355477 (Lower bounds are from explicit constructions; upper bounds are from mixed-integer-programming search.)
%C A355477 a(22) in {116, 117}.
%C A355477 a(23) = 121.
%C A355477 a(24) = 139.
%C A355477 a(25) = 144.
%C A355477 a(26) in {163, 164}.
%C A355477 a(27) = 169.
%C A355477 a(28) in {190, 191}.
%C A355477 a(29) = 196.
%C A355477 a(30) in {218, 219, 220}.
%C A355477 a(31) = 225.
%C A355477 a(32) in {248, 249, 250, 251}.
%C A355477 a(33) = 256.
%C A355477 a(34) in {280, 281, 282, 283}.
%C A355477 a(35) = 289.
%C A355477 a(36) in {316, 317, 318}.
%C A355477 a(37) = 324.
%C A355477 a(38) in {352, 353, 354, 355}.
%C A355477 a(39) = 361.
%C A355477 a(40) in {388, 389, 390, 391, 392, 393, 394}.
%C A355477 a(41) = 400.
%C A355477 a(42) in {432, 433, 434}.
%H A355477 Alexander D. Healy, <a href="/A355477/a355477.pdf">Examples of (near-)optimal packings for n <= 42</a>
%H A355477 Wikipedia, <a href="https://en.wikipedia.org/wiki/Tetromino">Tetromino</a>
%F A355477 a(n) < n^2/4.
%F A355477 a(2m+1) = m^2.
%e A355477 a(8) = 14 by the following packing of 14 skew-tetrominoes into an 8 X 8 square:
%e A355477    _______________
%e A355477   |_|1 _| |___| |_|
%e A355477   |___| 2_|3 _|_4 |
%e A355477   |_ 5|_|___| | |_|
%e A355477   | |___| | 6_|_7 |
%e A355477   |_8 | 9_|_|_10|_|
%e A355477   | |_|_|11_| |___|
%e A355477   |_12|___|13_|14_|
%e A355477   |_|_|___|_|___|_|
%Y A355477 Cf. A256535.
%K A355477 nonn,more
%O A355477 1,4
%A A355477 _Alexander D. Healy_, Jul 03 2022