|
| |
|
|
A000013
|
|
Definition (1): Number of n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed.
(Formerly M0313 N0115)
|
|
28
|
|
|
|
1, 1, 2, 2, 4, 4, 8, 10, 20, 30, 56, 94, 180, 316, 596, 1096, 2068, 3856, 7316, 13798, 26272, 49940, 95420, 182362, 349716, 671092, 1290872, 2485534, 4794088, 9256396, 17896832, 34636834, 67110932, 130150588, 252648992, 490853416
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Definition (2): Equivalently, number of different output sequences from an n-stage pure cycling shift register when 2 sequences are considered the same if one is the complement of the other.
Definition (3): Also number of different output sequences from an n-stage pure cycling shift register constrained so contents have even weight.
Definition (4): Also number of output sequences from (n-1)-stage shift register which feeds back the mod 2 sum of the contents of the register.
The equivalence of definitions (1) and (2) follows at once from the definitions.
If u is an output sequence of type (2) then its derivative is of type (3) - so (2) and (3) count the same things.
If we have a shift register of type (4), append a new cell which contains the mod 2 sum of the contents to get a shift register of type (3). So (3) and (4) count the same things.
If n is even, a(n) = A000116(n/2). If 2^(n+1)-1 is prime, then a(n) = A128976(n+1), the number of cycles in the digraph of the Lucas-Lehmer operator LL(x)=x^2-2 acting on Z/(2^(n+1)-1) - M. F. Hasler, May 19 2007
|
|
|
REFERENCES
|
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 172.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt, Fxtbook, p.151, p.408
H. Bottomley, Initial terms of A000011 and A000013
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
N. J. A. Sloane, On single-deletion-correcting codes
N. J. A. Sloane, Maple code for this and related sequences
Index entries for sequences related to necklaces
|
|
|
FORMULA
|
Sum_{ d divides n } (phi(2d)*2^(n/d))/(2n).
|
|
|
MAPLE
|
with(numtheory): A000013 := proc(n) local s, d; if n = 0 then RETURN(1) else s := 0; for d in divisors(n) do s := s+(phi(2*d)*2^(n/d))/(2*n); od; RETURN(s); fi; end;
|
|
|
MATHEMATICA
|
a[n_] := Fold[ #1 + EulerPhi[2#2]2^(n/#2)/(2n) &, 0, Divisors[n]]
|
|
|
PROG
|
(PARI) A000013(n)=if(n<1, n >= 0, sumdiv(n, k, eulerphi(2*k)*2^(n/k))/(2*n))
|
|
|
CROSSREFS
|
Cf. A000031, A000016, A000116.
Cf. A128976.
Sequence in context: A000011 A187213 A022476 * A064484 A063776 A118406
Adjacent sequences: A000010 A000011 A000012 * A000014 A000015 A000016
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
