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.

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,3

Comments

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.

Links

Antti Karttunen, Table of n, a(n) for n = 1..10440; the first 144 antidiagonals of array

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

Formula

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

Example

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

Prog

(PARI)
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
(Scheme)
(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.

Crossrefs

Cf. A001317, A014580, A048720, A091255, A268389, A268669.

Cf. A280499 for the lower triangular region (A280494 for its transpose).

Cf. also A106449, A280502, A280504, A280506.

Sequence in context: A333687 A210572 A085855 * A309576 A128132 A127701

Adjacent sequences: A280497 A280498 A280499 * A280501 A280502 A280503

Keyword

nonn,tabl,changed

Author

Antti Karttunen, Jan 09 2017

Status

approved