login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001037 Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n.
(Formerly M0116 N0046 N0287)
91
1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806, 1908866960, 3714566310, 7233615333, 14096302710, 27487764474 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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-A006208. - Jonathan Vos Post, 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, Jan 14 2007

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. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009

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. - Pietro Majer, Sep 22 2009

Number of distinct cycles of minimal period n in a shift dynamical system associated with a totally disconnected hyperbolic iterated function system (see Barnsley link). - Michel Marcus, Oct 06 2013

Warning: A000031 and A001037 are easily confused, since they have similar formulas.

REFERENCES

Michael F. Barnsley, Fractals Everywhere, Academic Press, San Diego, 1988, page 171 lemma 3.

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.

S. V, Duzhin, D. V. Pasechnik, Groups acting on necklaces and sandpile groups, ftp://pdmi.ras.ru/pub/publicat/znsl/v421/p081.pdf, 2014. See page 85. - N. J. A. Sloane, Jun 30 2014

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, pp. 65, 79.

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

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in entries N0046 and N0287).

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

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

M. Waldschmidt, Lectures on Multiple Zeta Values (IMSC 2011), http://www.math.jussieu.fr/~miw/articles/pdf/MZV2011IMSc.pdf

LINKS

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

Joerg Arndt, Matters Computational (The Fxtbook), pp.379-383, pp.843-845

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

J. Demongeot, M. Noual and S. Sene, On the number of attractors of positive and negative threshold Boolean automata circuits, 2010 IEEE 24th Intl. Conf. Advan. Inf. Network. Appl.  Workshops (WAINA), p 782-789

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.

T. Laarhoven and B de Weger, The Collatz conjecture and De Bruijn graphs, arXiv preprint arXiv:1209.3495, 2012. - From N. J. A. Sloane, Dec 27 2012

R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, sequence gamma_{2,j}^(T).

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

Mathilde Noual, Dynamics of Circuits and Intersecting Circuits, in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444, ArXiv 1011.3930. - N. J. A. Sloane, Jul 07 2012

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, pp 209-222. [From N. J. A. Sloane, Jul 09 2009]

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

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.

Eric Weisstein's World of Mathematics, Irreducible Polynomial

Eric Weisstein's World of Mathematics, Lyndon Word

Wikipedia, Lyndon word

Index entries for sequences related to Lyndon words

Index entries for "core" sequences

FORMULA

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

A000031(n) = sum_{ d divides n } a(d).

2^n = sum_{ d divides n } d*a(d).

a(n) = A027375(n)/n.

a(n) = A000048(n) + A051841(n).

For n>1, a(n) = A059966(n) = A060477(n).

G.f.: 1 - Sum_{n>=1} moebius(n)*log(1 - 2*x^n)/n, where moebius(n)=A008683(n). - Paul D. Hanna, Oct 13 2010

EXAMPLE

Binary strings (Lyndon words, cf. A102659):

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" }.

MAPLE

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;

MATHEMATICA

f[n_] := Block[{d = Divisors@ n}, Plus @@ (MoebiusMu[n/d]*2^d/n)]; Array[f, 32]

PROG

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

(PARI) {a(n)=polcoeff(1-sum(k=1, n, moebius(k)/k*log(1-2*x^k+x*O(x^n))), n)} \\ Paul D. Hanna, Oct 13 2010

(PARI) a(n)=if(n>1, my(s); forstep(i=2^n+1, 2^(n+1), 2, s+=polisirreducible(Mod(1, 2) * Pol(binary(i)))); s, n+1) \\ Charles R Greathouse IV, Jan 26 2012

(Haskell)

a001037 0 = 1

a001037 n = (sum $ map (\d -> (a000079 d) * a008683 (n `div` d)) $

                       a027750_row n) `div` n

-- Reinhard Zumkeller, Feb 01 2013

CROSSREFS

Row sums of A051168, which gives the number of Lyndon words with fixed number of zeros and ones.

Euler transform is A000079.

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

Irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058943, A058944, A058948, A058945, A058946. Primitive irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058947, A058949, A058952, A058950, A058951.

Cf. A000031 (n-bead necklaces but may have period dividing n), A014580, A046211, A046209, A006206-A006208, A038063, A060477, A103314

Cf. A027750, A008683.

See also A102659 for the list of binary Lyndon words themselves.

Sequence in context: A097719 A056493 A001371 * A122086 A082594 A051850

Adjacent sequences:  A001034 A001035 A001036 * A001038 A001039 A001040

KEYWORD

nonn,core,easy,nice,changed

AUTHOR

N. J. A. Sloane. Entry revised by N. J. A. Sloane, Jun 10 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 1 09:29 EDT 2014. Contains 246289 sequences.