This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A002729 Number of equivalence classes of binary sequences of period n. (Formerly M0538 N0191) 14
 1, 2, 3, 4, 6, 6, 13, 10, 24, 22, 45, 30, 158, 74, 245, 368, 693, 522, 2637, 1610, 7386, 8868, 19401, 16770, 94484, 67562, 216275, 277534, 815558, 662370, 4500267, 2311470, 8466189, 13045108, 31593285, 40937606, 159772176, 103197490, 401913697 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS 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: 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)) 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))." 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 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. REFERENCES N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270. LINKS M. Engelhardt, The N queens problem FORMULA Reference gives formula. MAPLE 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) MATHEMATICA max = 38; m[k_, n_] := (s = 1; Do[ If[ Mod[s, n] == 0, Return[e], s = s + k^e ] , {e, 1, max}]); c[k_, t_, n_] := Sum[ m[k, n/GCD[n, u*(k-1) + t]]^(-1), {u, 0, n-1}]; a[n_] := (s = 0; Do[ If[ GCD[n, k] == 1 , s = s + 2^c[k, t, n]] , {k, 1, n-1}, {t, 0, n-1}]; s/(n*EulerPhi[n])); a[0] = 1; a[1] = 2; Table[a[n], {n, 0, max}] (* From Jean-François Alcover, Dec 06 2011, after Maple *) CROSSREFS Cf. A002730. Sequence in context: A123131 A000793 A062163 * A030209 A138588 A143102 Adjacent sequences:  A002726 A002727 A002728 * A002730 A002731 A002732 KEYWORD nonn,easy,nice AUTHOR EXTENSIONS More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005 Entry revised by N. J. A. Sloane at the suggestion of Max Alekseyev, Jun 20 2007 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .