A091256 -id:A091256 - cp's OEIS frontend

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.

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

A091255 Square array computed from gcd(P(x),P(y)) where P(x) and P(y) are polynomials with coefficients in {0,1} given by the binary expansions of x and y, and the polynomial calculation is done over GF(2), with the result converted back to a binary number, and then expressed in decimal. Array is symmetric, and is read by falling 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, 3, 4, 3, 2, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 2, 1, 2, 5, 2, 1, 2, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 3, 2, 7, 2, 3, 2, 1, 2, 1, 1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1

Offset: 1

Antti Karttunen, Jan 03 2004

Array is read by antidiagonals, with (x,y) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ...
Analogous to A003989.
"Coded in binary" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where a(k)=0 or 1).

			The top left 17 X 17 corner of the array:
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
    +---------------------------------------------------------------
   1: 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,  2,  1, ...
   3: 1, 1, 3, 1, 3, 3, 1, 1, 3,  3,  1,  3,  1,  1,  3,  1,  3, ...
   4: 1, 2, 1, 4, 1, 2, 1, 4, 1,  2,  1,  4,  1,  2,  1,  4,  1, ...
   5: 1, 1, 3, 1, 5, 3, 1, 1, 3,  5,  1,  3,  1,  1,  5,  1,  5, ...
   6: 1, 2, 3, 2, 3, 6, 1, 2, 3,  6,  1,  6,  1,  2,  3,  2,  3, ...
   7: 1, 1, 1, 1, 1, 1, 7, 1, 7,  1,  1,  1,  1,  7,  1,  1,  1, ...
   8: 1, 2, 1, 4, 1, 2, 1, 8, 1,  2,  1,  4,  1,  2,  1,  8,  1, ...
   9: 1, 1, 3, 1, 3, 3, 7, 1, 9,  3,  1,  3,  1,  7,  3,  1,  3, ...
  10: 1, 2, 3, 2, 5, 6, 1, 2, 3, 10,  1,  6,  1,  2,  5,  2,  5, ...
  11: 1, 1, 1, 1, 1, 1, 1, 1, 1,  1, 11,  1,  1,  1,  1,  1,  1, ...
  12: 1, 2, 3, 4, 3, 6, 1, 4, 3,  6,  1, 12,  1,  2,  3,  4,  3, ...
  13: 1, 1, 1, 1, 1, 1, 1, 1, 1,  1,  1,  1, 13,  1,  1,  1,  1, ...
  14: 1, 2, 1, 2, 1, 2, 7, 2, 7,  2,  1,  2,  1, 14,  1,  2,  1, ...
  15: 1, 1, 3, 1, 5, 3, 1, 1, 3,  5,  1,  3,  1,  1, 15,  1, 15, ...
  16: 1, 2, 1, 4, 1, 2, 1, 8, 1,  2,  1,  4,  1,  2,  1, 16,  1, ...
  17: 1, 1, 3, 1, 5, 3, 1, 1, 3,  5,  1,  3,  1,  1,  15, 1, 17, ...
  ...
3, which is "11" in binary, encodes polynomial X + 1, while 7 ("111" in binary) encodes polynomial X^2 + X + 1, whereas 9 ("1001" in binary), encodes polynomial X^3 + 1. Now (X + 1)(X^2 + X + 1) = (X^3 + 1) when the polynomials are multiplied over GF(2), or equally, when multiplication of integers 3 and 7 is done as a carryless base-2 product (A048720(3,7) = 9). Thus it follows that A(3,9) = A(9,3) = 3 and A(7,9) = A(9,7) = 7.
Furthermore, 5 ("101" in binary) encodes polynomial X^2 + 1 which is equal to (X + 1)(X + 1) in GF(2)[X], thus A(5,9) = A(9,5) = 3, as the irreducible polynomial (X + 1) is the only common factor for polynomials X^2 + 1 and X^3 + 1.

Cf. A003987, A048720, A091256, A091257, A106449, A280500, A280501, A280503, A280505, A286153, A325634, A325635, A325825.

Cf. also A327856 (the upper left triangular section of this array), A327857.

A091255sq(a,b) = fromdigits(Vec(lift(gcd(Pol(binary(a))*Mod(1, 2),Pol(binary(b))*Mod(1, 2)))),2); \\ Antti Karttunen, Aug 12 2019

A(x,y) = A(y,x) = A(x, A003987(x,y)) = A(A003987(x,y), y), where A003987 gives the bitwise-XOR of its two arguments. - Antti Karttunen, Sep 28 2019

Data section extended up to a(105), examples added by Antti Karttunen, Sep 28 2019

A091257 Multiplication table A x B computed for polynomials over GF(2), where (A,B) runs as (1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 03 2004

Essentially same as A048720 but computed starting from offset one instead of zero. Analogous to A003991. Each n occurs A091220(n) times.

Alois P. Heinz, Antidiagonals n = 1..200, flattened
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials

a(n) = A048720bi(A091255(n), A091256(n)) because the identity A x B = gcd(A, B) x lcm(A, B) holds also in the polynomial ring GF(2)[X].

A346795 Irregular triangle T(n, k), n > 0, k = 1..A091220(n), read by rows; the n-th row gives, in ascending order, the distinct integers k such that A048720(k, m) = n for some m.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 2, 4, 1, 3, 5, 1, 2, 3, 6, 1, 7, 1, 2, 4, 8, 1, 3, 7, 9, 1, 2, 3, 5, 6, 10, 1, 11, 1, 2, 3, 4, 6, 12, 1, 13, 1, 2, 7, 14, 1, 3, 5, 15, 1, 2, 4, 8, 16, 1, 3, 5, 15, 17, 1, 2, 3, 6, 7, 9, 14, 18, 1, 19, 1, 2, 3, 4, 5, 6, 10, 12, 20, 1, 7, 21

Offset: 1

Rémy Sigrist, Sep 29 2021

The n-th row corresponds to the divisors of the n-th GF(2)[X]-polynomial.
The greatest value both in the n-th row and in the k-th row corresponds to A091255(n, k).
The index of the first row containing both n and k corresponds to A091256(n, k).

			The triangle starts:
      1:   [1]
      2:   [1, 2]
      3:   [1, 3]
      4:   [1, 2, 4]
      5:   [1, 3, 5]
      6:   [1, 2, 3, 6]
      7:   [1, 7]
      8:   [1, 2, 4, 8]
      9:   [1, 3, 7, 9]
     10:   [1, 2, 3, 5, 6, 10]
     11:   [1, 11]
     12:   [1, 2, 3, 4, 6, 12]
     13:   [1, 13]
     14:   [1, 2, 7, 14]
     15:   [1, 3, 5, 15]

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

Cf. A048720, A091220, A091255, A091256, A091257, A178908, A280493, A348135.

PARI
```
See Links section.
```

T(n, 1) = 1.
T(n, A091220(n)) = n.
Sum_{k = 1..A091220(n)} T(n, k) = A280493(n).
T(n, 1) XOR ... XOR T(n, A091220(n)) = A178908(n) (where XOR denotes the bitwise XOR operator).

cp's OEIS Frontend

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

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A091257 Multiplication table A x B computed for polynomials over GF(2), where (A,B) runs as (1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...

Views

Author

Keywords

Comments

Links

Crossrefs

A346795 Irregular triangle T(n, k), n > 0, k = 1..A091220(n), read by rows; the n-th row gives, in ascending order, the distinct integers k such that A048720(k, m) = n for some m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula