|
%I #135 Oct 20 2023 06:47:18
%S 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 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 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 Triangle T from the array A(x, y) = gcd(x,y), for x >= 1, y >= 1, read by antidiagonals.
%C 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 The determinant of the matrix of the first n rows and columns is A001088(n). [Smith, Mansion] - _Michael Somos_, Jun 25 2012
%C 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 Regarded as a triangle, table of gcd(n - k +1, k) for 1 <= k <= n. - _Franklin T. Adams-Watters_, Oct 09 2014
%C 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 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.
%D D. E. Knuth, The Art of Computer Programming, Addison-Wesley, section 4.5.2.
%H T. D. Noe, <a href="/A003989/b003989.txt">First 100 antidiagonals of array, flattened</a>
%H Grant Cairns, <a href="https://doi.org/10.37236/1591">Queens on Non-square Tori</a>, El. J. Combinatorics, N6, 2001.
%H 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 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 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 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 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 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 <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>
%F Multiplicative in both parameters with a(p^e, m) = gcd(p^e, m). - _David W. Wilson_, Jun 12 2005
%F 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 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 The LU decomposition of this square array = A051731 * transpose(A054522) (see Johnson (2003) or Chamberland (2013), p. 1673). - _Peter Bala_, Oct 15 2023
%e The array A begins:
%e [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
%e [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
%e [1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1]
%e [1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4]
%e [1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1]
%e [1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2]
%e [1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 7, 1, 1]
%e [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8]
%e [1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1]
%e [1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 2, 1, 2, 5, 2]
%e [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1]
%e [1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 2, 3, 4]
%e ...
%e The triangle T begins:
%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
%e 1: 1
%e 2: 1 1
%e 3: 1 2 1
%e 4: 1 1 1 1
%e 5: 1 2 3 2 1
%e 6: 1 1 1 1 1 1
%e 7: 1 2 1 4 1 2 1
%e 8: 1 1 3 1 1 3 1 1
%e 9: 1 2 1 2 5 2 1 2 1
%e 10: 1 1 1 1 1 1 1 1 1 1
%e 11: 1 2 3 4 1 6 1 4 3 2 1
%e 12: 1 1 1 1 1 1 1 1 1 1 1 1
%e 13: 1 2 1 2 1 2 7 2 1 2 1 2 1
%e 14: 1 1 3 1 5 3 1 1 3 5 1 3 1 1
%e 15: 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1
%e ... - _Wolfdieter Lang_, May 12 2018
%p 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 Table[ GCD[x - y + 1, y], {x, 1, 15}, {y, 1, x}] // Flatten (* _Jean-François Alcover_, Dec 12 2012 *)
%o (PARI) {A(n, m) = gcd(n, m)}; /* _Michael Somos_, Jun 25 2012 */
%o (GAP) Flat(List([1..15],n->List([1..n],k->Gcd(n-k+1,k)))); # _Muniru A Asiru_, Aug 26 2018
%Y Rows, columns and diagonals: A089128, A109007, A109008, A109009, A109010, A109011, A109012, A109013, A109014, A109015.
%Y A109004 is (0, 0) based.
%Y Cf. A001088, A003990, A003991, A050873, A051731, A054431, A054522.
%Y Cf. also A091255 for GF(2)[X] polynomial analog.
%Y A(x, y) = A075174(A004198(A075173(x), A075173(y))) = A075176(A004198(A075175(x), A075175(y))).
%Y Antidiagonal sums are in A006579.
%K tabl,nonn,easy,nice,mult
%O 1,5
%A _Marc LeBrun_
|
