|
| |
|
|
A002730
|
|
Number of equivalence classes of binary sequences of primitive period n.
(Formerly M0114 N0044)
|
|
4
|
|
|
|
2, 1, 2, 3, 4, 8, 8, 18, 18, 38, 28, 142, 72, 234, 360, 669, 520, 2606, 1608, 7338, 8856, 19370, 16768, 94308, 67556, 216200, 277512, 815310, 662368, 4499852, 2311468, 8465496, 13045076, 31592762, 40937592, 159769394, 103197488, 401912086
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The number of equivalence classes of primitive sequences of period p, taking values in a set with b elements, is given by: N'(p) = sum_{d|p} mobius(p/d)*N(d) where N denotes the number of equivalence classes in the set of all sequences with period p, taking b values (see A002729). - Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
|
|
|
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
|
|
|
|
FORMULA
|
Reference gives formula.
|
|
|
MAPLE
|
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; Nprimitive:=proc(p) options remember: local d: RETURN(add(mobius(p/d)*N(d), d=divisors(p))): end; seq(Nprimitive(p), p=1..51); (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}]; (* b = A002729 *) b[n_] := b[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]) ); b[0] = 1; b[1] = 2; a[n_] := Sum[ MoebiusMu[n/d]*b[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 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
|
| |
|
|
