0,3

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 (Maximilian.Hasler(AT)gmail.com), May 19 2007

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).

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

Sum_{ d divides n } (phi(2d)*2^(n/d))/(2n).

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;

a[n_] := Fold[ #1 + EulerPhi[2#2]2^(n/#2)/(2n) &, 0, Divisors[n]]

(PARI) A000013(n)=if(n<1, n >= 0, sumdiv(n, k, eulerphi(2*k)*2^(n/k))/(2*n))

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

nonn,nice,easy

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