%I #47 Aug 24 2023 03:14:03
%S 2,3,5,8,14,23,41,71,127,226,412,747,1377,2538,4720,8800,16510,31042,
%T 58636,111013,210871,401428,766150,1465020,2807196,5387991,10358999,
%U 19945394,38458184,74248451,143522117,277737797,538038783,1043325198
%N Number of irreducible polynomials over F_2 of degree at most n.
%C Number of binary pre-necklaces of length n. - _Joerg Arndt_, Jul 20 2013
%H G. C. Greubel, <a href="/A062692/b062692.txt">Table of n, a(n) for n = 1..3320</a>
%H P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, <a href="http://www.cis.uoguelph.ca/~sawada/papers/pnf.pdf">On prefix normal words and prefix normal forms</a>, Preprint, 2016.
%H G. Fici and Zs. Lipták, <a href="http://www.i3s.unice.fr/~mh/RR/2011/RR-11-03-G.FICI.pdf">On Prefix Normal Words</a>.
%H G. Fici and Zs. Lipták, <a href="http://dx.doi.org/10.1007/978-3-642-22321-1_20">On Prefix Normal Words</a>, Developments in Language Theory 2011, Lecture Notes in Computer Science 6795, 228-238.
%H Kenneth H. Hicks, Gary L. Mullen, and Ikuro Sato, <a href="https://doi.org/10.1007/978-3-642-59435-9_13">Distribution of irreducible polynomials over F_2, in Finite Fields with Applications to Coding Theory</a>, Cryptography and Related Areas (Oaxaca, 2001), 177-186, Springer, Berlin, 2002.
%H M. Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/MZV2011IMSc.pdf">Lectures on Multiple Zeta Values</a>, IMSC 2011.
%F a(n) = Sum_{m=1..n} (1/m)*Sum_{d | m } mu(d)*2^{m/d}.
%F a(n) = A091226(2^(n+1)).
%F G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k)*log(1/(1 - 2*x^k))/k. - _Ilya Gutkovskiy_, Nov 11 2019
%p 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);
%t a[n_] := Sum[1/m DivisorSum[m, MoebiusMu[#]*2^(m/#)&], {m, 1, n}]; Array[a, 34] (* _Jean-François Alcover_, Dec 07 2015 *)
%t f[n_] := DivisorSum[n, MoebiusMu[#] * 2^(n/#) &] / n; Accumulate[Array[f, 30]] (* _Amiram Eldar_, Aug 24 2023 *)
%o (PARI) a(n)=sum(m=1,n, 1/m* sumdiv(m, d, moebius(d)*2^(m/d) ) ); /* _Joerg Arndt_, Jul 04 2011 */
%Y Partial sums of A001037.
%Y Cf. A014580, A091226, A091231.
%Y Equals A001036 + 1.
%Y Column k=2 of A143328. - _Alois P. Heinz_, Jul 20 2013
%K nonn,easy
%O 1,1
%A Gary L Mullen (mullen(AT)math.psu.edu), Jul 04 2001
%E More terms from _Sascha Kurz_, Mar 25 2002