# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a003989
Showing 1-1 of 1

%I A003989 #139 Nov 12 2024 02:41:42
%S A003989 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,
%T A003989 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,
%U A003989 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
%N A003989 Triangle T from the array A(x, y) = gcd(x,y), for x >= 1, y >= 1, read by antidiagonals.
%C A003989 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.
%C A003989 The determinant of the matrix of the first n rows and columns is A001088(n). [Smith, Mansion] - _Michael Somos_, Jun 25 2012
%C A003989 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
%C A003989 Regarded as a triangle, table of gcd(n - k +1, k) for 1 <= k <= n. - _Franklin T. Adams-Watters_, Oct 09 2014
%C A003989 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
%D A003989 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.
%D A003989 D. E. Knuth, The Art of Computer Programming, Addison-Wesley, section 4.5.2.
%H A003989 T. D. Noe, <a href="/A003989/b003989.txt">First 100 antidiagonals of array, flattened</a>
%H A003989 Grant Cairns, <a href="https://doi.org/10.37236/1591">Queens on Non-square Tori</a>, El. J. Combinatorics, N6, 2001.
%H A003989 Marc Chamberland, <a href="https://doi.org/10.1016/j.laa.2011.08.030">Factored matrices can generate combinatorial identities</a>, Linear Algebra and its Applications, Volume 438, Issue 4, 2013, pp. 1667-1677.
%H A003989 Warren P. Johnson, <a href="https://doi.org/10.1080/0025570X.2003.11953215">An LDU Factorization in Elementary Number Theory</a>, Mathematics Magazine, Vol. 76, No. 5 (Dec., 2003), pp. 392-394.
%H A003989 P. Mansion, <a href="https://archive.org/stream/messengermathem01glaigoog#page/n94/mode/2up">On an Arithmetical Theorem of Professor Smith's</a>, Messenger of Mathematics, (1878), pp. 81-82.
%H A003989 Kival Ngaokrajang, <a href="/A003989/a003989_1.jpg">Pattern of GCD(x,y) > 1 for x and y = 1..60</a>. Non-isolated values larger than 1 (polyomino shapes) are colored.
%H A003989 Marcelo Polezzi, <a href="http://www.jstor.org/stable/2974739">A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor</a>, The American Mathematical Monthly, Vol. 104, No. 5 (May, 1997), pp. 445-446.
%H A003989 Mihai Prunescu and Joseph Shunia, <a href="https://arxiv.org/abs/2411.06430">Arithmetic-term representations for the greatest common divisor</a>, arXiv:2411.06430 [math.NT], 2024.
%H A003989 H. J. S. Smith, <a href="https://doi.org/10.1112/plms/s1-7.1.208">On the value of a certain arithmetical determinant</a>, Proc. London Math. Soc. 7 (1875-1876), pp. 208-212.
%H A003989 <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>
%F A003989 Multiplicative in both parameters with a(p^e, m) = gcd(p^e, m). - _David W. Wilson_, Jun 12 2005
%F A003989 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
%F A003989 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
%F A003989 The LU decomposition of this square array = A051731 * transpose(A054522) (see Johnson (2003) or Chamberland (2013), p. 1673). - _Peter Bala_, Oct 15 2023
%e A003989 The array A begins:
%e A003989   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
%e A003989   [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
%e A003989   [1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1]
%e A003989   [1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4]
%e A003989   [1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1]
%e A003989   [1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2]
%e A003989   [1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 7, 1, 1]
%e A003989   [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8]
%e A003989   [1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1]
%e A003989   [1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 2, 1, 2, 5, 2]
%e A003989   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1]
%e A003989   [1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 2, 3, 4]
%e A003989   ...
%e A003989 The triangle T begins:
%e A003989   n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
%e A003989   1:  1
%e A003989   2:  1  1
%e A003989   3:  1  2  1
%e A003989   4:  1  1  1  1
%e A003989   5:  1  2  3  2  1
%e A003989   6:  1  1  1  1  1  1
%e A003989   7:  1  2  1  4  1  2  1
%e A003989   8:  1  1  3  1  1  3  1  1
%e A003989   9:  1  2  1  2  5  2  1  2  1
%e A003989  10:  1  1  1  1  1  1  1  1  1  1
%e A003989  11:  1  2  3  4  1  6  1  4  3  2  1
%e A003989  12:  1  1  1  1  1  1  1  1  1  1  1  1
%e A003989  13:  1  2  1  2  1  2  7  2  1  2  1  2  1
%e A003989  14:  1  1  3  1  5  3  1  1  3  5  1  3  1  1
%e A003989  15:  1  2  1  4  1  2  1  8  1  2  1  4  1  2  1
%e A003989  ...  - _Wolfdieter Lang_, May 12 2018
%p A003989 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
%t A003989 Table[ GCD[x - y + 1, y], {x, 1, 15}, {y, 1, x}] // Flatten (* _Jean-François Alcover_, Dec 12 2012 *)
%o A003989 (PARI) {A(n, m) = gcd(n, m)}; /* _Michael Somos_, Jun 25 2012 */
%o A003989 (GAP) Flat(List([1..15],n->List([1..n],k->Gcd(n-k+1,k)))); # _Muniru A Asiru_, Aug 26 2018
%Y A003989 Rows, columns and diagonals: A089128, A109007, A109008, A109009, A109010, A109011, A109012, A109013, A109014, A109015.
%Y A003989 A109004 is (0, 0) based.
%Y A003989 Cf.  A001088, A003990, A003991, A050873, A051731, A054431, A054522.
%Y A003989 Cf. also A091255 for GF(2)[X] polynomial analog.
%Y A003989 A(x, y) = A075174(A004198(A075173(x), A075173(y))) = A075176(A004198(A075175(x), A075175(y))).
%Y A003989 Antidiagonal sums are in A006579.
%K A003989 tabl,nonn,easy,nice,mult
%O A003989 1,5
%A A003989 _Marc LeBrun_

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE