|
|
A062692
|
|
Number of irreducible polynomials over F_2 of degree at most n.
|
|
9
|
|
|
2, 3, 5, 8, 14, 23, 41, 71, 127, 226, 412, 747, 1377, 2538, 4720, 8800, 16510, 31042, 58636, 111013, 210871, 401428, 766150, 1465020, 2807196, 5387991, 10358999, 19945394, 38458184, 74248451, 143522117, 277737797, 538038783, 1043325198
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Number of binary pre-necklaces of length n. - Joerg Arndt, Jul 20 2013
|
|
LINKS
|
G. Fici and Zs. Lipták, On Prefix Normal Words, Developments in Language Theory 2011, Lecture Notes in Computer Science 6795, 228-238.
Kenneth H. Hicks, Gary L. Mullen, and Ikuro Sato, Distribution of irreducible polynomials over F_2, in Finite Fields with Applications to Coding Theory, Cryptography and Related Areas (Oaxaca, 2001), 177-186, Springer, Berlin, 2002.
|
|
FORMULA
|
a(n) = Sum_{m=1..n} (1/m)*Sum_{d | m } mu(d)*2^{m/d}.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k)*log(1/(1 - 2*x^k))/k. - Ilya Gutkovskiy, Nov 11 2019
|
|
MAPLE
|
with(numtheory):for n from 1 to 113 do sum3 := 0:for m from 1 to n do sum2 := 0:a := divisors(m):for h from 1 to nops(a) do sum2 := sum2+mobius(a[h])*2^(m/a[h]):end do:sum3 := sum3+sum2/m:end do:s[n] := sum3:end do:q := seq(s[j], j=1..113);
|
|
MATHEMATICA
|
a[n_] := Sum[1/m DivisorSum[m, MoebiusMu[#]*2^(m/#)&], {m, 1, n}]; Array[a, 34] (* Jean-François Alcover, Dec 07 2015 *)
f[n_] := DivisorSum[n, MoebiusMu[#] * 2^(n/#) &] / n; Accumulate[Array[f, 30]] (* Amiram Eldar, Aug 24 2023 *)
|
|
PROG
|
(PARI) a(n)=sum(m=1, n, 1/m* sumdiv(m, d, moebius(d)*2^(m/d) ) ); /* Joerg Arndt, Jul 04 2011 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Gary L Mullen (mullen(AT)math.psu.edu), Jul 04 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|