Squaring rectangles it is a nice high-school exercise to prove that a square can be tiled with n squares if and only if n=1, 4 or is any integer greater or equal to 6. A direct consequence is that any rectangle that can be tiled with n squares can be tiled as well with n+3 squares and any number of squares that is greater or equal to n+5.
A result of Dehn (not trivial) asserts that a rectangle can be tiled with finitely many squares if and only if it has integer lengths. Let R be such a rectangle and let m denote the least number of squares needed for a tiling of R. As we have already seen, R can be tiled with m+3 squares and any number greater or equal to m+5. Then there can be at most 6 classes of rectangles :


*

*those that cannot be tiled with any other number of squares,

*those that can be tiled with m+1 and m+4 squares,

*those that can be tiled with m+2 squares,

*those that can be tiled with m+1, m+2 and m+4 squares,

*those that can be tiled with m+2 and m+4 squares,

*those that can be tiled with m+4 squares.


It seems that any of these classes is not empty. However, it is not so easy to compute the class of a given rectangle (at least for me!). So my first question is about the existence of such an algorithm?
I feel that the first class contains all rectangles whose lengths are of the form (1,n) ; (2,2n+1) and (3,3n+2) and I don't know if there are others. Is it possible to determine all the rectangles of a class, or at least some subclasses in it?
So far, I have not found where this problem would have been studied before; all I know is some articles dealing with an asymptotic behavior of m with respect of the lengths of R. Please feel free to add any useful comment on this topic!
 A: Many of the minimal squarings can be found at Minimally Squared Rectangles.  
For $n \times (n+1)$ rectangles, the smallest rectangles requiring 4 to 13 squares are $3 \times 4$, $4 \times 5$, $9 \times 10$, $7 \times 8$, $16 \times 17$, $19 \times 20$, $44 \times 45$, $69 \times 70$, $113 \times 114$, and $179 \times 180$.
Here's the plot of minimal squares for an oblong rectangle.

An rectangle $R$ with minimal squaring $m$ isn't necessarily divisible into $m+3$ squares by the easy method. For a $61 \times 58$ rectangle, you'd need to go up to a $122 \times 116$ rectangle to use the easy method.

Once you get to this size, though, there are many tricks.  Shave off two 29 squares, then a 32, then a 26, then four 6's, and three 2's remain, which is an 11 square solution.  It's not to hard to find a 12 square solution.
It was hard enough to build up these tables with just the minimal squarings, but it might be possible to build up second best, third best, and so on.  I suspect solutions for $m+1, m+2, m+3, m+4$ and so on will exist for sufficiently large rectangles.  But there will be lots of chaos. 
