A005842 a(n) = minimal integer m such that an m X m square contains non-overlapping squares of sides 1, ..., n (some values are only conjectures).

1, 3, 5, 7, 9, 11, 13, 15, 18, 21, 24, 27, 30, 33, 36, 39, 43, 47, 50, 54, 58, 62, 66, 71, 75, 80, 84, 89, 93, 98, 103, 108, 113, 118, 123, 128, 133, 139, 144, 150, 155, 161, 166, 172, 178, 184, 190, 196, 202, 208, 214, 221, 227, 233, 240, 246

Offset: 1

Author

N. J. A. Sloane, R. K. Guy

Keywords

• nonn

Comments

The entries for n=1, 2, 8, 15, 16, 17, 19, 20, 21, 22, 23, 25, 27, 29, 30, 31, 35, 36, 37, 39, 41, 43, 44, 45, 46, 49, 50, 51, 54, and 56 all meet the lower bound in A092137 and are therefore correct. - Stuart E Anderson, Jan 05 2008

Simonis, H. and O'Sullivan showed that a(26) = 80. - Erich Friedman, May 27 2009

Houhardy S. showed a(32)=108, a(33)=113, a(34)=118, and a(47)=190. - Erich Friedman, Oct 11 2010

The values have been proved correct except those for n=38, 40, 42, 48, 52, 53 and 55, where they remain probable. - Erich Friedman, Oct 11 2010

References

• H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, D5.
• M. Gardner, Mathematical Carnival. Random House, NY, 1977, p. 147.
• Simonis, H. and O'Sullivan, B., Search Strategies for Rectangle Packing, in Proceedings of the 14th international conference on Principles and Practice of Constraint Programming, Springer-Verlag Berlin, Heidelberg, 2008, pp. 52-66.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• János Balogh, György Dósa, Lars Magnus Hvattum, Tomas Olaj, and Zsolt Tuza, Guillotine cutting is asymptotically optimal for packing consecutive squares, Optimization Letters (2022).
• János Balogh, György Dósa, Lars Magnus Hvattum, Tomas Attila Olaj, Istvan Szalkai, and Zsolt Tuza, Covering a square with consecutive squares, Ann. Oper. Res. (2025).
• Erich Friedman, Math Magic.
• S. Hougardy, A Scale Invariant Algorithm for Packing Rectangles Perfectly, 2012. - From _N. J. A. Sloane_, Oct 15 2012
• S. Hougardy, A Scale Invariant Exact Algorithm for Dense Rectangle Packing Problems, 2012.
• Minami Kawasaki, Catalogue of best known solutions
• R. E. Korf, Optimal Rectangle Packing: New Results, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS04), Whistler, British Columbia, June 2004, pp. 142-149. [From _Rob Pratt_, Jun 10 2009]
• Takehide Soh, Packing Consequtive Squares into a Sqaure (sic), Kobe University (Japan, 2019).

Crossrefs

Cf. A092137 (lower bound).