%I A000031 M0564 N0203
%S A000031 1,2,3,4,6,8,14,20,36,60,108,188,352,632,1182,2192,4116,7712,14602,27596,
%T A000031 52488,99880,190746,364724,699252,1342184,2581428,4971068,9587580,
%U A000031 18512792,35792568,69273668,134219796,260301176,505294128,981706832
%N A000031 Number of n-bead necklaces with 2 colors when turning over is not allowed; 
               also number of output sequences from a simple n-stage cycling shift 
               register; also number of binary irreducible polynomials whose degree 
               divides n.
%C A000031 Also a(n)-1 is number of 1's in truth table for lexicographically least 
               de Bruijn cycle (Fredricksen).
%D A000031 N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 
               285-302.
%D A000031 H. Fredricksen, The lexicographically least de Bruijn cycle, J. Combin. 
               Theory, 9 (1970) 1-5.
%D A000031 E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois 
               J. Math., 5 (1961), 657-665.
%D A000031 S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, 
               pp. 120, 172.
%D A000031 R. M. May, Simple mathematical models with very complicated dynamics, 
               Nature, 261 (Jun 10, 1976), 459-467.
%D A000031 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000031 N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs 
               (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. 
               Publ., 10, de Gruyter, Berlin, 2002.
%D A000031 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000031 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see 
               Problem 7.112(a).
%D A000031 R. C. Titsworth, Equivalence classes of periodic sequences, Illinois 
               J. Math., 8 (1964), 266-270.
%H A000031 T. D. Noe, <a href="b000031.txt">Table of n, a(n) for n = 0..200</a>
%H A000031 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A000031 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               Sequences realized by oligomorphic permutation groups</a>, J. Integ. 
               Seqs. Vol. 3 (2000), #00.1.5.
%H A000031 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
               Publications/books.html">Analytic Combinatorics</a>, 2009; see page 
               18, 64
%H A000031 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=2">
               Encyclopedia of Combinatorial Structures 2</a>
%H A000031 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=130">
               Encyclopedia of Combinatorial Structures 130</a>
%H A000031 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/neck/NecklaceInfo.html">
               Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A000031 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/doc/dijen.txt">
               On single-deletion-correcting codes</a>
%H A000031 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Necklace.html">Link to a section of The World of Mathematics.</a>
%H A000031 Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/
               EulerPhi/31/08/ShowAll.html">Number of necklaces</a>
%H A000031 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A000031 <a href="Sindx_Ne.html#necklaces">Index entries for sequences related 
               to necklaces</a>
%F A000031 a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d).
%e A000031 For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,
               0101,0111,1111}.
%e A000031 The analogous shift register sequences are {000..., 001001..., 011011..., 
               111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 
               111... }.
%p A000031 with(numtheory); A000031 := proc(n) local d,s; if n = 0 then RETURN(1); 
               else s := 0; for d in divisors(n) do s := s+phi(d)*2^(n/d); od; RETURN(s/
               n); fi; end; [ seq(A000031(n), n=0..50) ];
%t A000031 a[n_] := Fold[ # 1 + EulerPhi[ # 2]2^(n/ # 2) &, 0, Divisors[n]]/n
%o A000031 (PARI) {A000031(n)=if(n==0,1,sumdiv(n,d,eulerphi(d)*2^(n/d))/n)}. - Randall 
               L. Rathbun, Jan 11 2002
%Y A000031 Cf. A001037 (primitive solutions to same problem), A014580, A000016, 
               A000013, A000029 (if turning over is allowed), A000011, A001371, 
               A058766.
%Y A000031 Rows sums of triangle in A047996.
%Y A000031 Dividing by 2 gives A053634.
%Y A000031 A008965(n) = a(n) - 1 allowing different offsets.
%Y A000031 Cf. A008965, A053635, A052823.
%Y A000031 Sequence in context: A018137 A084239 A049708 this_sequence A111023 A008324 
               A084074
%Y A000031 Adjacent sequences: A000028 A000029 A000030 this_sequence A000032 A000033 
               A000034
%K A000031 nonn,easy,nice,core
%O A000031 0,2
%A A000031 N. J. A. Sloane (njas(AT)research.att.com).
%E A000031 There is an error in Fig. M3860 in the 1995 Encyclopedia of Integer Sequences: 
               in the third line, the formula for A000031 = M0564 should be (1/n) 
               sum phi(d) 2^(n/d).