Minimum number of integer-sided squares needed to tile an $m$ by $n$ rectangle.

Let $T(m,n)$ for integers $m,n$ be the least number of integer-sided squares needed to tile an $m\times n$ rectangle. Clearly $T(kx,ky)\leq T(x,y)$. Are there integers $x,y,k\gt 1$, such that $T(kx,ky)<T(x,y)$?


$T(m,n)$ is tabulated at the OEIS. Also, several references are given:

Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.

Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921.

Bertram Felgenhauer, Tiling rectangles by minimal number of squares.

Maybe you could have a look at those, to see whether your question is considered (and, if it is, you could then report back).


I've posted a 4944 possible counterexamples at Possible Counterexamples to the Minimal Squaring Conjecture. Odds are at least one of these is a valid counterexample.

Data and verified pictures up to 388 at Minimally Squared Rectangles

possible counterexample

Other information at tiling a rectangle with the smallest number of squares

According to my notes there, my minimal possible counterexample is currently

enter image description here


Here's the Bouwkamp code of two simple perfect squared rectangles:

  • 13: 304x274 (141,78,85)(71,7)(92)(133,8)(51,28)(23,97)(74);
  • 15: 152x137 (83,69)(31,38)(54,29)(16,15)(8,30)(25,4)(1,22)(21).

There is no lower-order simple squared rectangle of either size, but there might be compound ones. If not then T(304,274) = 13, T(152,137) = 15, and T(304,274) < T(152,137).