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

Author

Antti Karttunen, Jan 09 2017

Keywords

• nonn
• tabl

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.

Examples

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

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]

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.

Programs

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.

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