%I A001037 M0116 N0046
%S A001037 1,2,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,14532,27594,
%T A001037 52377,99858,190557,364722,698870,1342176,2580795,4971008,9586395,
%U A001037 18512790,35790267,69273666,134215680,260300986,505286415,981706806
%N 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.
%C A001037 Also dimensions of free Lie algebras - see A059966, which is essentially
the same sequence.
%C A001037 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
%C A001037 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
%C A001037 "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
%C A001037 Contribution from Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb
25 2009: (Start)
%C A001037 Also the number of dynamical cycles of period n of a threshold Boolean
automata
%C A001037 network which is a quasi-minimal positive circuit of size a multiple
of n and which is updated in parallel. (End)
%C A001037 Contribution from Pietro Majer (majer(AT)dm.unipi.it), Sep 22 2009: (Start)
%C A001037 Also, the number of periodic points with (minimal) period n in the iteration
%C A001037 of the tent map f(x):=2min{x,1-x} on the unit interval. (End)
%D A001037 E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
%D A001037 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.
%D A001037 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.
%D A001037 R. Church, Tables of irreducible polynomials for the first four prime
moduli, Annals Math., 36 (1935), 198-209.
%D A001037 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]
%D A001037 P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam,
1990. See 1.925.
%D A001037 E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois
J. Math., 5 (1961), 657-665.
%D A001037 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.
%D A001037 J. C. Lagarias, The set of rational cycles for the 3x+1 problem, Acta
Arith. 56 (1990), 33-53.
%D A001037 M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983,
p. 79.
%D A001037 G. Melancon, Factorizing infinite words using Maple, MapleTech journal,
vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
%D A001037 M. R. Nester, (1999). Mathematical investigations of some plant interaction
designs. PhD Thesis. University of Queensland, Brisbane, Australia.
%D A001037 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]
%D A001037 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A001037 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A001037 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.
%D A001037 G. Viennot, Algebres de Lie Libres et Monoides Libres, Lecture Notes
in Mathematics 691, Springer verlag 1978.
%H A001037 T. D. Noe, <a href="b001037.txt">Table of n, a(n) for n = 0..200</a>
%H A001037 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A001037 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
Sequences realized by oligomorphic permutation groups</a>, J. Integ.
Seqs. Vol. 3 (2000), #00.1.5.
%H A001037 Bau-Sen Du, <a href="http://arXiv.org/abs/0706.2297">The Minimal Number
of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem</
a>. Bull. Austral. Math. Soc. 31(1985), 89-103. Corrigendum: 32 (1985),
159.
%H A001037 H. Meyn and W. G\"otz, <a href="http://www.mat.univie.ac.at/~slc/opapers/
s21meyn.html">Self-reciprocal polynomials over finite fields</a>
%H A001037 Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/
index.html">Arithmetic and growth of periodic orbits</a>, J. Integer
Seqs., Vol. 4 (2001), #01.2.1.
%H A001037 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/neck/NecklaceInfo.html">
Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A001037 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/neck/PolyInfo.html">
Primitive and Irreducible Polynomials</a>
%H A001037 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
IrreduciblePolynomial.html">Link to a section of The World of Mathematics.</
a>
%H A001037 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
LyndonWord.html">Link to a section of The World of Mathematics.</
a>
%H A001037 Wikipedia, <a href="http://en.wikipedia.org/wiki/Lyndon_word">Lyndon
word</a>
%H A001037 <a href="Sindx_Lu.html#Lyndon">Index entries for sequences related to
Lyndon words</a>
%H A001037 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%F A001037 a(n) = (1/n) sum_{ d divides n } mu(n/d) 2^d.
%F A001037 A000031(n) = sum_{ d divides n } A001037(d); 2^n = sum_{ d divides n
} d*A001037(d).
%e A001037 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" }
%p A001037 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;
%t A001037 Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ]/n, {n,
1, 32} ]
%o A001037 (PARI) a(n)=if(n<1,n==0,sumdiv(n,d,moebius(d)*2^(n/d))/n)
%Y A001037 See A058943 and A102569 for initial terms. See also A058947, A011260,
A059966.
%Y A001037 Cf. A000031 (n-bead necklaces but may have period dividing n), A014580,
A046211, A046209. Equals A000048+A051841. Also equals A027375(n)/
n.
%Y A001037 Euler transform is A000079.
%Y A001037 Cf. A006206-A006208, A038063, A060477.
%Y A001037 Cf. A103314 ; A059966(n)=A060477(n)=A001037(n) for all n>1.
%Y A001037 Sequence in context: A097719 A056493 A001371 this_sequence A122086 A082594
A051850
%Y A001037 Adjacent sequences: A001034 A001035 A001036 this_sequence A001038 A001039
A001040
%K A001037 nonn,core,easy,nice
%O A001037 0,2
%A A001037 N. J. A. Sloane (njas(AT)research.att.com).
%E A001037 Replace arXiv URL by non-cached version - R. J. Mathar (mathar(AT)strw.leidenuniv.nl),
Oct 23 2009
|
