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

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.

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.

Dividing by 2 gives A053634.

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

Cf. A008965, A053635, A052823.

Adjacent sequences: A000028 A000029 A000030 this_sequence A000032 A000033 A000034

Sequence in context: A018137 A084239 A049708 this_sequence A111023 A008324 A084074

nonn,easy,nice,core

njas

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