OFFSET
1,1
COMMENTS
This is using the gcd in the polynomial ring GF(2)[X].
LINKS
Robert Israel, Table of n, a(n) for n = 1..118
Robert Israel, Probability of coprime polynomials, Math Overflow question (Oct. 2013).
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;
Table[Print[n , " ", a[n]]; a[n], {n, 1, 20}] (* Jean-François Alcover, Apr 12 2019 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Robert Israel, Jul 23 2014
EXTENSIONS
More terms from Robert Israel, Dec 26 2017
STATUS
approved