A109013 -id:A109013 - cp's OEIS frontend

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

Marc LeBrun

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

			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

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.

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

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.

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

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

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

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

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

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

Original entry on oeis.org

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

Mitch Harris

			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]

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

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.

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

A003989 is (1, 1) based.

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)}
```

{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 */

# 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

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

A109012 a(n) = gcd(n,9).

Original entry on oeis.org

9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1

Offset: 0

Mitch Harris

Start with positive integer n. At each step, either (a) multiply by any positive integer or (b) remove all zeros from the number. a(n) is the smallest number that can be reached by this process. - David W. Wilson, Nov 01 2005
From Martin Fuller, Jul 09 2007: (Start)
Also the minimal positive difference between numbers whose digit sum is a multiple of n. Proof:
Construction: Pick a positive number that does not end with 9, and has a digit sum n-a(n). To form the lower number, append 9 until the digit sum is a multiple of n. This is always possible since the difference is gcd(n,9). Add a(n) to form the higher number, which will have digit sum n.
E.g., n=12: prefix=18, lower=18999, higher=19002, difference=3.
Minimality: All numbers are a multiple of a(n) if their digit sum is a multiple of n. Hence the minimal difference is at least a(n). (End)

Antti Karttunen, Table of n, a(n) for n = 0..100000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,1).

Cf. A109004.
Cf. A109007, A109008, A109009, A109010, A109011, A109013, A109014, A109015.
Cf. A074232, A374039.

GCD[Range[0, 100], 9] (* Paolo Xausa, Aug 28 2024 *)

a(n)=gcd(n,9) \\ Charles R Greathouse IV, Oct 07 2015

from math import gcd
def a(n): return gcd(n, 9)
print([a(n) for n in range(101)]) # Michael S. Branicky, Sep 01 2021

a(n) = 1 + 2*[3|n] + 6*[9|n], where [x|y] = 1 when x divides y, 0 otherwise.
a(n) = a(n-9).
Multiplicative with a(p^e, 9) = gcd(p^e, 9). - David W. Wilson, Jun 12 2005
G.f.: (-9 - x - x^2 - 3*x^3 - x^4 - x^5 - 3*x^6 - x^7 - x^8) / ((x-1)*(1 + x + x^2)*(x^6 + x^3 + 1)). - R. J. Mathar, Apr 04 2011
Dirichlet g.f.: (1+2/3^s+6/9^s)*zeta(s). - R. J. Mathar, Apr 04 2011

A109051 a(n) = lcm(n,10).

Original entry on oeis.org

0, 10, 10, 30, 20, 10, 30, 70, 40, 90, 10, 110, 60, 130, 70, 30, 80, 170, 90, 190, 20, 210, 110, 230, 120, 50, 130, 270, 140, 290, 30, 310, 160, 330, 170, 70, 180, 370, 190, 390, 40, 410, 210, 430, 220, 90, 230, 470, 240, 490, 50, 510, 260, 530, 270, 110, 280

Offset: 0

Mitch Harris, Jun 18 2005

Amiram Eldar, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,-1).
Index entries for sequences related to lcm's.

Cf. A106611, A109013, A109042.

[Lcm(n,10): n in [0..100]]; // Vincenzo Librandi, Apr 18 2011

q:= [seq(10/igcd(i,10),i=1..10)]:
[0,seq(seq((10*i+j)*q[j],j=1..10),i=0..10)]; # Robert Israel, Feb 23 2016

a[n_] := LCM[n, 10]; Array[a, 60, 0] (* Amiram Eldar, Nov 26 2022 *)

a(n) = lcm(n, 10); \\ Michel Marcus, Feb 23 2016

[lcm(n,10)for n in range(0, 57)] # Zerinvary Lajos, Jun 07 2009

a(n) = n*10/gcd(n, 10).
a(n) = 10*n/A109013(n) = 10*A106611(n). - R. J. Mathar, Apr 18 2011
G.f.: 10*x*(1 +x +3*x^2 +2*x^3 +x^4 +3*x^5 +7*x^6 +4*x^7 +9*x^8 +x^9 +9*x^10 +4*x^11 +7*x^12 +3*x^13 +x^14 +2*x^15 +3*x^16 +x^17 +x^18)/(1 -x^10)^2. - Robert Israel, Feb 23 2016
Sum_{k=1..n} a(k) ~ (63/20) * n^2. - Amiram Eldar, Nov 26 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

A109012 a(n) = gcd(n,9).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A109051 a(n) = lcm(n,10).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A070291 a(n) = lcm(10,n)/gcd(10,n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A089086 Greatest common divisor of n^2-5 and n^2+5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI