A276523 - OEIS

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, 14

(list; graph; refs; listen; history; text; internal format)

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 1 X 2 rectangle and a 2 X 4 rectangle (these are similar), but there can't be two 1 X 2 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)

Best known values for a(67)-a(96) as follows (values with * are optimal): 16, 16*, 16*, 15*, 18, 16*, 16*, 15*, 16*, 18, 17, 14*, 16, 18, 17, 18, 16*, 16*, 16*, 18, 22, 18, 19, 20, 17, 20, 22, 20, 20, 24. - Mia Muessig, Nov 19 2025

LINKS

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

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

Mia Muessig, Best known tilings for n=66..96

Mia Muessig, Interactive Mondrian Art Editor

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

cccdddddddbbbb

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, Dec 21 2016

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

a(66) from Mia Muessig, Nov 19 2025

STATUS

approved