login
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.
10

%I #21 Jul 07 2018 16:23:28

%S 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,

%T 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,

%U 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

%N 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.

%C 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.

%H Antti Karttunen, <a href="/A280500/b280500.txt">Table of n, a(n) for n = 1..8256; the first 128 antidiagonals of array</a>

%H <a href="/index/Ge#GF2X">Index entries for sequences operating on polynomials in ring GF(2)[X]</a>

%F A(row,col) = the unique d such that A048720(d,col) = row, provided that such d exists, otherwise zero.

%F Other identities. For all n >= 1:

%F A(n, A001317(A268389(n))) = A268669(n).

%e The top left 17 X 17 corner of the array:

%e col: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

%e --------------------------------------------------

%e 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 4, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 5, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 6, 3, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 7, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 8, 4, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0

%e 9, 0, 7, 0, 0, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0

%e 10, 5, 6, 0, 2, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0

%e 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0

%e 12, 6, 4, 3, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0

%e 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0

%e 14, 7, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0

%e 15, 0, 5, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0

%e 16, 8, 0, 4, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0

%e 17, 0, 15, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 1

%e ---------------------------------------------------

%e 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.

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

%o (Scheme)

%o (define (A280500 n) (A280500bi (A002260 n) (A004736 n)))

%o ;; A very naive implementation:

%o (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.

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

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

%Y Cf. also A280502, A280504, A280506.

%K nonn,tabl

%O 1,3

%A _Antti Karttunen_, Jan 09 2017