A074712 Number of (interiors of) cells touched by a diagonal in a regular n X k 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

Author

Jens Voß, Sep 04 2002

Keywords

• easy
• nonn
• tabl
• look

Comments

From Yifan Xie, Nov 17 2024: (Start)

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

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

(End)

Examples

			The square array A(n,k) (n >= 1, k >= 1) 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
  ...
From _Seiichi Manyama_, Apr 05 2025: (Start)
The triangle T(n,k) (1 <= k <= n) begins:
   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;
  ... (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.

Crossrefs

Cf. A050873, A199408.

Programs

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

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

PARI

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

Formula

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

A(n, k) = n + k - gcd(n, k). - Luc Rousseau, Sep 15 2017

T(n,k) = A(k,n-k+1) = n+1 - A050873(n+1,k). - Seiichi Manyama, Apr 05 2025