1,1

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

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.

Index entries for sequences related to Lyndon words

Reference gives formula.

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)

Cf. A002729.

Sequence in context: A050040 A022875 A076480 this_sequence A081664 A117673 A107946

Adjacent sequences: A002727 A002728 A002729 this_sequence A002731 A002732 A002733

nonn,easy,nice

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

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