A075175 -id:A075175 - cp's OEIS frontend

A004198 Table of x AND y, where (x,y) = (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),...

0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 2, 2, 0, 0, 0, 1, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 4, 1, 2, 1, 0, 0, 0, 2, 2, 4, 4, 2, 2, 0, 0, 0, 1, 0, 3, 4, 5, 4, 3, 0, 1, 0, 0, 0, 0, 0, 4, 4, 4, 4, 0, 0, 0, 0, 0, 1, 2, 1, 0, 5, 6, 5, 0, 1, 2, 1, 0, 0, 0, 2, 2, 0, 0, 6, 6, 0, 0, 2, 2, 0, 0, 0, 1, 0

Offset: 0

David W. Wilson

Or, table of AND(i,j), i >= 0, j >= 0, read by antidiagonals. - N. J. A. Sloane, Feb 08 2016

Or, table of (i+j-Nimsum(i,j))/2 read by antidiagonals [Winning Ways, p. 75]. - N. J. A. Sloane, Feb 22 2019

			The AND(i,j) table (shown without commas or spaces) begins:
0000000000000000000000000...
0101010101010101010101010...
0022002200220022002200220...
0123012301230123012301230...
0000444400004444000044440...
0101454501014545010145450...
0022446600224466002244660...
0123456701234567012345670...
0000000088888888000000008...
0101010189898989010101018...
...
The first few antidiagonals are:
0,
0, 0,
0, 1, 0,
0, 0, 0, 0,
0, 1, 2, 1, 0,
0, 0, 2, 2, 0, 0,
0, 1, 0, 3, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 2, 1, 4, 1, 2, 1, 0,
0, 0, 2, 2, 4, 4, 2, 2, 0, 0,
0, 1, 0, 3, 4, 5, 4, 3, 0, 1, 0,
...
- _N. J. A. Sloane_, Feb 08 2016

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 75.

T. D. Noe, Rows n=0..100 of triangle, flattened

Cf. A003986 (OR) and A003987 (XOR). Cf. also A075173, A075175, A221146.

#include 
int main()
{
int n, k;
for (n=0; n<=20; n++){
    for(k=0; k<=n; k++){
        printf("%d, ", (k&(n - k)));
    }
    printf("\n");
}
return 0;
} /* Indranil Ghosh, Apr 01 2017 */

# Maple code for first M rows and columns of AND(i,j) table
M:=24;
f1:=n->[seq(ANDnos(i,n),i=0..M-1)];
for n from 0 to M-1 do lprint(f1(n)); od:
# N. J. A. Sloane, Feb 08 2016

Table[BitAnd[k, n - k], {n, 0, 20}, {k, 0, n}] // Flatten (* Indranil Ghosh, Apr 01 2017 *)

tabl(nn) = {for(n=0, nn, for(k=0, n, print1(bitand(k, n - k), ", "); ); print(); ); };
tabl(20) \\ Indranil Ghosh, Apr 01 2017

for n in range(21):
    print([k&(n - k) for k in range(n + 1)])
# Indranil Ghosh, Apr 01 2017

A003986 Table T(n,k) = n OR k read by antidiagonals.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 3, 3, 3, 3, 4, 3, 2, 3, 4, 5, 5, 3, 3, 5, 5, 6, 5, 6, 3, 6, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 6, 7, 4, 7, 6, 7, 8, 9, 9, 7, 7, 5, 5, 7, 7, 9, 9, 10, 9, 10, 7, 6, 5, 6, 7, 10, 9, 10, 11, 11, 11, 11, 7, 7, 7, 7, 11, 11, 11, 11, 12, 11, 10, 11, 12, 7, 6, 7, 12, 11, 10, 11, 12, 13, 13, 11

Offset: 0

Marc LeBrun

			The upper left corner of the array starts in row x=0 with columns y>=0 as:
   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
   1,  1,  3,  3,  5,  5,  7,  7,  9,  9, 11, 11, 13, ...
   2,  3,  2,  3,  6,  7,  6,  7, 10, 11, 10, 11, 14, ...
   3,  3,  3,  3,  7,  7,  7,  7, 11, 11, 11, 11, 15, ...
   4,  5,  6,  7,  4,  5,  6,  7, 12, 13, 14, 15, 12, ...
   5,  5,  7,  7,  5,  5,  7,  7, 13, 13, 15, 15, 13, ...
   6,  7,  6,  7,  6,  7,  6,  7, 14, 15, 14, 15, 14, ...
   7,  7,  7,  7,  7,  7,  7,  7, 15, 15, 15, 15, 15, ...
   8,  9, 10, 11, 12, 13, 14, 15,  8,  9, 10, 11, 12, ...
   9,  9, 11, 11, 13, 13, 15, 15,  9,  9, 11, 11, 13, ...
  10, 11, 10, 11, 14, 15, 14, 15, 10, 11, 10, 11, 14, ...

T. D. Noe, Rows n=0..100 of triangle, flattened

Cf. A003987 (XOR) and A004198 (AND). Cf. also A075173, A075175.

Antidiagonal sums are in A006583.

#include 
int main()
{
int n, k;
for (n=0; n<=20; n++){
    for(k=0; k<=n; k++){
        printf("%d, ", (k|(n - k)));
    }
    printf("\n");
}
return 0;
} /* Indranil Ghosh, Apr 01 2017 */

import Data.Bits ((.|.))
a003986 n k = (n - k) .|. k :: Int
a003986_row n = map (a003986 n) [0..n]
a003986_tabl = map a003986_row [0..]
-- Reinhard Zumkeller, Aug 05 2014

read("transforms") ;
A003986 := proc(x,y) ORnos(x,y) ;end proc:
for d from 0 to 12 do for x from 0 to d do printf("%d,", A003986(x,d-x)) ; end do: end do: # R. J. Mathar, May 28 2011

Table[BitOr[k, n - k], {n, 0, 20}, {k, 0, n}] //Flatten (* Indranil Ghosh, Apr 01 2017 *)

tabl(nn) = {for(n=0, nn, for(k=0, n, print1(bitor(k, n - k), ", "); ); print(); ); };
tabl(20) \\ Indranil Ghosh, Apr 01 2017

for n in range(21):
    print([k|(n - k) for k in range(n + 1)])
# Indranil Ghosh, Apr 01 2017

T(x,y) = T(y,x) = A080098(x,y). - R. J. Mathar, May 28 2011

Name edited by Michel Marcus, Jan 17 2023

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

Original entry on oeis.org

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))).

cp's OEIS Frontend

A075176 Inverse function of N -> N injection A075175.

Views

Author

Keywords

Comments

Crossrefs

A004198 Table of x AND y, where (x,y) = (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),...

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Maple

Mathematica

PARI

Python

A003986 Table T(n,k) = n OR k read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

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