A279317 Minimal number of squares in a dissection of an (n) X (n+1) oblong into squares.

2, 3, 4, 5, 5, 5, 7, 7, 6, 6, 7, 7, 7, 7, 7, 8, 8, 7, 9, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 8, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 9, 9, 10, 9, 10, 9, 10, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 10, 10, 10, 10, 10, 10, 10, 11, 11, 10, 10, 10, 10, 10, 10, 11, 10, 11, 10, 11, 10, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11, 12

Offset: 1

Author

Ed Pegg Jr, Dec 09 2016

Keywords

• nonn
• hard

Comments

This is very close to b(n) = round(n^(1/3)) + 6. b(18)-a(18) = 2. b(387)-a(387) = 0. All b(n)-a(n) terms in between these points are -1, 0, 1.

Bouwkamp codes of dissections that are believed to be optimal follow.

10 105 104 60 45 19 26 44 16 12 7 33 28

11 177 176 99 78 21 57 77 43 16 41 34 9 25

12 308 307 165 143 22 67 54 142 45 13 41 97 28 69

13 552 551 312 240 44 60 136 28 16 76 239 101 37 175 138

14 970 969 546 424 172 252 423 73 50 23 119 80 96 39 293 254

15 1699 1698 951 748 307 441 747 127 77 50 27 200 134 177 66 509 443

16 2926 2925 1633 1293 213 299 781 127 86 41 344 1292 509 206 138 68 851 783

17 5211 5210 2846 2365 571 518 1276 2364 392 90 53 465 302 412 694 584 293 1569 1278

18 8731 8730 4741 3990 751 1195 2044 3989 1059 444 790 849 884 175 709 256 197 2696 453 2046

19 15131 15130 8169 6962 2415 4547 6961 1208 1943 1680 263 965 452 1504 702 1378 3621 802 865 2306 2243

20 25679 25678 13719 11960 1456 1866 2626 6012 303 743 410 11959 1623 440 1516 760 1183 3386 4322 1692 7706 6014

21 49583 49582 27252 22331 4763 5036 12532 158 4332 273 22330 5080 5309 906 2176 1250 4716 1270 4372 2187 3446 14719 12534

Examples

			Oblong 18 X 19 uses 7 squares of size 3, 5, 5, 7, 7, 8, 11.
Oblong 34 X 35 uses 8 squares of size 4, 7, 9, 9, 11, 15, 16, 19.
Oblong 55 X 56 uses 9 squares of size 5, 9, 12, 12, 14, 19, 23, 24, 32.
Oblong 104 X 105 uses 10 squares of size 7, 12, 16, 19, 26, 28, 33, 44, 45, 60.
From _Peter Kagey_, Dec 13 2016: (Start)
An example of the a(10) = 6 squares that can dissect a 10 X 11 oblong:
  +-------+-----------+
  |       |           |
  |   4   |           |
  |       |     6     |
  +---+---+           |
  | 2 | 2 |           |
  +---+---+-+---------+
  |         |         |
  |    5    |    5    |
  |         |         |
  |         |         |
  +---------+---------+
(End)
		

Links

• Ed Pegg Jr, Table of n, a(n) for n = 1..387
• S. Anderson, Catalogues of Simple Perfect Squared Rectangles (SPSR)
• B. Felgenhauer, Filling Rectangles with Integer-Sided Squares.
• Ed Pegg Jr, Minimally Squared Rectangles.
• Ed Pegg Jr on StackExchange, Oblongs into minimal squares, Dec 13 2016.

Crossrefs

Cf. A005670, A339548.

Extensions

Corrected term 351 and extended to n=387 by Ed Pegg Jr, Oct 31 2018