|
|
A001115
|
|
Maximal number of pairwise relatively prime polynomials of degree n over GF(2).
(Formerly M0575 N0209)
|
|
1
|
|
|
1, 2, 3, 4, 6, 9, 14, 23, 38, 64, 113, 200, 358, 653, 1202, 2223, 4151, 7781, 14659, 27721, 52603, 100084, 190969, 365134, 699617, 1342923, 2582172, 4972385, 9588933, 18515328, 35794987, 69278386, 134224480, 260309786, 505302925, 981723316, 1908898002, 3714597352, 7233673969, 14096361346, 27487875487
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
For n>=4, a maximal set can be chosen by taking all irreducible polynomials of degree n, the squares of all irreducible polynomials of degree n/2 (if n is even) and, for each irreducible polynomial p of degree d with 1 <= d < n/2, a product p*q where q is irreducible of degree n-d. The q's should all be distinct, which is possible when n>=4.
|
|
REFERENCES
|
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = P(n) + Sum_{i=1..floor(n/2)} P(i), where P(n) = A001037(n) = number of irreducible polynomials of degree n.
|
|
EXAMPLE
|
n=1: x and x+1.
n=2: x^2, x^2+1, x^2+x+1.
n=3: x^3, x^3+1, x^3+x+1, x^3+x^2+1.
|
|
MATHEMATICA
|
p[0]=1; p[n_] := Sum[If[Mod[n, d]==0, MoebiusMu[n/d]2^d, 0], {d, 1, n}]/n; a[n_] := p[n]+Sum[p[i], {i, 1, Floor[n/2]}]
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|