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