0,2

Also a(n)-1 is number of 1's in truth table for lexicographically least de Bruijn cycle (Fredricksen).

N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.

H. Fredricksen, The lexicographically least de Bruijn cycle, J. Combin. Theory, 9 (1970) 1-5.

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, pp. 120, 172.

R. M. May, Simple mathematical models with very complicated dynamics, Nature, 261 (Jun 10, 1976), 459-467.

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

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).

R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

T. D. Noe, Table of n, a(n) for n = 0..200

Joerg Arndt, Fxtbook

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18, 64

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 2

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 130

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

N. J. A. Sloane, On single-deletion-correcting codes

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Wolfram Research, Number of necklaces

Index entries for "core" sequences

Index entries for sequences related to necklaces

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

For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.

The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111... }.

with(numtheory); A000031 := proc(n) local d, s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+phi(d)*2^(n/d); od; RETURN(s/n); fi; end; [ seq(A000031(n), n=0..50) ];

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

(PARI) {A000031(n)=if(n==0, 1, sumdiv(n, d, eulerphi(d)*2^(n/d))/n)}. - Randall L. Rathbun, Jan 11 2002

Cf. A001037 (primitive solutions to same problem), A014580, A000016, A000013, A000029 (if turning over is allowed), A000011, A001371, A058766.

Rows sums of triangle in A047996.

Dividing by 2 gives A053634.

A008965(n) = a(n) - 1 allowing different offsets.

Cf. A008965, A053635, A052823.

Sequence in context: A018137 A084239 A049708 this_sequence A111023 A008324 A084074

Adjacent sequences: A000028 A000029 A000030 this_sequence A000032 A000033 A000034

nonn,easy,nice,core

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

There is an error in Fig. M3860 in the 1995 Encyclopedia of Integer Sequences: in the third line, the formula for A000031 = M0564 should be (1/n) sum phi(d) 2^(n/d).