# tiling a rectangle with the smallest number of squares

This is based on another thread. For $m,n\in \mathbb N$, let $f(m,n)$ be the minimum number of squares with integer sides needed to tile a $m\times n$ rectangle. Recently, a table of values for $n\le m\le 85$, obtained by what seems to be a brute force search, has been put online here.

The table looks quite fuzzy, but if we restrict it to values of coprime $m,n$ such that $2n\ge m\ge n$, there is surprisingly little fluctuation. For convenience, the following table gives $f(m,n)$ in reverse order, showing in row $n$ the values for $n=m-1,m-2,...,\lbrace n/2\rbrace$ but putting "o" wherever $(m,n)>1$.

(The number following $m$ is $g(m):=\frac{\log(m\sqrt{5})}{\log(\phi)}$ where $\phi=\frac{\sqrt{5}+1}2$, see below.)

 3 :  3.955  [ 3]
4 :  4.553  [ 4]
5 :  5.016  [ 5, 4]
6 :  5.395  [ 5, o]
7 :  5.716  [ 5, 5, 5]
8 :  5.993  [ 7, o, 5]
9 :  6.238  [ 7, 6, o, 6]
10 :  6.457  [ 6, o, 6, o]
11 :  6.655  [ 6, 7, 6, 6, 6]
12 :  6.836  [ 7, o, o, o, 6]
13 :  7.002  [ 7, 6, 7, 7, 6, 6]
14 :  7.156  [ 7, o, 7, o, 7, o]
15 :  7.299  [ 7, 8, o, 7, o, o, 8]
16 :  7.433  [ 7, o, 8, o, 7, o, 7]
17 :  7.559  [ 8, 8, 7, 8, 7, 7, 7, 8]
18 :  7.678  [ 8, o, o, o, 7, o, 7, o]
19 :  7.791  [ 7, 9, 7, 7, 7, 7, 7, 7, 7]
20 :  7.897  [ 9, o, 7, o, o, o, 7, o, 8]
21 :  7.999  [ 8, 7, o, 9, 8, o, o, 7, o, 7]
22 :  8.095  [ 8, o, 8, o, 8, o, 8, o, 8, o]
23 :  8.188  [ 8, 8, 8, 9, 8, 8, 8, 8, 8, 8, 8]
24 :  8.276  [ 8, o, o, o, 9, o, 8, o, o, o, 7]
25 :  8.361  [ 8, 8, 8, 8, o, 8, 8, 9, 8, o, 8, 8]
26 :  8.442  [ 8, o, 8, o, 8, o, 8, o, 9, o, 8, o]
27 :  8.521  [ 8,10, o, 8, 8, o, 8, 8, o, 8, 8, o, 8]
28 :  8.596  [ 8, o,10, o, 9, o, o, o, 8, o, 8, o, 8]
29 :  8.669  [ 9, 8, 8,10,10, 9, 9, 8, 9, 8, 8, 8, 9, 8]
30 :  8.740  [ 9, o, o, o, o, o, 9, o, o, o, 8, o, 9, o]
31 :  8.808  [ 8, 8, 8,10, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 8]
32 :  8.874  [ 9, o, 8, o, 8, o, 9, o, 9, o, 8, o, 8, o, 9]
33 :  8.938  [ 9, 9, o, 9, 8, o, 8,10, o, 9, o, o, 8, 8, o, 9]
34 :  9.000  [ 9, o, 9, o, 9, o, 9, o, 8, o, 9, o, 8, o, 8, o]
35 :  9.060  [ 8, 9,10, 8, o, 9, o, 9, 8, o, 8, 9, 9, o, o, 8, 9]
36 :  9.119  [ 9, o, o, o,10, o,10, o, o, o, 9, o, 9, o, o, o,10]
37 :  9.176  [ 9, 9, 9, 9, 8,10, 9, 8, 9, 9, 9, 9, 8, 9, 8, 9, 8, 8]
38 :  9.231  [ 9, o, 9, o, 9, o, 9, o,10, o, 9, o, 9, o, 9, o,10, o]
39 :  9.285  [ 9, 9, o, 9, 9, o,10, 9, o, 9, 9, o, o, 9, o, 9, 9, o, 9]
40 :  9.338  [ 9, o, 9, o, o, o, 9, o, 9, o, 8, o, 9, o, o, o, 9, o, 8]
41 :  9.389  [ 9, 9, 9, 9,11, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
42 :  9.439  [ 9, o, o, o, 9, o, o, o, o, o,10, o,10, o, o, o,10, o,10, o]
43 :  9.488  [ 9, 9, 9, 9, 9, 9,10,10, 9, 9, 9, 9, 9, 9, 9, 9,10, 9, 9, 9, 9]
44 :  9.536  [ 9, o, 9, o, 9, o, 9, o, 9, o, o, o, 9, o, 9, o, 9, o, 9, o, 9]
45 :  9.582  [10, 9, o,10, o, o, 9, 9, o, o, 9, o, 9, 9, o,10, 9, o, 9, o, o, 9]
46 :  9.628  [ 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o]
47 :  9.673  [ 9, 9, 9,11, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,10, 9, 9, 9, 9, 9, 9, 9, 9]
48 :  9.716  [10, o, o, o, 9, o, 9, o, o, o,10, o,10, o, o, o, 9, o, 9, o, o, o, 9]
49 :  9.759  [ 9, 9, 9, 9,10,10, o, 9, 9, 9, 9, 9, 9, o, 9,10,10, 9, 9,10, o, 9, 9, 9]
50 :  9.801  [10, o, 9, o, o, o, 9, o, 9, o, 9, o, 9, o, o, o, 9, o, 9, o, 9, o, 9, o]
51 :  9.842  [ 9,10, o, 9,10, o,10, 9, o,10,10, o, 9,10, o, 9, o, o, 9,10, o,10,10, o, 9]
52 :  9.883  [10, o,11, o, 9, o,10, o,10, o, 9, o, o, o, 9, o,10, o, 9, o, 9, o,10, o,11]
53 :  9.922  [10, 9, 9,11, 9,10,10, 9,10,11,10, 9,10, 9,10,10,11,10, 9, 9, 9, 9, 9,11,11, 9]
54 :  9.961  [10, o, o, o, 9, o,10, o, o, o, 9, o, 9, o, o, o, 9, o, 9, o, o, o, 9, o,10, o]
55 :  9.999  [10,10,10,10, o, 9, 9, 9, 9, o, o, 9,10, 9, o, 9, 9, 9,10, o, 9, o,10, 9, o, 9, 9]
56 :  10.03  [ 9, o, 9, o,10, o, o, o, 9, o,10, o,11, o,10, o,10, o, 9, o, o, o,10, o, 9, o, 9]
57 :  10.07  [10,10, o,10, 9, o,10,10, o,10, 9, o, 9,10, o,10,10, o, o, 9, o,10, 9, o,10, 9, o,10]
58 :  10.11  [10, o,10, o,10, o,10, o,10, o,11, o,10, o,10, o,10, o,11, o,10, o,10, o,10, o,10, o]
59 :  10.14  [10,10, 9, 9,10,11, 9, 9, 9,10,10, 9, 9,10, 9, 9, 9,10, 9, 9,10, 9,10, 9, 9, 9, 9, 9,10]
60 :  10.18  [10, o, o, o, o, o,11, o, o, o,10, o,10, o, o, o,11, o, 9, o, o, o,10, o, o, o, o, o, 9]
61 :  10.21  [10, 9,10,10,10,10, 9, 9,10,10, 9,11,10,10,10,10, 9, 9,10,10, 9,10, 9, 9,10, 9,10, 9, 9, 9]
62 :  10.24  [10, o,10, o,10, o,10, o,10, o,10, o,11, o,11, o,10, o,11, o,10, o,10, o,10, o,10, o,10, o]
63 :  10.28  [10,10, o,10,10, o, o,10, o,10,10, o,10, o, o,10,10, o,10,10, o,10,10, o,10,10, o, o,10, o,10]
64 :  10.31  [10, o,10, o,10, o,10, o,11, o,11, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10]
65 :  10.34  [10,10,10,10, o,10,10,10,10, o,10,10, o,10, o,11,10,10,10, o,10,10,10,10, o, o,10,10,11, o,10,10]
66 :  10.37  [10, o, o, o,10, o,10, o, o, o, o, o,10, o, o, o, 9, o,10, o, o, o,10, o,10, o, o, o, 9, o, 9, o]
67 :  10.40  [10,10,10,10,10,10,11,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,10]
68 :  10.44  [10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o, o, o,10, o,10, o,10, o,10, o,10, o,10, o,11, o,10]
69 :  10.47  [10,10, o,10,11, o,10, 9, o,10,10, o,10,11, o,11,11, o,10,11, o,10, o, o,10,10, o, 9, 9, o,10, 9, o, 9]
70 :  10.50  [11, o,10, o, o, o, o, o,10, o,10, o,10, o, o, o,11, o,10, o, o, o,10, o, o, o,10, o,10, o,10, o,10, o]
71 :  10.53  [10,10,10,12,10,10,10,10,10,11,10,12,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10]
72 :  10.55  [10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10]
73 :  10.58  [10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
74 :  10.61  [10, o,10, o,10, o,10, o,10, o,10, o,11, o,11, o,10, o,11, o,10, o,10, o,10, o,10, o,11, o,10, o,10, o,10, o]
75 :  10.64  [10,11, o,10, o, o,10,10, o, o,10, o,10,10, o,10,10, o,10, o, o,10,11, o, o,10, o,10,10, o,10,10, o,10, o, o,10]
76 :  10.67  [10, o,10, o,10, o,11, o,10, o,10, o,10, o,10, o,10, o, o, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10]
77 :  10.69  [10,10,10,10,10,11, o,10,10,12, o,10,11, o,10,11,12,10,10,10, o, o,10,12,12,10,10, o,10,10,10,10, o,10, o,12,10,10]
78 :  10.72  [11, o, o, o,10, o,10, o, o, o,10, o, o, o, o, o,11, o,10, o, o, o,11, o,11, o, o, o,11, o,10, o, o, o,11, o,10, o]
79 :  10.75  [11,10,10,11,11,10,10,10,10,11,11,10,10,10,10,10,10,11,10,10,10,10,10,10,10,10,11,11,10,10,10,11,10,10,10,11,10,10,10]
80 :  10.77  [10, o,10, o, o, o,10, o,10, o,12, o,10, o, o, o,10, o,11, o,11, o,10, o, o, o,10, o,11, o,10, o,10, o, o, o,10, o,10]
81 :  10.80  [10,10, o,12,11, o,10,10, o,10,10, o,10,12, o,10,10, o,10,10, o,10,10, o,10,10, o,11,11, o,10,11, o,10,10, o,10,10, o,10]
82 :  10.82  [10, o,11, o,11, o,11, o,10, o,11, o,11, o,10, o,10, o,11, o,10, o,10, o,10, o,10, o,11, o,10, o,11, o,10, o,10, o,10, o]
83 :  10.85  [10,10,10,10,10,11,10,10,10,10,10,10,10,10,11,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,10,10,10]
84 :  10.87  [10, o, o, o,10, o, o, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,11, o,10, o, o, o,10, o,10, o, o, o, o, o,10, o, o, o,10]
85 :  10.90  [10,10,11,10, o,12,11,10,10, o,10,12,10,10, o,11, o,10,10, o,10,11,11,10, o,10,11,11,10, o,10,10,10, o, o,10,11,10,10, o,10,10]


For a Fibonacci rectangle, we obviously have $f(F_{k+1},F_k)\le k$, and it seems straightforward to show that this bound is sharp. But is this really trivial?

It looks like under the above restrictions on $m$ and $n$, the values of $f(m,n)$ are very close to $g(m)$, more precisely $$\boxed{\lfloor g(m)\rfloor -1\le f(m,n)\le \lceil g(m)\rceil +1}.$$ Is it possible that in the minimal tilings, patterns like in a 'Fibonacci rectangle tiling' occur frequently?

Note that it is already known or at least plausible from the article quoted in the first thread that $f(m,n)\sim g(m)$.

What about $f(m,n)$ if the rectangle sides are not coprime? Obviously $f(km,kn)\le f(m,n)$ for $k\in \mathbb N$. In the range of the table, there is equality everywhere.

Is anything known concerning the conjecture $f(km,kn)= f(m,n)$?

Moreover, does there even exist a minimal tiling of a $km\times kn$ rectangle such that not all square sides are multiples of $k$?

For $m> n$, let’s call a $m\times n$ rectangle reducible if $f(m,n)=f(n,m-n)+1$. This means there is a minimal tiling such that the biggest square has side $n$. (There may exist other minimal tilings also, though I'd rather doubt it).

Using the same order as above, I have kept in row $m$ only those $n$’s for which the $m\times n$ rectangle is reducible and put "o" where it is not:

 3 : [ 2]
4 : [ 3]
5 : [ 4, 3]
6 : [ o, 4]
7 : [ o, 5, 4]
8 : [ o, 6, 5]
9 : [ o, 7, 6, 5]
10 : [ o, 8, 7, 6]
11 : [ o, 9, 8, 7, 6]
12 : [ o, o, 9, 8, 7]
13 : [ o, o,10, 9, 8, 7]
14 : [ o, o,11,10, 9, 8]
15 : [ o, o,12,11,10, 9, 8]
16 : [ o, o,13,12,11,10, 9]
17 : [ o, o, o,13,12,11,10, 9]
18 : [ o, o, o,14,13,12,11,10]
19 : [ o, o, o, o, o,13,12,11,10]
20 : [ o, o, o,16,15,14,13,12,11]
21 : [ o, o, o,17,16,15,14,13,12,11]
22 : [ o, o, o,18,17,16, o,14,13,12]
23 : [ o, o, o,19,18,17,16, o,14,13,12]
24 : [ o, o, o, o,19,18,17,16,15,14,13]
25 : [ o, o, o, o,20,19,18,17,16,15,14,13]
26 : [ o, o, o, o, o,20,19,18,17,16,15,14]
27 : [ o, o, o, o, o,21,20,19,18,17,16,15,14]
28 : [ o, o, o, o,23,22,21,20,19,18,17,16, o]
29 : [ o, o, o, o,24,23, o,21,20,19,18,17,16,15]
30 : [ o, o, o, o, o,24,23,22,21,20,19,18,17,16]
31 : [ o, o, o, o, o, o, o, o, o,21,20,19,18,17,16]
32 : [ o, o, o, o, o,26,25,24,23,22,21,20,19,18,17]
33 : [ o, o, o, o, o,27, o,25,24,23,22,21,20,19,18,17]
34 : [ o, o, o, o, o, o,27,26, o,24,23,22,21,20,19,18]
35 : [ o, o, o, o, o, o,28,27, o,25,24,23,22,21,20,19,18]
36 : [ o, o, o, o, o, o, o,28,27,26,25,24,23,22,21,20,19]
37 : [ o, o, o, o, o,31, o, o,28,27,26,25,24,23, o,21,20,19]
38 : [ o, o, o, o, o, o, o, o,29, o,27,26,25,24,23,22,21,20]
39 : [ o, o, o, o, o, o,32, o,30,29,28,27,26,25,24,23,22,21, o]
40 : [ o, o, o, o, o, o, o,32, o,30, o,28,27,26,25,24,23,22,21]
41 : [ o, o, o, o, o, o, o, o, o,31,30,29, o,27,26,25,24,23,22,21]
42 : [ o, o, o, o, o, o, o,34,33,32,31,30,29,28,27,26,25,24,23,22]
43 : [ o, o, o, o, o, o, o,35, o, o,32,31, o,29,28,27,26,25, o,23,22]
44 : [ o, o, o, o, o, o, o,36, o,34,33,32,31, o,29,28,27,26,25,24,23]
45 : [ o, o, o, o, o, o, o, o,36,35, o,33,32,31,30,29,28,27,26,25,24,23]
46 : [ o, o, o, o, o, o, o,38, o,36,35,34,33,32,31, o,29,28,27,26,25,24]
47 : [ o, o, o, o, o, o, o, o, o, o, o, o,34,33,32,31, o,29,28,27,26,25,24]
48 : [ o, o, o, o, o, o, o, o,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25]
49 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,35,34,33,32,31,30,29,28,27,26,25]
50 : [ o, o, o, o, o, o, o, o, o,40, o,38,37,36,35,34, o,32,31,30,29,28,27,26]
51 : [ o, o, o, o, o, o, o, o, o,41,40,39, o,37,36,35,34,33,32,31,30,29,28,27,26]
52 : [ o, o, o, o, o, o, o, o, o, o, o,40,39,38, o,36,35,34,33,32,31,30,29,28,27]
53 : [ o, o, o, o, o, o, o, o, o,43, o, o,40, o,38,37,36,35,34,33,32,31, o,29,28,27]
54 : [ o, o, o, o, o, o, o, o, o, o, o,42, o,40,39,38,37,36,35,34,33,32,31,30, o,28]
55 : [ o, o, o, o, o, o, o, o, o,45,44, o, o, o,40, o, o,37, o,35,34,33,32,31,30,29,28]
56 : [ o, o, o, o, o, o, o, o, o,46, o,44,43,42,41,40,39,38,37,36,35,34,33,32,31, o,29]
57 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,43, o,41,40,39,38,37,36,35, o,33,32,31,30,29]
58 : [ o, o, o, o, o, o, o, o, o,48,47,46,45, o,43,42,41,40,39,38,37,36,35,34, o,32, o,30]
59 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,45, o, o, o,41,40, o, o,37,36,35,34,33,32,31,30]
60 : [ o, o, o, o, o, o, o, o, o, o, o,48,47,46,45,44,43,42, o,40,39,38,37,36,35,34,33,32,31]
61 : [ o, o, o, o, o, o, o, o, o, o, o,49, o,47,46, o, o, o, o,41,40,39, o,37,36,35,34,33,32,31]
62 : [ o, o, o, o, o, o, o, o, o, o, o, o,49, o,47, o,45, o,43,42,41,40,39,38,37,36,35,34,33,32]
63 : [ o, o, o, o, o, o, o, o, o, o, o,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32]
64 : [ o, o, o, o, o, o, o, o, o, o, o,52, o,50,49,48, o,46,45,44,43,42,41,40,39,38,37,36,35,34,33]
65 : [ o, o, o, o, o, o, o, o, o, o, o, o,52, o,50,49,48,47,46,45,44,43, o,41,40,39,38,37,36,35,34,33]
66 : [ o, o, o, o, o, o, o, o, o, o, o,54, o, o,51,50, o,48,47,46, o,44,43,42,41,40,39,38,37,36,35,34]
67 : [ o, o, o, o, o, o, o, o, o, o, o,55, o, o, o,51, o,49,48,47,46,45,44,43, o,41,40,39,38,37, o, o,34]
68 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,54, o,52,51, o,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35]
69 : [ o, o, o, o, o, o, o, o, o, o, o,57, o,55,54,53,52,51,50,49,48,47,46, o,44, o,42, o,40,39,38,37,36,35]
70 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,56,55,54, o, o,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36]
71 : [ o, o, o, o, o, o, o, o, o, o, o,59, o, o, o,55,54, o,52, o,50,49,48,47,46,45,44,43, o,41,40,39,38,37,36]
72 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,57,56, o,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37]
73 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,55,54,53,52, o,50,49,48,47,46,45,44,43, o,41,40,39,38,37]
74 : [ o, o, o, o, o, o, o, o, o, o, o,62, o, o,59, o, o,56, o,54,53,52, o,50,49,48,47,46,45, o,43,42,41,40,39,38]
75 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,60, o, o,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38]
76 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,58,57, o,55,54, o,52,51,50,49,48,47,46,45,44,43,42,41,40,39]
77 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,63, o, o,60, o, o,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39]
78 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,64, o, o,61,60,59,58,57,56,55,54, o,52,51,50,49,48,47,46,45,44,43,42,41, o]
79 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,61, o, o, o, o, o,55, o,53, o,51,50,49,48,47,46,45,44,43,42,41,40]
80 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,65,64, o, o, o,60, o, o, o,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41]
81 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,67, o, o, o,63, o, o,60,59, o,57,56,55,54, o,52,51,50,49,48,47,46,45,44,43,42,41]
82 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,63,62,61,60, o,58, o, o,55,54, o,52, o,50,49,48,47,46,45,44,43,42]
83 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,59, o,57,56,55, o,53,52,51,50,49,48,47,46,45,44,43,42]
84 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,69,68, o,66, o,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46, o,44,43]
85 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,68, o, o,65, o,63,62,61,60,59, o,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43]


The general tendency is clear, but the overall situation looks rather irregular. For some values of $m$, there are much more 'holes' than for others. Any ideas why?

-
A lot of work on this involved finding positive integer solutions to some low complexity linear equations. Allso, some nice consructions can yield small tesellation numbers for large n and m. You might consider which small tilings generate larger ones, throw those cases out, and then see if you can predict the numbers of the remaining cases. Gerhard "Ask Me About System Design" Paseman, 2012.12.14 – Gerhard Paseman Dec 14 '12 at 18:02
What do you mean by "small tessellation numbers for large n and m"? Do you mean minimal tilings for (km,kn) that are different from those for (m,n)? If so, do you have an example? – Wolfgang Dec 14 '12 at 20:22
I was trying to figure out a decompsition for the 20 by 19 case. I saw if I used three large squares, I could reduce it to solving 10 by 9. Another three large squares got me to 6 by 4, which then gives 9 squares total for the 20 by 19 rectangle. By iterating the same construction twice, I got a cover for an exponential increase in lengths at a linear cost in numbers of squares. I imagine many cases could follow this pattern. The exceptional cases are what are deserving of study. I hope you find a pattern. Gerhard "Ask Me About System Design" Paseman, 2012.12.14 – Gerhard Paseman Dec 14 '12 at 20:41
OK, I see. Your construction yields for example the formula $f(2m+2n,m+3n)\le f(m,n)+3$. In your case, m=3, n=2. (I cannot see how you find your initial 3 squares to reduce 20 by 19 to 10 by 9, but never mind.) – Wolfgang Dec 14 '12 at 21:21
See also demonstrations.wolfram.com/MinimallySquaredRectangles for tabulations up to 300-by-300. Also at int-e.eu/~bf3/squares/young.txt by way of int-e.eu/~bf3/squares – Gerry Myerson Jul 11 '14 at 1:50