cp's OEIS Frontend

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

%I A074712 #41 Apr 05 2025 10:01:25
%S A074712 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,
%T A074712 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,
%U A074712 11,8,9,10,11,12,12,12,12,12,12,12,12,12,12,12,12
%N A074712 Number of (interiors of) cells touched by a diagonal in a regular n X k grid (enumerated antidiagonally).
%C A074712 From _Yifan Xie_, Nov 17 2024: (Start)
%C A074712 A(n, k) is the minimum sum of side lengths of squares that exactly cover a n X k rectangle.
%C A074712 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.
%C A074712 (End)
%H A074712 Nathaniel Johnston, <a href="/A074712/b074712.txt">First 150 antidiagonals, flattened</a>
%H A074712 Micky Bullock, <a href="http://www.mickybullock.com/blog/2010/06/the-diagonal-problem/">The Diagonal Problem (2 dimensions)</a>.
%H A074712 Alberto L. Delgado's <a href="https://web.archive.org/web/20080808134752/http://hilltop.bradley.edu/~delgado/potw/p145.html">Problem of the Week No. 145</a>.
%F A074712 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.
%F A074712 A(n, k) = n + k - gcd(n, k). - _Luc Rousseau_, Sep 15 2017
%F A074712 T(n,k) = A(k,n-k+1) = n+1 - A050873(n+1,k). - _Seiichi Manyama_, Apr 05 2025
%e A074712 The square array A(n,k) (n >= 1, k >= 1) begins:
%e A074712   1 2  3  4  5  6  7  8
%e A074712   2 2  4  4  6  6  8  8
%e A074712   3 4  3  6  7  6  9 10
%e A074712   4 4  6  4  8  8 10  8
%e A074712   5 6  7  8  5 10 11 12
%e A074712   6 6  6  8 10  6 12 12
%e A074712   7 8  9 10 11 12  7 14
%e A074712   8 8 10  8 12 12 14  8
%e A074712   ...
%e A074712 From _Seiichi Manyama_, Apr 05 2025: (Start)
%e A074712 The triangle T(n,k) (1 <= k <= n) begins:
%e A074712    1;
%e A074712    2,  2;
%e A074712    3,  2,  3;
%e A074712    4,  4,  4,  4;
%e A074712    5,  4,  3,  4,  5;
%e A074712    6,  6,  6,  6,  6,  6;
%e A074712    7,  6,  7,  4,  7,  6,  7;
%e A074712    8,  8,  6,  8,  8,  6,  8,  8;
%e A074712    9,  8,  9,  8,  5,  8,  9,  8,  9;
%e A074712   10, 10, 10, 10, 10, 10, 10, 10, 10, 10;
%e A074712   ... (End)
%p A074712 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
%t A074712 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 *)
%o A074712 (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
%Y A074712 Cf. A050873, A199408.
%K A074712 easy,nonn,tabl,look
%O A074712 1,2
%A A074712 _Jens Voß_, Sep 04 2002