A003989 Triangle T from the array A(x, y) = gcd(x,y), for x >= 1, y >= 1, read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 2, 1, 2, 5, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 7, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 1, 2, 1

Offset: 1

Author

Marc LeBrun

Keywords

• tabl
• nonn
• easy
• nice
• mult

Comments

For m < n, the maximal number of nonattacking queens that can be placed on the n by m rectangular toroidal chessboard is gcd(m,n), except in the case m=3, n=6.

The determinant of the matrix of the first n rows and columns is A001088(n). [Smith, Mansion] - Michael Somos, Jun 25 2012

Imagine a torus having regular polygonal cross-section of m sides. Now, break the torus and twist the free ends, preserving rotational symmetry, then reattach the ends. Let n be the number of faces passed in twisting the torus before reattaching it. For example, if n = m, then the torus has exactly one full twist. Do this for arbitrary m and n (m > 1, n > 0). Now, count the independent, closed paths on the surface of the resulting torus, where a path is "closed" if and only if it returns to its starting point after a finite number of times around the surface of the torus. Conjecture: this number is always gcd(m,n). NOTE: This figure constitutes a group with m and n the binary arguments and gcd(m,n) the resulting value. Twisting in the reverse direction is the inverse operation, and breaking & reattaching in place is the identity operation. - Jason Richardson-White, May 06 2013

Regarded as a triangle, table of gcd(n - k +1, k) for 1 <= k <= n. - Franklin T. Adams-Watters, Oct 09 2014

The n-th row of the triangle is 1,...,1, if and only if, n + 1 is prime. - Alexandra Hercilia Pereira Silva, Oct 03 2020

Examples

			The array A begins:
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
  [1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1]
  [1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4]
  [1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1]
  [1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2]
  [1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 7, 1, 1]
  [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8]
  [1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1]
  [1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 2, 1, 2, 5, 2]
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1]
  [1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 2, 3, 4]
  ...
The triangle T begins:
  n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1:  1
  2:  1  1
  3:  1  2  1
  4:  1  1  1  1
  5:  1  2  3  2  1
  6:  1  1  1  1  1  1
  7:  1  2  1  4  1  2  1
  8:  1  1  3  1  1  3  1  1
  9:  1  2  1  2  5  2  1  2  1
 10:  1  1  1  1  1  1  1  1  1  1
 11:  1  2  3  4  1  6  1  4  3  2  1
 12:  1  1  1  1  1  1  1  1  1  1  1  1
 13:  1  2  1  2  1  2  7  2  1  2  1  2  1
 14:  1  1  3  1  5  3  1  1  3  5  1  3  1  1
 15:  1  2  1  4  1  2  1  8  1  2  1  4  1  2  1
 ...  - _Wolfdieter Lang_, May 12 2018
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.
• D. E. Knuth, The Art of Computer Programming, Addison-Wesley, section 4.5.2.

Links

• T. D. Noe, First 100 antidiagonals of array, flattened
• Grant Cairns, Queens on Non-square Tori, El. J. Combinatorics, N6, 2001.
• Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 2013, pp. 1667-1677.
• Warren P. Johnson, An LDU Factorization in Elementary Number Theory, Mathematics Magazine, Vol. 76, No. 5 (Dec., 2003), pp. 392-394.
• P. Mansion, On an Arithmetical Theorem of Professor Smith's, Messenger of Mathematics, (1878), pp. 81-82.
• Kival Ngaokrajang, Pattern of GCD(x,y) > 1 for x and y = 1..60. Non-isolated values larger than 1 (polyomino shapes) are colored.
• Marcelo Polezzi, A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor, The American Mathematical Monthly, Vol. 104, No. 5 (May, 1997), pp. 445-446.
• Mihai Prunescu and Joseph Shunia, Arithmetic-term representations for the greatest common divisor, arXiv:2411.06430 [math.NT], 2024.
• H. J. S. Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7 (1875-1876), pp. 208-212.
• Index entries for sequences related to lcm's

Crossrefs

Rows, columns and diagonals: A089128, A109007, A109008, A109009, A109010, A109011, A109012, A109013, A109014, A109015.

A109004 is (0, 0) based.

Cf. A001088, A003990, A003991, A050873, A051731, A054431, A054522.

Cf. also A091255 for GF(2)[X] polynomial analog.

A(x, y) = A075174(A004198(A075173(x), A075173(y))) = A075176(A004198(A075175(x), A075175(y))).

Antidiagonal sums are in A006579.

Programs

GAP

Flat(List([1..15],n->List([1..n],k->Gcd(n-k+1,k)))); # Muniru A Asiru, Aug 26 2018

Maple

a:=(n,k)->gcd(n-k+1,k): seq(seq(a(n,k),k=1..n),n=1..15); # Muniru A Asiru, Aug 26 2018

Mathematica

Table[ GCD[x - y + 1, y], {x, 1, 15}, {y, 1, x}] // Flatten (* Jean-François Alcover, Dec 12 2012 *)

PARI

{A(n, m) = gcd(n, m)}; /* Michael Somos, Jun 25 2012 */

Formula

Multiplicative in both parameters with a(p^e, m) = gcd(p^e, m). - David W. Wilson, Jun 12 2005

T(n, k) = A(n - k + 1, k) = gcd(n - k + 1, k), n >= 1, k = 1..n. See a comment above and the Mathematica program. - Wolfdieter Lang, May 12 2018

Dirichlet generating function: Sum_{n>=1} Sum_{k>=1} gcd(n, k)/n^s/k^c = zeta(s)*zeta(c)*zeta(s + c - 1)/zeta(s + c). - Mats Granvik, Feb 13 2021

The LU decomposition of this square array = A051731 * transpose(A054522) (see Johnson (2003) or Chamberland (2013), p. 1673). - Peter Bala, Oct 15 2023