A109004 Table of gcd(n, m) read by antidiagonals, n >= 0, m >= 0.

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

Offset: 0

Author

Mitch Harris

Keywords

• nonn
• easy
• mult
• tabl

Examples

			Triangle starts:
  [ 0] [0]
  [ 1] [1, 1]
  [ 2] [2, 1, 2]
  [ 3] [3, 1, 1, 3]
  [ 4] [4, 1, 2, 1, 4]
  [ 5] [5, 1, 1, 1, 1, 5]
  [ 6] [6, 1, 2, 3, 2, 1, 6]
  [ 7] [7, 1, 1, 1, 1, 1, 1, 7]
  [ 8] [8, 1, 2, 1, 4, 1, 2, 1, 8]
  [ 9] [9, 1, 1, 3, 1, 1, 3, 1, 1, 9]
  [10] [10, 1, 2, 1, 2, 5, 2, 1, 2, 1, 10]
  [11] [11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11]
  [12] [12, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12]
		

References

• L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, p. 335.
• 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

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• Peter Luschny, The binary GCD algorithm, a Python implementation.
• 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.

Crossrefs

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

A003989 is (1, 1) based.

Programs

Mathematica

a[n_, m_] := GCD[n, m]; Table[a[n - m, m], {n,0,10}, {m,0,n}]//Flatten (* G. C. Greubel, Jan 04 2018 *)

PARI

{a(n, m) = gcd( n, m)}

PARI

{a(n, m) = local(x); n = abs(n); m = abs(m); if( !m, n, -2 * sum( k=1, m, x = k * n / m; x - floor( x) - 1/2))} /* Michael Somos, May 22 2011 */

Python

# Since 3.5 part of the math module. For a version using the binary GCD algorithm see the links.
for n in range(13): print([math.gcd(n, k) for k in range(n + 1)])  # Peter Luschny, May 14 2025

Formula

a(n, m) = a(m, n) = a(m, n-m) = a(m, n mod m), n >= m.

a(n, m) = n + m - n*m + 2*Sum_{k=1..m-1} floor(k*n/m).

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