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
Offset: 1
Examples
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.
Links
Crossrefs
Programs
-
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
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
Extensions
Data section extended up to a(105), examples added by Antti Karttunen, Sep 28 2019
Comments