%I A000013 M0313 N0115
%S A000013 1,1,2,2,4,4,8,10,20,30,56,94,180,316,596,1096,2068,3856,7316,13798,
%T A000013 26272,49940,95420,182362,349716,671092,1290872,2485534,4794088,
%U A000013 9256396,17896832,34636834,67110932,130150588,252648992,490853416
%N A000013 Definition (1): Number of n-bead binary necklaces with beads of 2 colors 
               where the colors may be swapped but turning over is not allowed.
%C A000013 Definition (2): Equivalently, number of different output sequences from 
               an n-stage pure cycling shift register when 2 sequences are considered 
               the same if one is the complement of the other.
%C A000013 Definition (3): Also number of different output sequences from an n-stage 
               pure cycling shift register constrained so contents have even weight.
%C A000013 Definition (4): Also number of output sequences from (n-1)-stage shift 
               register which feeds back the mod 2 sum of the contents of the register.
%C A000013 The equivalence of definitions (1) and (2) follows at once from the definitions.
%C A000013 If u is an output sequence of type (2) then its derivative is of type 
               (3) - so (2) and (3) count the same things.
%C A000013 If we have a shift register of type (4), append a new cell which contains 
               the mod 2 sum of the contents to get a shift register of type (3). 
               So (3) and (4) count the same things.
%C A000013 If n is even, a(n) = A000116(n/2). If 2^(n+1)-1 is prime, then a(n) = 
               A128976(n+1), the number of cycles in the digraph of the Lucas-Lehmer 
               operator LL(x)=x^2-2 acting on Z/(2^(n+1)-1) - M. F. Hasler (Maximilian.Hasler(AT)gmail.com), 
               May 19 2007
%D A000013 N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 
               285-302.
%D A000013 E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois 
               J. Math., 5 (1961), 657-665.
%D A000013 S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, 
               p. 172.
%D A000013 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000013 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 A000013 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A000013 T. D. Noe, <a href="b000013.txt">Table of n, a(n) for n = 0..200</a>
%H A000013 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A000013 H. Bottomley, <a href="A11_A13.gif">Initial terms of A000011 and A000013</
               a>
%H A000013 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/neck/NecklaceInfo.html">
               Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A000013 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/doc/dijen.txt">
               On single-deletion-correcting codes</a>
%H A000013 N. J. A. Sloane, <a href="a000013.txt">Maple code for this and related 
               sequences</a>
%H A000013 <a href="Sindx_Ne.html#necklaces">Index entries for sequences related 
               to necklaces</a>
%F A000013 Sum_{ d divides n } (phi(2d)*2^(n/d))/(2n).
%p A000013 with(numtheory): A000013 := proc(n) local s,d; if n = 0 then RETURN(1) 
               else s := 0; for d in divisors(n) do s := s+(phi(2*d)*2^(n/d))/(2*n); 
               od; RETURN(s); fi; end;
%t A000013 a[n_] := Fold[ #1 + EulerPhi[2#2]2^(n/#2)/(2n) &, 0, Divisors[n]]
%o A000013 (PARI) A000013(n)=if(n<1,n >= 0,sumdiv(n,k,eulerphi(2*k)*2^(n/k))/(2*n))
%Y A000013 Cf. A000031, A000016, A000116.
%Y A000013 Cf. A128976.
%Y A000013 Sequence in context: A120803 A000011 A022476 this_sequence A064484 A063776 
               A118406
%Y A000013 Adjacent sequences: A000010 A000011 A000012 this_sequence A000014 A000015 
               A000016
%K A000013 nonn,nice,easy
%O A000013 0,3
%A A000013 N. J. A. Sloane (njas(AT)research.att.com).