cp's OEIS Frontend

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

%I A245488 #18 Apr 12 2019 10:51:41
%S A245488 9,56,180,489,1019,1895,3299,5308,8092,11954,17086,23346,31634,41672,
%T A245488 53892,69055,86779,107795,132593,161137,193749,232283,275561,323469,
%U A245488 379373,441693,509675,587289,673043,766707,870975,986172,1109528,1247292,1396452,1557052,1734814,1923922,2127524,2350182
%N 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).
%C A245488 This is using the gcd in the polynomial ring GF(2)[X].
%H A245488 Robert Israel, <a href="/A245488/b245488.txt">Table of n, a(n) for n = 1..118</a>
%H A245488 Robert Israel, <a href="http://mathoverflow.net/questions/145757/probability-of-coprime-polynomials">Probability of coprime polynomials</a>, Math Overflow question (Oct. 2013).
%e A245488 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).
%p A245488 increment:= proc(n) local tot,m1,m2,n1,n2,f1,f2;
%p A245488   tot:= 0;
%p A245488 # first case: m2 = n
%p A245488   m2:= n;
%p A245488   for m1 from 0 to m2 do
%p A245488     for n2 from 0 to n do
%p A245488       for n1 from 0 to `if`(m1=m2, n2,n) do
%p A245488          f1:= x^m1 + (1+x)^n1 mod 2;
%p A245488          f2:= x^m2 + (1+x)^n2 mod 2;
%p A245488          if Gcd(f1,f2) mod 2 = 1 then
%p A245488            tot:= tot + `if`(m1=m2 and n1=n2,1,2);
%p A245488          fi
%p A245488        od
%p A245488      od
%p A245488    od;
%p A245488 # second case: m2 < n, n2 = n
%p A245488   n2:= n;
%p A245488   for m2 from 0 to n-1 do
%p A245488     for m1 from 0 to m2 do
%p A245488       for n1 from 0 to n do
%p A245488          f1:= x^m1 + (1+x)^n1 mod 2;
%p A245488          f2:= x^m2 + (1+x)^n2 mod 2;
%p A245488          if Gcd(f1,f2) mod 2 = 1 then
%p A245488            tot:= tot + `if`(m1=m2 and n1=n2,1,2);
%p A245488          fi
%p A245488        od
%p A245488      od
%p A245488    od;
%p A245488 # third case: m2 < n, n2 < n, n1 = n.  Here m1 < m2
%p A245488   n1:= n;
%p A245488   for m2 from 0 to n-1 do
%p A245488     for m1 from 0 to m2-1 do
%p A245488       for n2 from 0 to n-1 do
%p A245488          f1:= x^m1 + (1+x)^n1 mod 2;
%p A245488          f2:= x^m2 + (1+x)^n2 mod 2;
%p A245488          if Gcd(f1,f2) mod 2 = 1 then
%p A245488            tot:= tot + 2;
%p A245488          fi
%p A245488        od
%p A245488      od
%p A245488    od;
%p A245488 tot
%p A245488 end proc:
%p A245488 A[0]:= 0:
%p A245488 for i from 1 to 30 do
%p A245488   A[i]:= A[i-1] + increment(i)
%p A245488 od:
%p A245488 seq(A[i],i=1..30);
%t A245488 (* This program is not suitable to compute a large number of terms. *)
%t A245488 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;
%t A245488 Table[Print[n , " ", a[n]]; a[n], {n, 1, 20}] (* _Jean-François Alcover_, Apr 12 2019 *)
%K A245488 nonn
%O A245488 1,1
%A A245488 _Robert Israel_, Jul 23 2014
%E A245488 More terms from _Robert Israel_, Dec 26 2017