login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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