A091255 - OEIS

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.

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

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

LINKS

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

A. Karttunen, Scheme-program for computing this sequence.

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

Index entries for sequences related to Lattices

FORMULA

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

EXAMPLE

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.

PROG

(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

CROSSREFS

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.

Sequence in context: A159923 A287957 A003989 * A332013 A324350 A175466

Adjacent sequences: A091252 A091253 A091254 * A091256 A091257 A091258

KEYWORD

nonn,tabl,look

AUTHOR

Antti Karttunen, Jan 03 2004

EXTENSIONS

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

STATUS

approved