|
|
A245488
|
|
Number of (m1,m2,n1,n2) in {0,1,...,n}^4 such that gcd(X^m1 + (1+X)^n1, X^m2 + (1+X)^n2) = 1 over GF(2).
|
|
3
|
|
|
9, 56, 180, 489, 1019, 1895, 3299, 5308, 8092, 11954, 17086, 23346, 31634, 41672, 53892, 69055, 86779, 107795, 132593, 161137, 193749, 232283, 275561, 323469, 379373, 441693, 509675, 587289, 673043, 766707, 870975, 986172, 1109528, 1247292, 1396452, 1557052, 1734814, 1923922, 2127524, 2350182
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
This is using the gcd in the polynomial ring GF(2)[X].
|
|
LINKS
|
|
|
EXAMPLE
|
For n=1 there are 9 such 4-tuples: [0,1,0,1],[0,1,1,0],[0,1,1,1],[1,0,0,1],[1,0,1,0],[1,0,1,1],[1,1,1,0] and [1,1,1,1]. Thus [0,1,1,0] is included because X^0 + (1+X)^1 = X and X^1 + (1+X)^0 = 1 + X and these are coprime over GF(2).
|
|
MAPLE
|
increment:= proc(n) local tot, m1, m2, n1, n2, f1, f2;
tot:= 0;
# first case: m2 = n
m2:= n;
for m1 from 0 to m2 do
for n2 from 0 to n do
for n1 from 0 to `if`(m1=m2, n2, n) do
f1:= x^m1 + (1+x)^n1 mod 2;
f2:= x^m2 + (1+x)^n2 mod 2;
if Gcd(f1, f2) mod 2 = 1 then
tot:= tot + `if`(m1=m2 and n1=n2, 1, 2);
fi
od
od
od;
# second case: m2 < n, n2 = n
n2:= n;
for m2 from 0 to n-1 do
for m1 from 0 to m2 do
for n1 from 0 to n do
f1:= x^m1 + (1+x)^n1 mod 2;
f2:= x^m2 + (1+x)^n2 mod 2;
if Gcd(f1, f2) mod 2 = 1 then
tot:= tot + `if`(m1=m2 and n1=n2, 1, 2);
fi
od
od
od;
# third case: m2 < n, n2 < n, n1 = n. Here m1 < m2
n1:= n;
for m2 from 0 to n-1 do
for m1 from 0 to m2-1 do
for n2 from 0 to n-1 do
f1:= x^m1 + (1+x)^n1 mod 2;
f2:= x^m2 + (1+x)^n2 mod 2;
if Gcd(f1, f2) mod 2 = 1 then
tot:= tot + 2;
fi
od
od
od;
tot
end proc:
A[0]:= 0:
for i from 1 to 30 do
A[i]:= A[i-1] + increment(i)
od:
seq(A[i], i=1..30);
|
|
MATHEMATICA
|
(* This program is not suitable to compute a large number of terms. *)
a[n_] := a[n] = Select[Tuples[Range[0, n], {4}], PolynomialGCD[X^#[[1]] + (1+X)^#[[2]], X^#[[3]] + (1+X)^#[[4]], Modulus -> 2] == 1&] // Length;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|