A002729 - OEIS

%I M0538 N0191 #62 Sep 02 2023 15:45:57

%S 1,2,3,4,6,6,13,10,24,22,45,30,158,74,245,368,693,522,2637,1610,7386,

%T 8868,19401,16770,94484,67562,216275,277534,815558,662370,4500267,

%U 2311470,8466189,13045108,31593285,40937606,159772176,103197490,401913697

%N Number of equivalence classes of binary sequences of period n.

%C From Pab Ter (pabrlos2(AT)yahoo.com), Jan 24 2006: (Start)

%C The number of equivalence classes of sequences of period p, taking values in a set with b elements, is given by:

%C 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 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 (End)

%C 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 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 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A002729/b002729.txt">Table of n, a(n) for n = 0..50</a>

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/necklace">Generate necklaces, Lyndon words, chord diagrams, and relatives</a>.

%H 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 M. Engelhardt, <a href="http://www.nqueens.de">The N queens problem</a>.

%H 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 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F Reference gives formula.

%p 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 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 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 Row 2 of A285548.

%Y Cf. A002730.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_

%E More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005

%E Entry revised by _N. J. A. Sloane_ at the suggestion of _Max Alekseyev_, Jun 20 2007