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

%I #35 Oct 14 2019 13:51:44

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

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

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

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

%C Array is read by antidiagonals, with (x,y) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ...

%C Analogous to A003989.

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

%H Antti Karttunen, <a href="/A091255/b091255.txt">Table of n, a(n) for n = 1..10440; the first 144 antidiagonals of array</a>

%H A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</a>

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

%H <a href="/index/La#Lattices">Index entries for sequences related to Lattices</a>

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

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

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

%e +---------------------------------------------------------------

%e 1: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 2: 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, ...

%e 3: 1, 1, 3, 1, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 3, 1, 3, ...

%e 4: 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, ...

%e 5: 1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 5, 1, 5, ...

%e 6: 1, 2, 3, 2, 3, 6, 1, 2, 3, 6, 1, 6, 1, 2, 3, 2, 3, ...

%e 7: 1, 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 1, 1, 7, 1, 1, 1, ...

%e 8: 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, ...

%e 9: 1, 1, 3, 1, 3, 3, 7, 1, 9, 3, 1, 3, 1, 7, 3, 1, 3, ...

%e 10: 1, 2, 3, 2, 5, 6, 1, 2, 3, 10, 1, 6, 1, 2, 5, 2, 5, ...

%e 11: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, ...

%e 12: 1, 2, 3, 4, 3, 6, 1, 4, 3, 6, 1, 12, 1, 2, 3, 4, 3, ...

%e 13: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, ...

%e 14: 1, 2, 1, 2, 1, 2, 7, 2, 7, 2, 1, 2, 1, 14, 1, 2, 1, ...

%e 15: 1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 15, 1, 15, ...

%e 16: 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, ...

%e 17: 1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 15, 1, 17, ...

%e ...

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

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

%o (PARI) 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

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

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

%K nonn,tabl,look

%O 1,5

%A _Antti Karttunen_, Jan 03 2004

%E Data section extended up to a(105), examples added by _Antti Karttunen_, Sep 28 2019