A074712 Number of (interiors of) cells touched by a diagonal in a regular m X n grid (enumerated antidiagonally).

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

Offset

1,2

Comments

From Yifan Xie, Nov 17 2024: (Start)

T(m, n) is the minimum sum of side lengths of squares that exactly cover a m X n rectangle.

T(m, n) is the minimum number of nonzero elements of a m X n matrix such that the sum of each row is n, and the sum of each column is m.

(End)

Links

Nathaniel Johnston, First 150 antidiagonals, flattened

Micky Bullock, The Diagonal Problem (2 dimensions).

Alberto L. Delgado's Problem of the Week No. 145.

Formula

T(m, n) = m + n - 1 if m and n are coprime; T(m, n) = d * T(m/d, n/d) where d is the greatest common divisor of m and n, otherwise.

T(m, n) = m + n - gcd(m, n). - Luc Rousseau, Sep 15 2017

Example

The array begins:
1 2  3  4  5  6  7  8
2 2  4  4  6  6  8  8
3 4  3  6  7  6  9 10
4 4  6  4  8  8 10  8
5 6  7  8  5 10 11 12
6 6  6  8 10  6 12 12
7 8  9 10 11 12  7 14
8 8 10  8 12 12 14  8
...

Maple

A074712 := proc(m, n) local d: d:=gcd(m, n): if(d=1)then return m+n-1: else return d*procname(m/d, n/d): fi: end: seq(seq(A074712(n-d+1, d), d=1..n), n=1..8); # Nathaniel Johnston, May 09 2011

Mathematica

T[m_, n_]=m+n-GCD[m, n]; Table[T[m, s-m], {s, 2, 10}, {m, 1, s-1}]//Flatten (* Luc Rousseau, Sep 16 2017 *)

Prog

(PARI) (T(m, n)=m+n-gcd(m, n)); for(s=2, 10, for(m=1, s-1, n=s-m; print1(T(m, n), ", "))) \\ Luc Rousseau, Sep 16 2017

Crossrefs

Cf. A199408.

Sequence in context: A127095 A249871 A330408 * A271914 A087735 A322630

Adjacent sequences: A074709 A074710 A074711 * A074713 A074714 A074715

Keyword

easy,nonn,tabl

Author

Jens Voß, Sep 04 2002

Status

approved