|
Search: id:A000013
|
|
|
| A000013 |
|
(1) Number of n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed. 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.
(Formerly M0313 N0115)
|
|
+0
27
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
(2) Also number of different output sequences from an n-stage pure cycling shift register constrained so contents have even weight.
(3) Also number of output sequences from (n-1)-stage shift register which feeds back the mod 2 sum of the contents of the register.
If u is an output sequence of type (1) then its derivative is of type (2) - so (1) and (2) count the same things.
If we have a shift register of type (3), append a new cell which contains the mod sum of the contents to get a shift register of type (2) - (2) and (3) 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 (Maximilian.Hasler(AT)gmail.com), 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, 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.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt, Fxtbook
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]]
|
|
PROGRAM
|
(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: A120803 A000011 A022476 this_sequence A064484 A063776 A118406
Adjacent sequences: A000010 A000011 A000012 this_sequence A000014 A000015 A000016
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
njas
|
|
|
Search completed in 0.002 seconds
|
