%I A002729 M0538 N0191
%S A002729 1,2,3,4,6,6,13,10,24,22,45,30,158,74,245,368,693,522,2637,1610,7386,8868,
%T A002729 19401,16770,94484,67562,216275,277534,815558,662370,4500267,2311470,
%U A002729 8466189,13045108,31593285,40937606,159772176,103197490,401913697
%N A002729 Number of equivalence classes of binary sequences of period n.
%C A002729 Comment from Pab Ter: "The number of equivalence classes of sequences 
               of period p, taking values in a set with b elements, is given by:
%C A002729 N(p) = 1/(p*phi(p)) sum_{0<=t<=p-1} sum_{1<=k<=p-1 & gcd(p,k)=1} b^C(k,
               t) where C(k,t), the number of disjoint cycles of the permutations 
               considered, is C(k,t) = sum_{0<=u<=p-1} 1/M(k,p/gcd(p,u(k-1)+t))
%C A002729 If gcd(k,L)=1, M(k,L) denotes the least positive integer M such that 
               1+k+..+k^(M-1) == 0 (mod L). Also if gcd(k,L)=1 and Ek(L) denotes 
               the exponent of k mod L: M(k,L)=L*Ek(L)/gcd(L,1+k+..+k^(Ek(L)-1))."
%C A002729 Number of two-colored necklaces of length n, where similar necklaces 
               are counted only once. Two necklaces of length n, given by color 
               functions c and d from {0, ..., n-1} to N (set of natural numbers) 
               are considered similar iff there is a factor f, 0 < f < n, satisfying 
               GCD (f,n) = 1, such that, for all k from {0, ..., n-1}, d(f * k mod 
               n) = c(k). I.e. the bead at position k is moved to f * k mod n. In 
               other words: the sequence counts the orbits of the action of the 
               multiplicative group {f | 0 < f < n, GCD (f,n) = 1} on the set of 
               two-colored necklaces where f maps c to d with the formula above. 
               - Matthias Engelhardt (Matthias.R.Engelhardt(AT)web.de)
%C A002729 Counts the same necklaces as A000029 but some of the necklaces viewed 
               as distinct in A000029 are now viewed as equal. In particular, this 
               implies that a(n) <= A000029(n) for every n.
%D A002729 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A002729 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A002729 R. C. Titsworth, Equivalence classes of periodic sequences, Illinois 
               J. Math., 8 (1964), 266-270.
%H A002729 M. Engelhardt, <a href="http://people.freenet.de/nQueens">The N queens 
               problem</a>
%H A002729 <a href="Sindx_Ne.html#necklaces">Index entries for sequences related 
               to necklaces</a>
%F A002729 Reference gives formula.
%p A002729 with(numtheory): M:=proc(k,L) local e,s: s:=1: for e from 1 do if(s mod 
               L = 0) then RETURN(e) else s:=s+k^e fi od: end; C:=proc(k,t,p) local 
               u: RETURN(add(M(k,p/igcd(p,u*(k-1)+t))^(-1),u=0..p-1)) :end; N:=proc(p) 
               options remember: local s,t,k: if(p=1) then RETURN(2) fi: s:=0: for 
               t from 0 to p-1 do for k from 1 to p-1 do if igcd(p,k)=1 then s:=s+2^C(k,
               t,p) fi od od: RETURN(s/(p*phi(p))):end;seq(N(p),p=1..51); # first 
               M expression with(numtheory): E:=proc(k,L) if(L=1) then RETURN(1) 
               else RETURN(order(k,L)) fi end; M:=proc(k,L) local s,EkL: EkL:=E(k,
               L): if(k>1) then s:=(k^EkL-1)/(k-1): RETURN(L*EkL/igcd(L,s)) else 
               RETURN(L*EkL/igcd(L,EkL)) fi end; C:=proc(k,t,p) local u: RETURN(add(M(k,
               p/igcd(p,u*(k-1)+t))^(-1),u=0..p-1)) :end; N:=proc(p) options remember: 
               local s,t,k: if(p=1) then RETURN(2) fi: s:=0: for t from 0 to p-1 
               do for k from 1 to p-1 do if igcd(p,k)=1 then s:=s+2^C(k,t,p) fi 
               od od: RETURN(s/(p*phi(p))):end;seq(N(p),p=1..51);# second M expression 
               (Pab Ter)
%Y A002729 Cf. A002730.
%Y A002729 Sequence in context: A123131 A000793 A062163 this_sequence A030209 A138588 
               A143102
%Y A002729 Adjacent sequences: A002726 A002727 A002728 this_sequence A002730 A002731 
               A002732
%K A002729 nonn,easy,nice
%O A002729 0,2
%A A002729 N. J. A. Sloane (njas(AT)research.att.com).
%E A002729 More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
%E A002729 Entry revised by N. J. A. Sloane (njas(AT)research.att.com) at the suggestion 
               of Max Alekseyev, Jun 20 2007