login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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
Sequence in context: A307844 A114026 A368889 * A242604 A212150 A203838
KEYWORD
nonn
AUTHOR
Robert Israel, Jul 23 2014
EXTENSIONS
More terms from Robert Israel, Dec 26 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)