login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003989 Table of gcd(x,y) read by antidiagonals, where (x,y) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ... 39
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

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 number of 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) for 0 < k < n. - Franklin T. Adams-Watters, Oct 09 2014

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.

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.

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

FORMULA

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

EXAMPLE

Table begins:

1 1 1 1 1 1 ...

1 2 1 2 1 2 ...

1 1 3 1 1 3 ...

1 2 1 4 1 2 ...

1 1 1 1 5 1 ...

MATHEMATICA

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

PROG

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

CROSSREFS

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

A109004 is (0, 0) based.

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

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.

Sequence in context: A140194 A159923 A287957 * A091255 A175466 A214403

Adjacent sequences:  A003986 A003987 A003988 * A003990 A003991 A003992

KEYWORD

tabl,nonn,easy,nice,mult

AUTHOR

Marc LeBrun

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 25 21:58 EST 2018. Contains 299660 sequences. (Running on oeis4.)