|
Search: id:A002730
|
|
|
| A002730 |
|
Number of equivalence classes of binary sequences of primitive period n.
(Formerly M0114 N0044)
|
|
+0
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; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
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
|
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
|
|
LINKS
|
Index entries for sequences related to Lyndon words
|
|
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)
|
|
CROSSREFS
|
Cf. A002729.
Adjacent sequences: A002727 A002728 A002729 this_sequence A002731 A002732 A002733
Sequence in context: A050040 A022875 A076480 this_sequence A081664 A117673 A107946
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
|
|
|
Search completed in 0.002 seconds
|
