%I A000029 M0563 N0202
%S A000029 1,2,3,4,6,8,13,18,30,46,78,126,224,380,687,1224,2250,4112,7685,14310,
%T A000029 27012,50964,96909,184410,352698,675188,1296858,2493726,4806078,
%U A000029 9272780,17920860,34669602,67159050,130216124,252745368,490984488
%N A000029 Number of necklaces with n beads of 2 colors, allowing turning over.
%D A000029 N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 
               285-302.
%D A000029 J. L. Fisher, Application-Oriented Algebra (1977) ISBN 0-7002-2504-8, 
               circa p 215.
%D A000029 Martin Gardner, "New Mathematical Diversions from Scientific American" 
               (Simon and Schuster, New York, 1966), pages 245-246.
%D A000029 E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois 
               J. Math., 5 (1961), 657-665.
%D A000029 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000029 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A000029 N. J. A. Sloane, <a href="b000029.txt">Table of n, a(n) for n = 0..300</
               a>
%H A000029 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A000029 H. Bottomley, <a href="A29.gif">Illustration of initial terms</a>
%H A000029 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 A000029 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/neck/NecklaceInfo.html">
               Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A000029 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 A000029 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               e.html">e</a>
%H A000029 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A000029 <a href="Sindx_Br.html#bracelets">Index entries for sequences related 
               to bracelets</a>
%H A000029 <a href="Sindx_Ne.html#necklaces">Index entries for sequences related 
               to necklaces</a>
%F A000029 Sum_{ d divides n } phi(d)*2^(n/d)/(2*n) + either 2^((n-1)/2) if n odd 
               or 2^(n/2-1)+2^(n/2-2) if n even.
%p A000029 with(numtheory): A000029 := proc(n) local d,s; if n = 0 then RETURN(1); 
               else if n mod 2 = 1 then s := 2^((n-1)/2) else s := 2^(n/2-2)+2^(n/
               2-1); fi; for d in divisors(n) do s := s+phi(d)*2^(n/d)/(2*n); od; 
               RETURN(s); fi; end;
%t A000029 a[0] := 1; a[n_] := Fold[ # 1 + EulerPhi[ # 2]2^(n/ # 2)/(2n) &, If[OddQ[n], 
               2^((n - 1)/2), 2^(n/2 - 1) + 2^(n/2 - 2)], Divisors[n]]
%o A000029 (PARI) a(n)=if(n<1,!n,(n%2+3)/4*2^(n\2)+sumdiv(n,d,eulerphi(n/d)*2^d)/
               2/n)
%Y A000029 Row sums of triangle in A052307.
%Y A000029 Cf. A001371 (primitive necklaces), A000031 (if cannot turn necklace over), 
               A000011, A000013.
%Y A000029 Sequence in context: A068597 A094372 A039880 this_sequence A155051 A018137 
               A084239
%Y A000029 Adjacent sequences: A000026 A000027 A000028 this_sequence A000030 A000031 
               A000032
%K A000029 nonn,easy,nice,core
%O A000029 0,2
%A A000029 N. J. A. Sloane (njas(AT)research.att.com).
%E A000029 More terms from Christian G. Bower (bowerc(AT)usa.net)