A075174 -id:A075174 - 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

A003990 Table of lcm(x,y), read along antidiagonals.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 4, 6, 6, 4, 5, 4, 3, 4, 5, 6, 10, 12, 12, 10, 6, 7, 6, 15, 4, 15, 6, 7, 8, 14, 6, 20, 20, 6, 14, 8, 9, 8, 21, 12, 5, 12, 21, 8, 9, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 11, 10, 9, 8, 35, 6, 35, 8, 9, 10, 11, 12, 22, 30, 36, 40, 42, 42, 40, 36, 30, 22, 12, 13, 12, 33, 20, 45, 24

Offset: 1

Marc LeBrun

A(x,x) = x on the diagonal. - Reinhard Zumkeller, Aug 05 2012

			The symmetric array is lcm(x,y) = lcm(y,x):
   1  2  3  4  5  6  7  8  9 10 ...
   2  2  6  4 10  6 14  8 18 10 ...
   3  6  3 12 15  6 21 24  9 30 ...
   4  4 12  4 20 12 28  8 36 20 ...
   5 10 15 20  5 30 35 40 45 10 ...
   6  6  6 12 30  6 42 24 18 30 ...
   7 14 21 28 35 42  7 56 63 70 ...
   8  8 24  8 40 24 56  8 72 40 ...
   9 18  9 36 45 18 63 72  9 90 ...
  10 10 30 20 10 30 70 40 90 10 ...

T. D. Noe, First 100 antidiagonals of array, flattened
Kival Ngaokrajang, Illustration of pattern, where terms with least significant decimal digit equal to zero are colored.
Index entries for sequences related to lcm's

Cf. A003989, A003991, A051173.
A(x, y) = A075174(A003986(A075173(x), A075173(y))) = A075176(A003986(A075175(x), A075175(y))).
Antidiagonal sums are in A006580.
Cf. A002260.

a003990 x y = a003990_adiag x !! (y-1)
a003990_adiag n = a003990_tabl !! (n-1)
a003990_tabl = zipWith (zipWith lcm) a002260_tabl $ map reverse a002260_tabl
-- Reinhard Zumkeller, Aug 05 2012

Table[ LCM[x-y, y], {x, 1, 14}, {y, 1, x-1}] // Flatten (* Jean-François Alcover, Aug 20 2013 *)

A(x,y)=lcm(x,y) \\ Charles R Greathouse IV, Feb 06 2017

A075173 Prime factorization of n encoded by interleaving successive prime exponents in unary to bit-positions given by columns of A075300.

Original entry on oeis.org

0, 1, 2, 5, 8, 3, 128, 21, 34, 9, 32768, 7, 2147483648, 129, 10, 85, 9223372036854775808, 35, 170141183460469231731687303715884105728, 13, 130, 32769

Offset: 1

Antti Karttunen, Sep 13 2002

nonn

As in A059884, here also we store the exponent e_i of p_i (p1=2, p2=3, p3=5, ...) in the factorization of n to the bit positions given by the column i-1 of A075300 (the exponent of 2 is thus stored to bit positions 0, 2, 4, ..., exponent of 3 to 1, 5, 9, 13, ..., exponent of 5 to 3, 11, 19, 27, 35, ...), but using unary instead of binary system, i.e. we actually store 2^(e_i) - 1 in binary.

This injective mapping from N to N offers an example of the proof given in Cameron's book that any distributive lattice can be represented as a sublattice of the power-set lattice P(X) of some set X. This allows us to implement GCD (A003989) with bitwise AND (A004198) and LCM (A003990) with bitwise OR (A003986). Also, to test whether x divides y, it is enough to check that ((a(x) OR a(y)) XOR a(y)) = A003987(A003986(a(x),a(y)),a(y)) is zero.

			a(24) = 23 because 24 = 2^3 * 3^1 so we add the binary words 10101 and 10 to get 10111 in binary = 23 in decimal and a(25) = 2056 because 25 = 5^2 so we form a binary word 100000001000 = 2056 in decimal.

P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1998, page 191. (12.3. Distributive lattices)

Variant: A075175. Inverse: A075174. Cf. A059884.

A003989(x, y) = A075174(A004198(a(x), a(y))), A003990(x, y) = A075174(A003986(a(x), a(y))).

A075176 Inverse function of N -> N injection A075175.

Original entry on oeis.org

1, 2, 3, 6, 0, 4, 0, 12, 5, 10, 15, 30, 0, 20, 0, 60, 0, 0, 9, 18, 0, 0, 0, 36, 0, 0, 45, 90, 0, 0, 0, 180, 0, 0, 0, 0, 0, 8, 0, 24, 0, 0, 0, 0, 0, 40, 0, 120, 0, 0, 0, 0, 0, 0, 0, 72, 0, 0, 0, 0, 0, 0, 0, 360, 7, 14, 21, 42, 0, 28, 0, 84, 35, 70, 105, 210, 0, 140, 0, 420, 0, 0, 63, 126, 0, 0

Offset: 0

Antti Karttunen, Sep 13 2002

nonn

a(n) = 0 for those n which do not occur as the values of A075175. All positive natural numbers occur here once.

a(A075175(n)) = n for all n >= 1. Differs from A075174 for first time at a(18) = 9, while A075174(18) = 0.

A082856 Recursive binary interleaving code for rooted plane binary trees, as ordered by A014486.

Original entry on oeis.org

0, 1, 3, 5, 11, 35, 7, 21, 69, 139, 2059, 43, 547, 8227, 15, 39, 23, 277, 4117, 71, 85, 1093, 16453, 32907, 8388747, 2187, 526347, 134219787, 171, 2091, 555, 131619, 33554979, 8235, 8739, 2105379, 536879139, 143, 2063, 47, 551, 8231, 31, 55, 279, 65813, 16777493, 4119, 4373, 1052693, 268439573, 79, 103, 87, 341, 4181, 1095, 1109

Offset: 0

Antti Karttunen, May 06 2003

nonn

This encoding has a property that the greatest common subtree i.e. the intersect (or the least common supertree, the union) of any two trees can be obtained by simply computing the binary-AND (A004198) (or respectively: binary-OR, A003986) of the corresponding codes. See A082858-A082860.

			The empty tree . has code 0, the tree of two edges (and leaves) \/ has code 1 and in general tree's code is obtained by interleaving into odd and even bits (above bit-0, which is always 1 for nonempty trees) the codes for the left and right hand side subtrees of the tree.

Antti Karttunen, Alternative Catalan Orderings (with the complete Scheme source)

Inverse: A082857. Cf. A072634-A072637, A075173-A075174, A000695.

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

A003990 Table of lcm(x,y), read along antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A075173 Prime factorization of n encoded by interleaving successive prime exponents in unary to bit-positions given by columns of A075300.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A075176 Inverse function of N -> N injection A075175.

Views

Author

Keywords

Comments

Crossrefs

A082856 Recursive binary interleaving code for rooted plane binary trees, as ordered by A014486.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A082857 Inverse function of N -> N injection A082856.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula