A226576 -id:A226576 - cp's OEIS frontend

A113881 Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals.

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

Offset: 1

Devin Kilminster (devin(AT)27720.net), Jan 27 2006

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

			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, ...

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, and 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.

Rows (or columns) m=1-10 give: A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.

Cf. A219158, A219924, A226545, A338573.

(* *** 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 *)

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 2, 4, 1, 5, 4, 4, 5, 1, 6, 3, 2, 3, 5, 1, 7, 5, 5, 5, 5, 5, 1, 8, 4, 5, 2, 5, 4, 7, 1, 9, 6, 3, 6, 6, 3, 6, 7, 1, 10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1

Offset: 1

David Radcliffe, Nov 12 2012

Triangular array read by rows. m=1,2,...,n; n=1,2,3,...

			T(6,5) = 5 because a 6 X 5 rectangle can be subdivided into two 3 X 3 squares and three 2 X 2 squares.
Triangle begins:
   1;
   2, 1;
   3, 3, 1;
   4, 2, 4, 1;
   5, 4, 4, 5, 1;
   6, 3, 2, 3, 5, 1;
   7, 5, 5, 5, 5, 5, 1;
   8, 4, 5, 2, 5, 4, 7, 1;
   9, 6, 3, 6, 6, 3, 6, 7, 1;
  10, 5, 6, 4, 2, 4, 6, 5, 6, 1;
  11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1;
  12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1;
  13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1;
  14, 7, 7, 5, 7, 5, 2, 5, 7, 5, 7, 5, 7, 1;
  15, 9, 5, 7, 3, 4, 8, 8, 4, 3, 7, 5, 8, 7, 1;

Massimo Ortolano, Table of n, a(n) for n = 1..75466, rows 1..388 of triangle, flattened. Corrected version provided by Qizheng He.
Gary Antonick, Matt Enlow's Rectangle Division Puzzle, The New York Times, June 15, 2015.
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, and 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.

First 19 terms agree with A049834.
Columns m=1..10 give A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.
Cf. A113881, A338861.

A285721 Square array read by antidiagonals: A(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k, read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Original entry on oeis.org

0, 1, 1, 2, 0, 2, 3, 2, 2, 3, 4, 1, 0, 1, 4, 5, 3, 3, 3, 3, 5, 6, 2, 3, 0, 3, 2, 6, 7, 4, 1, 4, 4, 1, 4, 7, 8, 3, 4, 2, 0, 2, 4, 3, 8, 9, 5, 4, 4, 5, 5, 4, 4, 5, 9, 10, 4, 2, 1, 4, 0, 4, 1, 2, 4, 10, 11, 6, 5, 5, 4, 6, 6, 4, 5, 5, 6, 11, 12, 5, 5, 3, 5, 3, 0, 3, 5, 3, 5, 5, 12, 13, 7, 3, 5, 1, 2, 7, 7, 2, 1, 5, 3, 7, 13, 14, 6, 6, 2, 6, 3, 5, 0, 5, 3, 6, 2, 6, 6, 14

Offset: 1

Antti Karttunen, May 03 2017

			The top left 18 X 18 corner of the array:
   0, 1, 2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 12, 13, 14, 15, 16, 17
   1, 0, 2, 1, 3, 2, 4, 3, 5,  4,  6,  5,  7,  6,  8,  7,  9,  8
   2, 2, 0, 3, 3, 1, 4, 4, 2,  5,  5,  3,  6,  6,  4,  7,  7,  5
   3, 1, 3, 0, 4, 2, 4, 1, 5,  3,  5,  2,  6,  4,  6,  3,  7,  5
   4, 3, 3, 4, 0, 5, 4, 4, 5,  1,  6,  5,  5,  6,  2,  7,  6,  6
   5, 2, 1, 2, 5, 0, 6, 3, 2,  3,  6,  1,  7,  4,  3,  4,  7,  2
   6, 4, 4, 4, 4, 6, 0, 7, 5,  5,  5,  5,  7,  1,  8,  6,  6,  6
   7, 3, 4, 1, 4, 3, 7, 0, 8,  4,  5,  2,  5,  4,  8,  1,  9,  5
   8, 5, 2, 5, 5, 2, 5, 8, 0,  9,  6,  3,  6,  6,  3,  6,  9,  1
   9, 4, 5, 3, 1, 3, 5, 4, 9,  0, 10,  5,  6,  4,  2,  4,  6,  5
  10, 6, 5, 5, 6, 6, 5, 5, 6, 10,  0, 11,  7,  6,  6,  7,  7,  6
  11, 5, 3, 2, 5, 1, 5, 2, 3,  5, 11,  0, 12,  6,  4,  3,  6,  2
  12, 7, 6, 6, 5, 7, 7, 5, 6,  6,  7, 12,  0, 13,  8,  7,  7,  6
  13, 6, 6, 4, 6, 4, 1, 4, 6,  4,  6,  6, 13,  0, 14,  7,  7,  5
  14, 8, 4, 6, 2, 3, 8, 8, 3,  2,  6,  4,  8, 14,  0, 15,  9,  5
  15, 7, 7, 3, 7, 4, 6, 1, 6,  4,  7,  3,  7,  7, 15,  0, 16,  8
  16, 9, 7, 7, 6, 7, 6, 9, 9,  6,  7,  6,  7,  7,  9, 16,  0, 17
  17, 8, 5, 5, 6, 2, 6, 5, 1,  5,  6,  2,  6,  5,  5,  8, 17,  0

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 antidiagonals of the array

One less than A072030.
Row 2 & column 2: A028242 (but with starting offset 1).
Row 3 & column 3 (from zero onward) seems to be A226576.
Cf. A003989, A285722, A285732.
Compare also to arrays A049834, A113881, A219158.

def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
for n in range(1, 21): print([A(n - k + 1, k) for k in range(1, n + 1)]) # Indranil Ghosh, May 03 2017

(define (A285721 n) (A285721bi (A002260 n) (A004736 n)))
(define (A285721bi row col) (cond ((= row col) 0) ((> row col) (+ 1 (A285721bi (- row col) col))) (else (+ 1 (A285721bi row (- col row))))))
;; Alternatively:
(define (A285721bi row col) (if (= row col) 0 (+ 1 (A285721bi (abs (- row col)) (min col row)))))
;; Another implementation, as an one-dimensional sequence:
(definec (A285721 n) (if (zero? (A285722 n)) 0 (+ 1 (A285721 (A285722 n)))))

If n = k, then A(n,k) = 0, if n > k, then A(n,k) = 1 + A(n-k,k), otherwise [when n < k], A(n,k) = 1 + A(n,k-n).
Or alternatively, when n <> k, A(n,k) = 1 + A(abs(n-k),min(n,k)).
A(n,k) = A072030(n,k)-1.
As an one-dimensional sequence:
a(n) = 0 if A285722(n) = 0, otherwise a(n) = 1 + a(A285722(n)). [Here A285722 is also used as an one-dimensional sequence.]

cp's OEIS Frontend

A113881 Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A285721 Square array read by antidiagonals: A(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k, read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Scheme

Formula