0,2

Also dimensions of free Lie algebras - see A059966, which is essentially the same sequence.

This sequence also represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1. This number does not depend on q and L is any divisor of q-1. See Theorem 5 and Corollary 3 of the Shallit and Vasiga paper: N=sum(eulerphi(d)/order(d,2)) where d is a divisor of 2^(q-1)-1 such that order(d,2)=L. - Tony Reix (Tony.Reix(AT)laposte.net), Nov 17 2005

Except for a(0) = 1, Bau-Sen Du's [1985/2007] Table 1, p. 6, has this sequence as the 7th (rightmost) column. Other columns of the table include (but are not identified as) A006206-8. - Jonathan Vos Post (jvospost3(AT)gmail.com), Jun 18 2007

"Number of binary Lyndon words" means: number of binary strings inequivalent modulo rotation (cyclic permutation) of the digits and not having a period smaller than n. This provides a link to A103314, since these strings correspond to the inequivalent zero-sum subsets of U_m (m-th roots of unity) obtained by taking the union of U_n (n|m) with 0 or more U_d (n | d, d | m) multiplied by some power of exp(i 2pi/n) to make them mutually disjoint. (But not all zero-sum subsets of U_m are of that form.) - M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Jan 14 2007

Contribution from Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009: (Start)

Also the number of dynamical cycles of period n of a threshold Boolean automata

network which is a quasi-minimal positive circuit of size a multiple of n and which is updated in parallel. (End)

Contribution from Pietro Majer (majer(AT)dm.unipi.it), Sep 22 2009: (Start)

Also, the number of periodic points with (minimal) period n in the iteration

of the tent map f(x):=2min{x,1-x} on the unit interval. (End)

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.

E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie. On the digraph defined by squaring mod m, when m has primitive roots. Congr. Numer. 82 (1991), 167-177.

E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie. On a digraph defined by squaring modulo n. Fibonacci Quart. 30 (1992), 322-333.

R. Church, Tables of irreducible polynomials for the first four prime moduli, Annals Math., 36 (1935), 198-209.

J. Demongeot, M. Noual and S. Sene, On the number of attractors of positive and negative threshold Boolean automata circuits", preprint 2009 [From Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009]

P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam, 1990. See 1.925.

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

M. A. Harrison, On the classification of Boolean functions by the general linear and affine groups, J. Soc. Indust. Appl. Math. 12 (1964) 285-299.

J. C. Lagarias, The set of rational cycles for the 3x+1 problem, Acta Arith. 56 (1990), 33-53.

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983, p. 79.

G. Melancon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

M. R. Nester, (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia.

George Petrides and Johannes Mykkeltveit, On the Classification of Periodic Binary Sequences into Nonlinear Complexity Classes, in Sequences and Their Applications SETA 2006, Lecture Notes in Computer Science, Volume 4086/2006, Springer-Verlag. [From N. J. A. Sloane, Jul 09 2009]

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.

G. Viennot, Algebres de Lie Libres et Monoides Libres, Lecture Notes in Mathematics 691, Springer verlag 1978.

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.

Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem. Bull. Austral. Math. Soc. 31(1985), 89-103. Corrigendum: 32 (1985), 159.

H. Meyn and W. G\"otz, Self-reciprocal polynomials over finite fields

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

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

F. Ruskey, Primitive and Irreducible Polynomials

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

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

Wikipedia, Lyndon word

Index entries for sequences related to Lyndon words

Index entries for "core" sequences

a(n) = (1/n) sum_{ d divides n } mu(n/d) 2^d.

A000031(n) = sum_{ d divides n } A001037(d); 2^n = sum_{ d divides n } d*A001037(d).

Binary strings (Lyndon words): a(0) = 1 = #{ "" }, a(1) = 2 = #{ "0", "1" }, a(2) = 1 = #{ "01" }, a(3) = 2 = #{ "001", "011" }, a(4) = 3 = #{ "0001", "0011", "0111" }, a(5) = 6 = #{ "00001", "00011", "00101", "00111", "01011", "01111" }

with(numtheory): A001037 := proc(n) local a, d; if n = 0 then RETURN(1); else a := 0: for d in divisors(n) do a := a+mobius(n/d)*2^d; od: RETURN(a/n); fi; end;

Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ]/n, {n, 1, 32} ]

(PARI) a(n)=if(n<1, n==0, sumdiv(n, d, moebius(d)*2^(n/d))/n)

See A058943 and A102569 for initial terms. See also A058947, A011260, A059966.

Cf. A000031 (n-bead necklaces but may have period dividing n), A014580, A046211, A046209. Equals A000048+A051841. Also equals A027375(n)/n.

Euler transform is A000079.

Cf. A006206-A006208, A038063, A060477.

Cf. A103314 ; A059966(n)=A060477(n)=A001037(n) for all n>1.

Sequence in context: A097719 A056493 A001371 this_sequence A122086 A082594 A051850

Adjacent sequences: A001034 A001035 A001036 this_sequence A001038 A001039 A001040

nonn,core,easy,nice

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

Replace arXiv URL by non-cached version - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 23 2009