login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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).
(Formerly M2401)
3

%I M2401 #45 Oct 14 2023 13:27:17

%S 1,3,5,7,9,11,13,15,18,21,24,27,30,33,36,39,43,47,50,54,58,62,66,71,

%T 75,80,84,89,93,98,103,108,113,118,123,128,133,139,144,150,155,161,

%U 166,172,178,184,190,196,202,208,214,221,227,233,240,246

%N 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).

%C 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

%C Simonis, H. and O'Sullivan showed that a(26) = 80. - _Erich Friedman_, May 27 2009

%C Houhardy S. showed a(32)=108, a(33)=113, a(34)=118, and a(47)=190. - _Erich Friedman_, Oct 11 2010

%C 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

%D H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, D5.

%D M. Gardner, Mathematical Carnival. Random House, NY, 1977, p. 147.

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H János Balogh, György Dósa, Lars Magnus Hvattum, Tomas Olaj, and Zsolt Tuza, <a href="https://doi.org/10.1007/s11590-022-01858-w">Guillotine cutting is asymptotically optimal for packing consecutive squares</a>, Optimization Letters (2022).

%H Erich Friedman, <a href="https://erich-friedman.github.io/mathmagic/1099.html">Math Magic</a>.

%H S. Hougardy, <a href="http://contraintes.inria.fr/BPPC/BPPC12papers/submissions/bppc12_submission_1.pdf">A Scale Invariant Algorithm for Packing Rectangles Perfectly</a>, 2012. - From _N. J. A. Sloane_, Oct 15 2012

%H S. Hougardy, <a href="http://www.or.uni-bonn.de/~hougardy/paper/PerfectRectanglePacking.pdf">A Scale Invariant Exact Algorithm for Dense Rectangle Packing Problems</a>, 2012.

%H Minami Kawasaki, <a href="http://www.geocities.co.jp/Berkeley-Labo/6317/seqsqr_00.htm">Catalogue of best known solutions</a>

%H R. E. Korf, <a href="https://www.aaai.org/Papers/ICAPS/2004/ICAPS04-019.pdf">Optimal Rectangle Packing: New Results</a>, 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]

%H Takehide Soh, <a href="https://web.archive.org/web/20210123133356/http://www.cril.univ-artois.fr/XCSP19/files/sp.pdf">Packing Consequtive Squares into a Sqaure</a> (sic), Kobe University (Japan, 2019).

%Y Cf. A092137 (lower bound).

%K nonn

%O 1,2

%A _N. J. A. Sloane_, _R. K. Guy_

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 03:28 EDT 2024. Contains 371235 sequences. (Running on oeis4.)