Logo

Greetings from The On-Line Encyclopedia of Integer Sequences!

Hints

Search: id:A002730
Displaying 1-1 of 1 results found. page 1
     Format: long | short | internal | text      Sort: relevance | references | number      Highlight: on | off
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

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

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.

Sequence in context: A050040 A022875 A076480 this_sequence A081664 A117673 A107946

Adjacent sequences: A002727 A002728 A002729 this_sequence A002731 A002732 A002733

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane (njas(AT)research.att.com).

EXTENSIONS

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

page 1

Search completed in 0.002 seconds

Lookup | Welcome | Find friends | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
More pages | Superseeker | Maintained by N. J. A. Sloane (njas@research.att.com)

Last modified November 25 08:46 EST 2009. Contains 167481 sequences.


AT&T Labs Research