cp's OEIS Frontend

A002729 Number of equivalence classes of binary sequences of period n.

%I A002729 M0538 N0191 #62 Sep 02 2023 15:45:57
%S A002729 1,2,3,4,6,6,13,10,24,22,45,30,158,74,245,368,693,522,2637,1610,7386,
%T A002729 8868,19401,16770,94484,67562,216275,277534,815558,662370,4500267,
%U A002729 2311470,8466189,13045108,31593285,40937606,159772176,103197490,401913697
%N A002729 Number of equivalence classes of binary sequences of period n.
%C A002729 From Pab Ter (pabrlos2(AT)yahoo.com), Jan 24 2006: (Start)
%C A002729 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_{t=0..p-1} Sum_{k=1..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_{u=0..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 (End)
%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_
%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 D. Z. Dokovic, I. Kotsireas, D. Recoskie, J. Sawada, Charm bracelets and their application to the construction of periodic Golay pairs, Discrete Applied Mathematics, Volume 188, 19 June 2015, Pages 32-40.
%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).
%H A002729 Vincenzo Librandi, <a href="/A002729/b002729.txt">Table of n, a(n) for n = 0..50</a>
%H A002729 CombOS - Combinatorial Object Server, <a href="http://combos.org/necklace">Generate necklaces, Lyndon words, chord diagrams, and relatives</a>.
%H A002729 D. Z. Dokovic, I. Kotsireas et al., <a href="http://arxiv.org/abs/1405.7328">Charm bracelets and their application to the construction of periodic Golay pairs</a>, arXiv:1405.7328 [math.CO], 2014.
%H A002729 M. Engelhardt, <a href="http://www.nqueens.de">The N queens problem</a>.
%H A002729 R. C. Titsworth, <a href="http://projecteuclid.org/euclid.ijm/1256059671">Equivalence classes of periodic sequences</a>, Illinois J. Math., 8 (1964), 266-270.
%H A002729 <a href="/index/Ne#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
%p A002729 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)
%t A002729 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}] (* _Jean-François Alcover_, Dec 06 2011, after Maple *)
%Y A002729 Row 2 of A285548.
%Y A002729 Cf. A002730.
%K A002729 nonn,easy,nice
%O A002729 0,2
%A A002729 _N. J. A. Sloane_
%E A002729 More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
%E A002729 Entry revised by _N. J. A. Sloane_ at the suggestion of _Max Alekseyev_, Jun 20 2007