A276523 Partition an n X n square into multiple non-congruent integer-sided rectangles. a(n) is the least possible difference between the largest and smallest area.

2, 4, 4, 5, 5, 6, 6, 8, 6, 7, 8, 6, 8, 8, 8, 8, 8, 9, 9, 9, 8, 9, 10, 9, 10, 9, 9, 11, 11, 10, 12, 12, 11, 12, 11, 10, 11, 12, 13, 12, 12, 12, 13, 13, 12, 14, 12, 13, 14, 13, 14, 15, 14, 14, 15, 15, 14, 15, 15, 14, 15, 15, 15

Offset

3,1

Comments

Developed as the Mondrian Art Puzzle.

The rectangles can be similar, though. - Daniel Forgues, Nov 22 2016

That is, there can be a 1x2 rectangle and a 2x4 rectangle (these are similar), but there can't be two 1x2 rectangles (these are congruent). - Michael B. Porter, Oct 13 2018

Upper bounds for a(n) are n if n is odd, and min(2*n, 4 * a(n/2)) if n is even. - Roderick MacPhee, Nov 28 2016

An upper bound seems to be ceiling(n/log(n))+3, or A050501+3. See A278970. Holds to at least a(96). - Ed Pegg Jr, Dec 02 2016

Best known values for a(66)-a(96) as follows: 16, 18, 19, 18, 19, 18, 20, 20, 20, 20, 19, 20, 21, 21, 20, 21, 20, 20, 21, 22, 18, 22, 20, 22, 24, 23, 22, 22, 24, 24, 24. - (shortened by Ruud H.G. van Tol, Oct 25 2024)

Links

Table of n, a(n) for n=3..65.

Michel Gaillard, Optimal tilings for n=58..65

Robert Gerbicz, Optimal tilings for n=3..57

Gordon Hamilton, Mondrian Art Puzzles (2015).

Gordon Hamilton and Brady Haran, Mondrian Puzzle, Numberphile video (2016)

Mersenneforum.org puzzles, Mondrian art puzzles

Cooper O'Kuhn, The Mondrian Puzzle: A Connection to Number Theory, arXiv:1810.04585 [math.CO], 2018.

Cooper O'Kuhn and Todd Fellman, The Mondrian Puzzle: A Bound Concerning the M(n)=0 Case, arXiv:2006.12547 [math.NT], 2020. See also Integers (2021) Vol. 21, #A37.

Ed Pegg Jr, Mondrian Art Problem.

Example

A size-11 square can be divided into 3 X 4, 2 X 6, 2 X 7, 3 X 5, 4 X 4, 2 X 8, 2 X 9, and 3 X 6 rectangles. 18 - 12 = 6, the minimal area range.
The 14 X 14 square can be divided into non-congruent rectangles of area 30 to 36:
  aaaaaaaaaabbbb
  aaaaaaaaaabbbb
  aaaaaaaaaabbbb
  cccdddddddbbbb
  cccdddddddbbbb
  cccdddddddbbbb
  cccdddddddbbbb
  cccdddddddbbbb
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff

Crossrefs

Cf. A050501, A278970, A279596.

Sequence in context: A036437 A053306 A108422 * A244320 A084616 A196259

Adjacent sequences: A276520 A276521 A276522 * A276524 A276525 A276526

Keyword

nonn,hard,more

Author

Ed Pegg Jr, Nov 15 2016

Extensions

Bruce Norskog corrected a(18), and a recheck by Pegg corrected a(15) and a(19). - Charles R Greathouse IV, Nov 28 2016

Correction of a(14), a(16), a(23) and new terms a(25)-a(28) from Robert Gerbicz, Nov 28 2016

a(29)-a(44) from Robert Gerbicz, Dec 02 2016

a(45)-a(47) from Robert Gerbicz added, as well as best known values to a(96).

Correction of a(45), a(46) and new terms a(48)-a(57) from Robert Gerbicz, Dec 27 2016

a(58)-a(65) from Michel Gaillard, Oct 23 2020

Status

approved