A281726 Triangular array read by rows: T(n,k) is the number of elements in an n X k matrix that will be assigned the same value whether the integers from 1 to n*k are assigned to elements in row-major order or column-major order.

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

Offset: 1

Author

Michel Marcus, Jan 28 2017

Keywords

• nonn
• tabl

Comments

From Jon E. Schoenfield, Dec 10 2023: (Start)

T(n,k) is also the number of lattice points that lie on a line segment from (0,0) to (n-k,k-1). Thus, row n of the triangle lists, for each of the n 1st-quadrant lattice points P whose Manhattan distance from the origin is n-1, the number of lattice points on a line segment from the origin to P.

E.g., for n = 5, the 5 1st-quadrant lattice points whose Manhattan distance from the origin is 4 are (0,4), (1,3), (2,2), (3,1), and (4,0), and a line segment drawn from the origin to each of these points will intersect 5, 2, 3, 2, and 5 lattice points, respectively; { 5, 2, 3, 2, 5 } is row 5 of the triangle. (End)

Examples

			For n=3 and k=2, the matrix will be
  1 2  and  1 4
  3 4       2 5
  5 6       3 6
and there are 2 identical terms (1 and 6).
Triangle begins:
  1;
  2, 2;
  3, 2, 3;
  4, 2, 2, 4;
  5, 2, 3, 2, 5;
  6, 2, 2, 2, 2, 6;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..200, flattened
• Ana Rechtman, 3ème Défi du Calendrier Mathématique, Images des Mathématiques, CNRS, January 2017.

Crossrefs

Cf. A109004, A281725.

Main diagonal and column k=1 give A000027.

Programs

Maple

T:= (n, k)-> add(add(`if`(j+k*(i-1)=i+n*(j-1), 1, 0), i=1..n), j=1..k):
seq(seq(T(n,k), k=1..n), n=1..20);  # Alois P. Heinz, Jan 28 2017

Mathematica

Array[1+GCD[#,Range[0,#]]&,20,0] (* Paolo Xausa, Dec 08 2023 *)

PARI

a(n, k) = {ml = matrix(n, k, i, j, ((i-1)*k+j)); mc = matrix(n, k, i, j, ((j-1)*n+i)); sum(i=1, n, sum(j=1, k, ml[i,j] == mc[i,j]));}

Formula

T(n,k) = 1 + gcd(n-1, k-1). - Jon E. Schoenfield, Dec 08 2023