The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A355477 Maximum number of skew-tetrominoes that can be packed into an n X n square. 1
 0, 0, 1, 3, 4, 8, 9, 14, 16, 23, 25, 33, 36, 46, 49, 60, 64, 77, 81, 96, 100 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS Skew-tetrominoes are tiles of the form: ___ |_ |_ |___| together with all rotations/reflections of this shape. It is not hard to see that skew-tetrominoes cannot completely tile an n X n square, so a(n) < n^2/4. The odd terms are easily understood: a(2m+1) = m^2. 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. 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. 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). Additional terms: (Lower bounds are from explicit constructions; upper bounds are from mixed-integer-programming search.) a(22) in {116, 117}. a(23) = 121. a(24) = 139. a(25) = 144. a(26) in {163, 164}. a(27) = 169. a(28) in {190, 191}. a(29) = 196. a(30) in {218, 219, 220}. a(31) = 225. a(32) in {248, 249, 250, 251}. a(33) = 256. a(34) in {280, 281, 282, 283}. a(35) = 289. a(36) in {316, 317, 318}. a(37) = 324. a(38) in {352, 353, 354, 355}. a(39) = 361. a(40) in {388, 389, 390, 391, 392, 393, 394}. a(41) = 400. a(42) in {432, 433, 434}. LINKS Table of n, a(n) for n=1..21. Alexander D. Healy, Examples of (near-)optimal packings for n <= 42 Wikipedia, Tetromino FORMULA a(n) < n^2/4. a(2m+1) = m^2. EXAMPLE a(8) = 14 by the following packing of 14 skew-tetrominoes into an 8 X 8 square: _______________ |_|1 _| |___| |_| |___| 2_|3 _|_4 | |_ 5|_|___| | |_| | |___| | 6_|_7 | |_8 | 9_|_|_10|_| | |_|_|11_| |___| |_12|___|13_|14_| |_|_|___|_|___|_| CROSSREFS Cf. A256535. Sequence in context: A047204 A050035 A306901 * A341578 A046974 A177986 Adjacent sequences: A355474 A355475 A355476 * A355478 A355479 A355480 KEYWORD nonn,more,changed AUTHOR Alexander D. Healy, Jul 03 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 22 08:04 EDT 2023. Contains 365519 sequences. (Running on oeis4.)