|
| |
|
|
A002729
|
|
Number of equivalence classes of binary sequences of period n.
(Formerly M0538 N0191)
|
|
22
|
|
|
|
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
|
From Pab Ter (pabrlos2(AT)yahoo.com), Jan 24 2006: (Start)
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_{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)).
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)).
(End)
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
|
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.
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).
|
|
|
LINKS
|
|
|
|
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}] (* Jean-François Alcover, Dec 06 2011, after Maple *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
|
|
|
STATUS
|
approved
|
| |
|
|
