This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A113881 Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals. 14
 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, 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, 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 LINKS Alois P. Heinz, Antidiagonals n = 1..350, flattened (using data from A219158) Bertram Felgenhauer, Filling rectangles with integer-sided squares Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291. M. Ortolano, M. Abrate, L. Callegaro, On the synthesis of Quantum Hall Array Resistance Standards, arXiv preprint arXiv:1311.0756 [physics.ins-det], 2013. Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921. EXAMPLE T(n,n) = 1 (1 n X n square). T(n,1) = n (n 1 X 1 squares). T(6,7) = 6 (2 3 X 3, 1 4 X 4, 1 2 X 2, 2 1 X 1). T(11,13) = 6 (1 7 X 7, 1 6 X 6, 1 5 X 5, 2 4 X 4 1 1 X 1). Table T(m,n) begins: :   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... :   2, 1, 3, 2, 4, 3, 5, 4, 6,  5, ... :   3, 3, 1, 4, 4, 2, 5, 5, 3,  6, ... :   4, 2, 4, 1, 5, 3, 5, 2, 6,  4, ... :   5, 4, 4, 5, 1, 5, 5, 5, 6,  2, ... :   6, 3, 2, 3, 5, 1, 5, 4, 3,  4, ... :   7, 5, 5, 5, 5, 5, 1, 7, 6,  6, ... :   8, 4, 5, 2, 5, 4, 7, 1, 7,  5, ... :   9, 6, 3, 6, 6, 3, 6, 7, 1,  6, ... :  10, 5, 6, 4, 2, 4, 6, 5, 6,  1, ... MATHEMATICA (* *** 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. *) nmax = 31; Clear[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; 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[n_, n_] = 1; T[n_, 1] := n; T[1, k_] := k; T[n_, k_ /; k > 1] /; n > k && Divisible[n, k] := n/k; 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[n_, k_ /; k > 1] /; n < k := T[n, k] = T[k, n]; 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 *) CROSSREFS Rows (or columns) m=1-10 give: A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583. Cf. A219158, A219924, A226545. Sequence in context: A143182 A128715 A237447 * A072030 A217029 A205456 Adjacent sequences:  A113878 A113879 A113880 * A113882 A113883 A113884 KEYWORD nonn,look,tabl AUTHOR Devin Kilminster (devin(AT)27720.net), Jan 27 2006 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 25 23:52 EDT 2019. Contains 324367 sequences. (Running on oeis4.)