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 $m=n-1,n-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?
Best Answer
For rectangles with maximum size 760 or less, there is one remaining possible counterexample. The 17-square tiling of the 697x611 is not proven minimal.
16 1394 1222 723 671 120 551 499 155 69 1 32 87 39 31 8 55 47 344
17 697 611 51 51 119 119 119 119 119 34 68 34 41 82 82 492 41 205 205
I've put 4944 more at Possible Counterexamples to the Minimal Squaring Conjecture.
My original example shows two known ways to divide a 2(7125×7081) rectangle into 20 squares.
The smallest known dissection of a (7125×7081) rectangle needs 21 squares.