A002730 Number of equivalence classes of binary sequences of primitive period n. (Formerly M0114 N0044)

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

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

Vincenzo Librandi, Table of n, a(n) for n = 1..50

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)

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

Cf. A002729.

Sequence in context: A350404 A325841 A076480 * A081664 A224926 A117673

Adjacent sequences: A002727 A002728 A002729 * A002731 A002732 A002733

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved