%I #77 Nov 15 2020 12:34:11
%S 1,2,2,3,1,3,4,3,3,4,5,2,1,2,5,6,4,4,4,4,6,7,3,4,1,4,3,7,8,5,2,5,5,2,
%T 5,8,9,4,5,3,1,3,5,4,9,10,6,5,5,5,5,5,5,6,10,11,5,3,2,5,1,5,2,3,5,11,
%U 12,7,6,6,5,5,5,5,6,6,7,12,13,6,6,4,6,4,1,4,6,4,6,6,13,14,8,4,6,2,3,7,7,3,2,6,4,8,14
%N Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals.
%C a(n) = A338573(n) for n <= 105, as stated by _R. J. Mathar_. These sequences are essentially different though, because a(13433) = T(67,98) = T(98,67) = a(13464), but A338573(13433) != A338573(13464). The relationship between the tiling problem and resistor networks is remarkable. There are explanations in M. Ortolano et al., 2013. - _Rainer Rosenthal_, Nov 09 2020
%H Alois P. Heinz, <a href="/A113881/b113881.txt">Antidiagonals n = 1..350, flattened</a> (using data from A219158)
%H Bertram Felgenhauer, <a href="http://int-e.eu/~bf3/squares/">Filling rectangles with integer-sided squares</a>
%H Richard J. Kenyon, <a href="http://dx.doi.org/10.1006/jcta.1996.0104">Tiling a rectangle with the fewest squares</a>, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.
%H M. Ortolano, M. Abrate, and L. Callegaro, <a href="http://arxiv.org/abs/1311.0756">On the synthesis of Quantum Hall Array Resistance Standards</a>, arXiv preprint arXiv:1311.0756 [physics.ins-det], 2013.
%H Mark Walters, <a href="http://dx.doi.org/10.1016/j.disc.2008.07.028">Rectangles as sums of squares</a>, Discrete Math. 309 (2009), no. 9, 2913-2921.
%e T(n,n) = 1 (1 n X n square).
%e T(n,1) = n (n 1 X 1 squares).
%e T(6,7) = 6 (2 3 X 3, 1 4 X 4, 1 2 X 2, 2 1 X 1).
%e T(11,13) = 6 (1 7 X 7, 1 6 X 6, 1 5 X 5, 2 4 X 4 1 1 X 1).
%e Table T(m,n) begins:
%e : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
%e : 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, ...
%e : 3, 3, 1, 4, 4, 2, 5, 5, 3, 6, ...
%e : 4, 2, 4, 1, 5, 3, 5, 2, 6, 4, ...
%e : 5, 4, 4, 5, 1, 5, 5, 5, 6, 2, ...
%e : 6, 3, 2, 3, 5, 1, 5, 4, 3, 4, ...
%e : 7, 5, 5, 5, 5, 5, 1, 7, 6, 6, ...
%e : 8, 4, 5, 2, 5, 4, 7, 1, 7, 5, ...
%e : 9, 6, 3, 6, 6, 3, 6, 7, 1, 6, ...
%e : 10, 5, 6, 4, 2, 4, 6, 5, 6, 1, ...
%t (* *** Warning *** This empirical toy-program is based on the greedy algorithm. Its output was only verified for n+k <= 32. Any use outside this domain might produce only upper bounds instead of minimums. *)
%t nmax = 31; Clear[T];
%t Tmin[n_, k_] := Table[{1 + T[ c, k - c] + T[n - c, k], 1 + T[n, k - c] + T[n - c, c]}, {c, 1, k - 1}] // Flatten // Min;
%t Tmin2[n_, k_] := Module[{n1, n2, k1, k2}, 1 + T[n2, k1 + 1] + T[n - n1, k2] + T[n - n2, k1] + T[n1, k - k1] /. {Reduce[1 <= n1 <= n - 1 && 1 <= n2 <= n - 1 && 1 <= k1 <= k - 1 && 1 <= k2 <= k - 1 && n1 + 1 + n2 == n && k1 + 1 + k2 == k, Integers] // ToRules} // Min];
%t T[n_, n_] = 1;
%t T[n_, 1] := n;
%t T[1, k_] := k;
%t T[n_, k_ /; k > 1] /; n > k && Divisible[n, k] := n/k;
%t T[n_, k_ /; k > 1] /; n > k := T[n, k] = If[k >= 5 && n >= 6 && n - k <= 3, Min[Tmin[n, k], Tmin2[n, k], T[k, n - k] + 1], T[k, n - k] + 1];
%t T[n_, k_ /; k > 1] /; n < k := T[n, k] = T[k, n];
%t Table[T[n - k + 1, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Mar 11 2016, checked against first 496 terms of the b-file *)
%Y Rows (or columns) m=1-10 give: A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.
%Y Cf. A219158, A219924, A226545, A338573.
%K nonn,look,tabl
%O 1,2
%A Devin Kilminster (devin(AT)27720.net), Jan 27 2006