A091255 -id:A091255 - cp's OEIS frontend

A369281 Lexicographically earliest sequence of distinct positive integers such that for any n > 0, A091255(a(n), a(n+1)) = 1.

1, 2, 3, 4, 5, 7, 6, 11, 8, 9, 13, 10, 19, 12, 21, 15, 14, 17, 16, 23, 22, 25, 18, 31, 20, 35, 24, 37, 26, 27, 32, 29, 28, 33, 38, 39, 41, 30, 47, 34, 49, 40, 55, 36, 59, 42, 43, 44, 45, 50, 51, 52, 53, 56, 57, 61, 46, 67, 48, 69, 54, 73, 58, 79, 60, 81, 62

Offset: 1

Rémy Sigrist, Jan 18 2024

In other words, the polynomials over GF(2) whose coefficients are encoded in the binary expansions of two consecutive terms are coprime.
As the polynomials over GF(2) whose coefficients are encoded in the binary expansions of two consecutive integers are not necessarily coprime (see A369317-A369318), the present sequence does not equal the identity map.
This sequence is a permutation of the positive integers with inverse A369282:
- we can always extend the sequence with some term of A014580 not yet in the sequence, hence the sequence is infinite, and all terms of A014580 appear in the sequence, in ascending order,
- for any k > 0, the first term >= A014580(k) is precisely A014580(k),
- if a(n) = A014580(k) for some n and the least value not among the first n terms, say u, is less than A014580(k), then a(n+1) = u,
- and eventually every integer will appear in the sequence.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Scatterplot of the first 2500 terms.
Rémy Sigrist, PARI program.
Index entries for sequences operating on GF(2)[X]-polynomials
Index entries for sequences that are permutations of the natural numbers

See A369293 for a similar sequence.

Cf. A014580, A091255, A369282 (inverse), A369317-A369318.

PARI
```
See Links section.
```

A369317 a(n) = A091255(n, n + 1).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 1, 3, 1, 1, 1, 3, 1, 7, 1, 1, 1, 5, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 7, 1, 3, 1, 1

Offset: 1

Rémy Sigrist, Jan 19 2024

Two consecutive integers are always coprime, however the polynomials over GF(2) whose coefficients are encoded in the binary expansions of two consecutive integers are not necessarily coprime, hence this sequence.

			The first terms, alongside the correspond GF(2)[X]-polynomials, are:
  n   a(n)  P(n)               P(n+1)             gcd(P(n), P(n+1))
  --  ----  -----------------  -----------------  -----------------
   1     1  1                  X                  1
   2     1  X                  X + 1              1
   3     1  X + 1              X^2                1
   4     1  X^2                X^2 + 1            1
   5     3  X^2 + 1            X^2 + X            X + 1
   6     1  X^2 + X            X^2 + X + 1        1
   7     1  X^2 + X + 1        X^3                1
   8     1  X^3                X^3 + 1            1
   9     3  X^3 + 1            X^3 + X            X + 1
  10     1  X^3 + X            X^3 + X + 1        1

Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A091255, A129868, A369277 (distinct values), A369318 (indices of values <> 1).

a(n) = fromdigits(lift(Vec(gcd(Mod(1, 2) * Pol(binary(n)), Mod(1, 2) * Pol(binary(n+1))))), 2)

a(A129868(k)) = 2^(k+1) - 1 for any k > 0.

A327856 The upper left triangular section of square array A091255, read by rows.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Sep 28 2019

			The triangular table starts as:
  1,
  1, 2,
  1, 1, 3,
  1, 2, 1, 4,
  1, 1, 3, 1, 5,
  1, 2, 3, 2, 3, 6,
  1, 1, 1, 1, 1, 1, 7,
  1, 2, 1, 4, 1, 2, 1, 8,
  1, 1, 3, 1, 3, 3, 7, 1, 9,
  1, 2, 3, 2, 5, 6, 1, 2, 3, 10,
  ...

Cf. A000217, A091255.

up_to = 105;
A091255sq(a,b) = fromdigits(Vec(lift(gcd(Pol(binary(a))*Mod(1, 2),Pol(binary(b))*Mod(1, 2)))),2);
A327856list(up_to) =  { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A091255sq(a,col))); (v); };
v327856 = A327856list(up_to);
A327856(n) = v327856[n];

A(n,k) = A091255(n,k), with k in range 1 .. n.

a(A000217(n)) = n.

A327857 a(n) = A091255(1+A059905(n), 1+A059906(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 2, 3, 3, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 3, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 4, 5, 3, 3, 6, 1, 1, 1, 2, 1, 1, 1, 2, 7, 1, 1, 8, 1, 1, 1, 2, 1, 1, 1, 2, 3, 3, 1, 2, 1, 3, 1, 4, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 4, 3, 5, 3, 6, 1, 3, 1, 6, 7, 1

Offset: 0

Antti Karttunen, Sep 28 2019

nonn

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for sequences operating on polynomials in ring GF(2)[X]

Cf. A059905, A059906, A091255.

A059905(n) = { my(t=1,s=0); while(n>0, s += (n%2)*t; n \= 4; t *= 2); (s); };
A059906(n) = { my(t=1,s=0); while(n>0, s += ((n%4)>=2)*t; n \= 4; t *= 2); (s); };
A091255sq(a,b) = fromdigits(Vec(lift(gcd(Pol(binary(a))*Mod(1, 2),Pol(binary(b))*Mod(1, 2)))),2);
A327857(n) = A091255sq(1+A059905(n), 1+A059906(n));

a(n) = A091255(1+A059905(n), 1+A059906(n)) = A091255(1+A059906(n), 1+A059905(n)).

A369294 Lexicographically earliest sequence of distinct positive integers such that a(1) = 1, a(2) = 2, a(3) = 3, and for any n > 3, A091255(a(n), a(n-2)) <> 1 and A091255(a(n), a(n-1)) = 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 9, 16, 7, 6, 21, 10, 35, 12, 13, 14, 23, 22, 15, 11, 17, 44, 27, 26, 29, 28, 33, 32, 31, 18, 155, 20, 81, 24, 127, 30, 49, 34, 69, 36, 173, 40, 19, 39, 38, 43, 42, 25, 45, 50, 51, 52, 53, 56, 57, 62, 63, 64, 65, 74, 71, 37, 46, 251, 48, 79

Offset: 1

Rémy Sigrist, Jan 18 2024

This sequence is a variant of the Yellowstone permutation (A098550).

Is this a permutation of the positive integers?

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Scatterplot of (n, a(n)) such that n, a(n) <= 25000
Rémy Sigrist, PARI program
Index entries for sequences operating on GF(2)[X]-polynomials

See A369293 for a similar sequence.

Cf. A091255, A098550.

PARI
```
See Links section.
```

A369302 a(n) = A091255(A369293(n), A369293(n+1)).

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 7, 7, 2, 2, 6, 3, 15, 3, 2, 4, 2, 11, 11, 3, 13, 13, 2, 3, 7, 7, 2, 2, 2, 3, 31, 31, 2, 7, 7, 2, 19, 19, 3, 5, 3, 25, 25, 2, 2, 3, 3, 3, 5, 7, 7, 4, 13, 3, 6, 3, 63, 3, 2, 4, 2, 14, 3, 61, 61, 2, 37, 37, 3, 3, 59, 59, 2, 2, 11, 11, 7, 7, 4, 2

Offset: 1

Rémy Sigrist, Jan 19 2024

All terms, except the first, are > 1.

			a(42) = A091255(A369293(42), A369293(43)) = A091255(43, 25) = 25.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A073734, A091255, A369293.

PARI
```
See Links section.
```

A369318 Numbers k such that A091255(k, k + 1) <> 1.

Original entry on oeis.org

5, 9, 17, 23, 27, 29, 33, 35, 39, 45, 53, 57, 65, 71, 77, 83, 85, 89, 95, 101, 105, 107, 113, 119, 125, 129, 135, 139, 141, 149, 153, 159, 165, 169, 177, 179, 183, 189, 195, 197, 201, 209, 215, 221, 223, 225, 231, 237, 245, 249, 251, 257, 259, 263, 269, 277

Offset: 1

Rémy Sigrist, Jan 19 2024

Equivalently, numbers k such that A369317(k) <> 1.

			The first terms, alongside the correspond GF(2)[X]-polynomials, are:
  n   a(n)  P(a(n))              P(a(n)+1)            gcd(P(a(n)), P(a(n)+1))
  --  ----  -------------------  -------------------  -----------------------
   1     5  X^2 + 1              X^2 + X              X + 1
   2     9  X^3 + 1              X^3 + X              X + 1
   3    17  X^4 + 1              X^4 + X              X + 1
   4    23  X^4 + X^2 + X + 1    X^4 + X^3            X + 1
   5    27  X^4 + X^3 + X + 1    X^4 + X^3 + X^2      X^2 + X + 1
   6    29  X^4 + X^3 + X^2 + 1  X^4 + X^3 + X^2 + X  X + 1
   7    33  X^5 + 1              X^5 + X              X + 1
   8    35  X^5 + X + 1          X^5 + X^2            X^2 + X + 1
   9    39  X^5 + X^2 + X + 1    X^5 + X^3            X^2 + 1
  10    45  X^5 + X^3 + X^2 + 1  X^5 + X^3 + X^2 + X  X + 1

Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A091255, A369317.

is(n) = fromdigits(lift(Vec(gcd(Mod(1, 2) * Pol(binary(n)), Mod(1, 2) * Pol(binary(n+1))))), 2) != 1

A048720 Multiplication table {0..i} X {0..j} of binary polynomials (polynomials over GF(2)) interpreted as binary vectors, then written in base 10; or, binary multiplication without carries.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 4, 3, 0, 0, 4, 6, 6, 4, 0, 0, 5, 8, 5, 8, 5, 0, 0, 6, 10, 12, 12, 10, 6, 0, 0, 7, 12, 15, 16, 15, 12, 7, 0, 0, 8, 14, 10, 20, 20, 10, 14, 8, 0, 0, 9, 16, 9, 24, 17, 24, 9, 16, 9, 0, 0, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 0, 0, 11, 20, 27, 32, 27, 20, 27, 32, 27, 20, 11, 0

Offset: 0

Antti Karttunen, Apr 26 1999

Essentially same as A091257 but computed starting from offset 0 instead of 1.
Each polynomial in GF(2)[X] is encoded as the number whose binary representation is given by the coefficients of the polynomial, e.g., 13 = 2^3 + 2^2 + 2^0 = 1101_2 encodes 1*X^3 + 1*X^2 + 0*X^1 + 1*X^0 = X^3 + X^2 + X^0. - Antti Karttunen and Peter Munn, Jan 22 2021
To listen to this sequence, I find instrument 99 (crystal) works well with the other parameters defaulted. - Peter Munn, Nov 01 2022

			Top left corner of array:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ...
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 ...
  0  3  6  5 12 15 10  9 24 27 30 29 20 23 18 17 ...
  ...
From _Antti Karttunen_ and _Peter Munn_, Jan 23 2021: (Start)
Multiplying 10 (= 1010_2) and 11 (= 1011_2), in binary results in:
     1011
  *  1010
  -------
   c1011
  1011
  -------
  1101110  (110 in decimal),
and we see that there is a carry-bit (marked c) affecting the result.
In carryless binary multiplication, the second part of the process (in which the intermediate results are summed) looks like this:
    1011
  1011
  -------
  1001110  (78 in decimal).
(End)

Alois P. Heinz, Antidiagonals n = 0..200, flattened
Antti Karttunen, Scheme-program for computing this sequence.
N. J. A. Sloane, Transforms: Maple implementation of binary eXclusive OR (XORnos).
Index entries for sequences related to carryless arithmetic
Index entries for sequences related to polynomials in ring GF(2)[X]

Cf. A051776 (Nim-product), A091257 (subtable).
Carryless multiplication in other bases: A325820 (3), A059692 (10).
Ordinary {0..i} * {0..j} multiplication table: A004247 and its differences from this: A061858 (which lists further sequences related to presence/absence of carry in binary multiplication).
Carryless product of the prime factors of n: A234741.
Binary irreducible polynomials ("X-primes"): A014580, factorization table: A256170, table of "X-powers": A048723, powers of 3: A001317, rearranged subtable with distinct terms (comparable to A054582): A277820.
See A014580 for further sequences related to the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the integer encoding.
Row/column 3: A048724 (even bisection of A003188), 5: A048725, 6: A048726, 7: A048727; main diagonal: A000695.
Associated additive operation: A003987.
Equivalent sequences, as compared with standard integer multiplication: A048631 (factorials), A091242 (composites), A091255 (gcd), A091256 (lcm), A280500 (division).
See A091202 (and its variants) and A278233 for maps from/to ordinary multiplication.
See A115871, A115872 and A277320 for tables related to cross-domain congruences.

trinv := n -> floor((1+sqrt(1+8*n))/2); # Gives integral inverses of the triangular numbers
# Binary multiplication of nn and mm, but without carries (use XOR instead of ADD):
Xmult := proc(nn,mm) local n,m,s; n := nn; m := mm; s := 0; while (n > 0) do if(1 = (n mod 2)) then s := XORnos(s,m); fi; n := floor(n/2); # Shift n right one bit. m := m*2; # Shift m left one bit. od; RETURN(s); end;

trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2];
Xmult[nn_, mm_] := Module[{n = nn, m = mm, s = 0}, While[n > 0, If[1 == Mod[n, 2], s = BitXor[s, m]]; n = Floor[n/2]; m = m*2]; Return[s]];
a[n_] := Xmult[(trinv[n] - 1)*((1/2)*trinv[n] + 1) - n, n - (trinv[n]*(trinv[n] - 1))/2];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 16 2015, updated Mar 06 2016 after Maple *)

up_to = 104;
A048720sq(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A048720list(up_to) = { my(v = vector(1+up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A048720sq(col, a-col))); (v); };
v048720 = A048720list(up_to);
A048720(n) = v048720[1+n]; \\ Antti Karttunen, Feb 15 2021

a(n) = Xmult( (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n), (n-((trinv(n)*(trinv(n)-1))/2)) );
T(2b, c)=T(c, 2b)=T(b, 2c)=2T(b, c); T(2b+1, c)=T(c, 2b+1)=2T(b, c) XOR c - Henry Bottomley, Mar 16 2001
For n >= 0, A003188(2n) = T(n, 3); A003188(2n+1) = T(n, 3) XOR 1, where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Feb 11 2021

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

A280500 Square array for division in ring GF(2)[X]: A(r,c) = r/c, or 0 if c is not a divisor of r, where the binary expansion of each number defines the corresponding (0,1)-polynomial.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 09 2017

The array A(row,col) is read by descending antidiagonals: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

			The top left 17 X 17 corner of the array:
col: 1  2   3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
     --------------------------------------------------
     1, 0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     2, 1,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     3, 0,  1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     4, 2,  0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     5, 0,  3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     6, 3,  2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     7, 0,  0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     8, 4,  0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
     9, 0,  7, 0, 0, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0
    10, 5,  6, 0, 2, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
    11, 0,  0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0
    12, 6,  4, 3, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0
    13, 0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0
    14, 7,  0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0
    15, 0,  5, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0
    16, 8,  0, 4, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0
    17, 0, 15, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 1
    ---------------------------------------------------
7 ("111" in binary) encodes polynomial X^2 + X + 1, which is irreducible over GF(2) (7 is in A014580), thus it is divisible only by itself and 1, and for any other values of c than 1 and 7, A(7,c) = 0.
9 ("1001" in binary) encodes polynomial X^3 + 1, which is factored over GF(2) as (X+1)(X^2 + X + 1), and thus A(9,3) = 7 and A(9,7) = 3 because the polynomial X + 1 is encoded by 3 ("11" in binary).

Cf. A001317, A014580, A048720, A091255, A268389, A268669.
Cf. A280499 for the lower triangular region (A280494 for its transpose).
Cf. also A106449, A280502, A280504, A280506.

up_to = 10440;
A280500sq(a,b) = { my(Pa=Pol(binary(a))*Mod(1, 2), Pb=Pol(binary(b))*Mod(1, 2)); if(0!=lift(Pa % Pb), 0, fromdigits(Vec(lift(Pa/Pb)),2)); };
A280500list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A280500sq(col,(a-(col-1))))); (v); };
v280500 = A280500list(up_to);
A280500(n) = v280500[n]; \\ Antti Karttunen, Jan 05 2025

(define (A280500 n) (A280500bi (A002260 n) (A004736 n)))
;; A very naive implementation:
(define (A280500bi row col) (let loop ((d row)) (cond ((zero? d) d) ((= (A048720bi d col) row) d) (else (loop (- d 1)))))) ;; A048720bi implements the carryless binary multiplication A048720.

A(row,col) = the unique d such that A048720(d,col) = row, provided that such d exists, otherwise zero.
Other identities. For all n >= 1:
A(n, A001317(A268389(n))) = A268669(n).

cp's OEIS Frontend

A369281 Lexicographically earliest sequence of distinct positive integers such that for any n > 0, A091255(a(n), a(n+1)) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A369317 a(n) = A091255(n, n + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A327856 The upper left triangular section of square array A091255, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A327857 a(n) = A091255(1+A059905(n), 1+A059906(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A369294 Lexicographically earliest sequence of distinct positive integers such that a(1) = 1, a(2) = 2, a(3) = 3, and for any n > 3, A091255(a(n), a(n-2)) <> 1 and A091255(a(n), a(n-1)) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A369302 a(n) = A091255(A369293(n), A369293(n+1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A369318 Numbers k such that A091255(k, k + 1) <> 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A048720 Multiplication table {0..i} X {0..j} of binary polynomials (polynomials over GF(2)) interpreted as binary vectors, then written in base 10; or, binary multiplication without carries.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica