1,2

The entries a(1)=1, a(2)=3, a(8)=15, a(15)=36, a(16)=39, a(17)=43, a(19)=50, a(20)=54, a(21)=58, a(22)=62, a(23)=66, a(25)=75, a(27)=84, a(29)=93, a(30)=98, a(31)=103, a(35)=123, a(36)=128, a(37)=133, a(39)=144, a(41)=155, a(43)=166, a(44)=172,

a(45)=178, a(46)=184, a(49)=202, a(50)=208, a(51)=214, a(54)=233, a(56)=246, a(62)=286, a(63)=293, a(64)=300, a(65)=307, a(76)=387, a(90)=498 and a(94)=531 all meet the lower bound in A092137 and are therefore correct. [Comment updated by Stuart Anderson (stuart(AT)squaring.net), Jan 05 2008]

The values a(3)=5, a(4)=7, a(5)=9, a(6)=11, a(7)=13 are correct, since it can be shown that the size of smallest square that contains two squares of sides a and b is a+b. As a consequence A060747(n)=2n-1 is a lower bound for a(n). - Dan Dima (dimad72(AT)gmail.com), Jan 28 2007

This problem has a long history and the people credited in Ed Pegg's description (including myself) are not the first to find the packings that he attributes. The values given are upper bounds and conjectured values and have been proved except those for n=26, 28, 32, 33, 34, 38, 40, 42, 47, 48, 52, 53 and 55, where they remain probable. Not only is 2n-1 a lower bound (sharp for n<=8), so is 3n-9 because of the 3rd, 4th and 5th smallest squares (sharp for 8n<=n<=16). - Erich Friedman (efriedma(AT)stetson.edu), Jul 17 2007

Comment from Erich Friedman, May 27 2009: Simonis, H. and O'Sullivan show that a(26) = 80. The first first unknown value is now a(28), though the answer is almost surely 89.

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

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.

Erich Friedman, Math Magic.

Shigeyoshi Kamakura, Illustration for n = 23

Minami Kawasaki, Illustration for n = 19

Minami Kawasaki, Illustration for n = 22

Minami Kawasaki, Catalogue of known solutions

Ed Pegg Jr, Illustration for n = 25, 27, 29, 30, 31, 35

Ed Pegg Jr, Illustration for n = 37

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 (Rob.Pratt(AT)sas.com), Jun 10 2009]

75^2 - Sum[n^2, {n, 1, 25}] == 100 Solvable - Erich Friedman

79^2 - Sum[n^2, {n, 1, 26}] == 40 Highly unlikely

84^2 - Sum[n^2, {n, 1, 27}] == 126 Solvable - Robert Reid

88^2 - Sum[n^2, {n, 1, 28}] == 30 Highly unlikely

93^2 - Sum[n^2, {n, 1, 29}] == 94 Solvable - Ed Pegg Jr

98^2 - Sum[n^2, {n, 1, 30}] == 149 Solvable - Robert Reid

103^2 - Sum[n^2, {n, 1, 31}] == 193 Solvable - RR and EF

107^2 - Sum[n^2, {n, 1, 32}] == 9 Very highly unlikely

112^2 - Sum[n^2, {n, 1, 33}] == 15 Very highly unlikely

117^2 - Sum[n^2, {n, 1, 34}] == 4 Very highly unlikely

123^2 - Sum[n^2, {n, 1, 35}] == 219 Solvable - Erich Friedman

128^2 - Sum[n^2, {n, 1, 36}] == 178 Likely hand-solvable

Cf. A092137 (lower bound).

Sequence in context: A137507 A061808 A143450 this_sequence A081110 A143449 A033034

Adjacent sequences: A005839 A005840 A005841 this_sequence A005843 A005844 A005845

nonn

N. J. A. Sloane (njas(AT)research.att.com), R. K. Guy

a(25)-a(36) reported by Ed Pegg Jr. (ed(AT)mathpuzzle.com), Jan 04 2004

a(23) = 66 from Shigeyoshi Kamakura, Mar 29 2004

a(37) = 133, solved independently by Robert Reid and Berend Jan van der Zwaag, Mar 30 2004

It is not clear which of these entries have been proved to be correct. At the present time they should all be regarded as conjectures unless indicated otherwise. N. J. A. Sloane (njas(AT)research.att.com), Mar 30 2004. Entry revised Apr 06 2004.

More terms from Erich Friedman (efriedma(AT)stetson.edu), Jul 17 2007

Corrected a comment on a lower bound. - Jon E. Schoenfield (jonscho(AT)hiwaay.net), Nov 19 2008