|
|
A335383
|
|
a(n) is the number of irreducible Mersenne polynomials in GF(2)[x] that have degree n.
|
|
0
|
|
|
1, 2, 2, 2, 2, 4, 0, 4, 2, 2, 2, 0, 2, 6, 0, 6, 2, 0, 2, 2, 2, 4, 0, 4, 0, 0, 8, 2, 2, 8, 0, 4, 2, 2, 2, 0, 0, 6, 0, 4, 0, 0, 2, 0, 2, 8, 0, 8, 0, 0, 8, 0, 0, 4, 0, 8, 2, 0, 8, 0, 2, 8, 0, 4, 0, 0, 4, 0, 0, 10, 0, 6, 2, 0, 2, 0, 0, 4, 0, 6, 0, 0, 6, 0, 2, 2, 0, 2, 0, 0, 2, 2, 2, 4, 0, 8, 4, 0, 6
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,2
|
|
COMMENTS
|
A Mersenne polynomial is a binary (i.e., an element of GF(2)[x]) polynomial M, of degree > 1, such that M+1 has only 0 and 1 as roots in a fixed algebraic closure of GF(2).
If for some positive integers a,b, M = x^a(x+1)^b+1 is an irreducible Mersenne polynomial, then gcd(a,b)=1. This condition is not sufficient.
There is no known formula for a(n). Of course it is bounded above by the total number of prime (irreducible) binary polynomials of degree n, but this is a too weak upper bound. A trivial, better upper bound, is simply n-1, the total number of Mersenne polynomials (prime or not) of degree n.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n = 5 one has a(5) = 2 since there are 2 irreducible Mersenne polynomials of degree 5. Namely, x^2*(x+1)^3+1 and x^3*(x+1)^2+1.
For n = 8, a(8) = 0 since there are no irreducible Mersenne polynomial of degree 8.
|
|
PROG
|
(PARI) a(n) = sum(k=1, n-1, polisirreducible(Mod(1, 2)*(x^(n-k)*(x+1)^k+1))); \\ Michel Marcus, Jun 07 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|