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

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

Offset: 1

Author

Robert Israel, Jul 23 2014

Keywords

• nonn

Comments

This is using the gcd in the polynomial ring GF(2)[X].

Examples

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

Links

• Robert Israel, Table of n, a(n) for n = 1..118
• Robert Israel, Probability of coprime polynomials, Math Overflow question (Oct. 2013).

Programs

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

Extensions

More terms from Robert Israel, Dec 26 2017