This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A001037 M0116 N0046 N0287 #254 May 16 2025 00:56:51
%S A001037 1,2,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,14532,
%T A001037 27594,52377,99858,190557,364722,698870,1342176,2580795,4971008,
%U A001037 9586395,18512790,35790267,69273666,134215680,260300986,505286415,981706806,1908866960,3714566310,7233615333,14096302710,27487764474
%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_, 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-A006208. - _Jonathan Vos Post_, 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_, Jan 14 2007
%C A001037 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
%C A001037 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
%C A001037 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
%C A001037 From _Jean-Christophe Hervé_, Oct 26 2014: (Start)
%C A001037 For n > 0, a(n) is also the number of orbits of size n of the transform associated to the Kolakoski sequence A000002 (and this is true for any map with 2^n periodic points of period n). The Kolakoski transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the periodic points of the orbit of size 2. A027375(n) = n*a(n) gives the number of periodic points of minimal period n.
%C A001037 For n > 1, this sequence is equal to A059966 and to A060477, and for n = 1, a(1) = A059966(1)+1 = A060477(1)-1; this because the n-th term of all 3 sequences is equal to (1/n)*sum_{d|n} mu(n/d)*(2^d+e), with e = -1/0/1 for resp. A059966/this sequence/A060477, and sum_{d|n} mu(n/d) equals 1 for n = 1 and 0 for all n > 1. (End)
%C A001037 Warning: A000031 and A001037 are easily confused, since they have similar formulas.
%C A001037 From _Petros Hadjicostas_, Jul 14 2020: (Start)
%C A001037 Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.
%C A001037 Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) = A001221(N) being the number of distinct primes of N).
%C A001037 For N = 3, a = phi(3)/2 + omega(3) = 2/2 + 1 = 2 and b = omega(3) - 1 = 0. It follows that D(w, N=3) = A000079(w) = 2^w.
%C A001037 For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.
%C A001037 For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w.
%C A001037 He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)
%C A001037 Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).
%C A001037 For N = 3, we saw that a = 2 and b = 0, and hence d*(w, N=3) = a(w) = Sum_{k | w} (mu(k)/k) * 2^(w/k) / (w/k) = (1/w) * Sum_{k | w} mu(k) * 2^(w/k) for w >= 1. See Table 1 on p. 6 in Kam Cheong Au (2020). (End)
%D A001037 Michael F. Barnsley, Fractals Everywhere, Academic Press, San Diego, 1988, page 171, Lemma 3.
%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 P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam, 1990. See 1.925.
%D A001037 M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983, pp. 65, 79.
%D A001037 Robert M. May, "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - _N. J. A. Sloane_, Mar 17 2019
%D A001037 Guy Melançon, 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. [See A056391 for pdf file of Chap. 2]
%D A001037 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in entries N0046 and N0287).
%D A001037 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001037 Seiichi Manyama, <a href="/A001037/b001037.txt">Table of n, a(n) for n = 0..3333</a> (terms 0..200 from T. D. Noe)
%H A001037 Per Alexandersson and Joakim Uhlin, <a href="https://arxiv.org/abs/1908.00083">Cyclic sieving, skew Macdonald polynomials and Schur positivity</a>, arXiv:1908.00083 [math.CO], 2019.
%H A001037 Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, <a href="https://arxiv.org/abs/2505.06941">When are Hopf algebras determined by integer sequences?</a>, arXiv:2505.06941 [math.CO], 2025. See p. 17.
%H A001037 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.379-383, pp.843-845.
%H A001037 Kam Cheong Au, <a href="https://arxiv.org/abs/2007.03957">Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series</a>, arXiv:2007.03957 [math.NT], 2020. See 3rd line of Table 1 (p. 6).
%H A001037 E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/30-4/blanton.pdf">On a digraph defined by squaring modulo n</a>, Fibonacci Quart. 30 (1992), 322-333.
%H A001037 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H A001037 Émilie Charlier, Manon Philibert, and Manon Stipulanti, <a href="https://arxiv.org/abs/1804.09735">Nyldon words</a>, arXiv:1804.09735 [math.CO], 2018. Also J. Comb. Thy. A, 167 (2019), 60-90.
%H A001037 R. Church, <a href="http://www.jstor.org/stable/1968675">Tables of irreducible polynomials for the first four prime moduli</a>, Annals Math., 36 (1935), 198-209.
%H A001037 J. Demongeot, M. Noual and S. Sene, <a href="http://dx.doi.org/10.1109/WAINA.2010.141">On the number of attractors of positive and negative threshold Boolean automata circuits</a>, 2010 IEEE 24th Intl. Conf. Advan. Inf. Network. Appl. Workshops (WAINA), p 782-789.
%H A001037 Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, <a href="https://arxiv.org/abs/2412.19670">Conjugation, loop and closure invariants of the iterated-integrals signature</a>, arXiv:2412.19670 [math.RA], 2024. See p. 6.
%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>, arXiv:0706.2297 [math.DS], 2007; Bull. Austral. Math. Soc. 31(1985), 89-103. Corrigendum: 32 (1985), 159.
%H A001037 S. V. Duzhin and D. V. Pasechnik, <a href="ftp://pdmi.ras.ru/pub/publicat/znsl/v421/p081.pdf">Groups acting on necklaces and sandpile groups</a>, 2014. See page 85. - _N. J. A. Sloane_, Jun 30 2014
%H A001037 E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%H A001037 M. A. Harrison, <a href="http://www.jstor.org/stable/2946369">On the classification of Boolean functions by the general linear and affine groups</a>, J. Soc. Indust. Appl. Math. 12 (1964) 285-299.
%H A001037 A. Knopfmacher and M. E. Mays, <a href="http://www.emis.de/journals/INTEGERS/papers/b4/b4.Abstract.html">Graph Compositions I: Basic enumeration</a>, Integers 1 (2001), A4, eq. (1).
%H A001037 T. Laarhoven and B de Weger, <a href="http://arxiv.org/abs/1209.3495">The Collatz conjecture and De Bruijn graphs</a>, arXiv preprint arXiv:1209.3495 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 27 2012
%H A001037 J. C. Lagarias, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa56/aa5614.pdf">The set of rational cycles for the 3x+1 problem</a>, Acta Arithmetica, LVI (1990), pp. 33-53.
%H A001037 R. J. Mathar, <a href="http://arxiv.org/abs/0903.2514">Hardy-Littlewood constants embedded into infinite products over all positive integers</a>, sequence gamma_{2,j}^(T), arXiv:0903.2514 [math.NT], 2009-2011.
%H A001037 Ueli M. Maurer, <a href="http://dx.doi.org/10.1016/0166-218X(92)90149-5">Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs</a>, Discrete applied mathematics 37 (1992): 421-436. See Table 1.
%H A001037 Romeo Meštrović, <a href="https://arxiv.org/abs/1804.00992">Different classes of binary necklaces and a combinatorial method for their enumerations</a>, arXiv:1804.00992 [math.CO], 2018.
%H A001037 H. Meyn and W. Götz, <a href="http://www.mat.univie.ac.at/~slc/opapers/s21meyn.html">Self-reciprocal polynomials over finite fields</a>, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
%H A001037 J.-F. Michon and P. Ravache, <a href="https://dx.doi.org/10.1016/j.ffa.2010.01.004">On different families of invariant irreducible polynomials over F_2</a>, Finite fields & Applications 16 (2010) 163-174.
%H A001037 Hans Z. Munthe-Kaas and Jonatan Stava, <a href="https://arxiv.org/abs/2306.15582">Lie Admissible Triple Algebras: The Connection Algebra of Symmetric Spaces</a>, arXiv:2306.15582 [math.DG], 2023.
%H A001037 Mathilde Noual, <a href="http://dx.doi.org/10.1007/978-3-642-28332-1_37">Dynamics of Circuits and Intersecting Circuits</a>, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444, <a href="http://arxiv.org/abs/1011.3930">ArXiv 1011.3930</a> [cs.DM]. - _N. J. A. Sloane_, Jul 07 2012
%H A001037 Cormac O'Sullivan, <a href="https://arxiv.org/abs/2408.14405">Topographs for binary quadratic forms and class numbers</a>, arXiv:2408.14405 [math.NT], 2024. See p. 30.
%H A001037 George Petrides and Johannes Mykkeltveit, <a href="http://dx.doi.org/10.1007/11863854_18">On the Classification of Periodic Binary Sequences into Nonlinear Complexity Classes</a>, 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]
%H A001037 Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
%H A001037 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A001037 F. Ruskey, <a href="https://web.archive.org/web/20161128105338/http://theory.cs.uvic.ca:80/inf/neck/PolyInfo.html">Primitive and Irreducible Polynomials</a>
%H A001037 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A001037 Troy Vasiga and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00158-4">On the iteration of certain quadratic maps over GF(p)</a>, Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.
%H A001037 G. Viennot, <a href="http://dx.doi.org/10.1007/BFb0067950">Algèbres de Lie Libres et Monoïdes Libres</a>, Lecture Notes in Mathematics 691, Springer Verlag 1978.
%H A001037 M. Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/MZV2011IMSc.pdf">Lectures on Multiple Zeta Values</a>, IMSC 2011.
%H A001037 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>
%H A001037 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LyndonWord.html">Lyndon Word</a>
%H A001037 Wikipedia, <a href="http://en.wikipedia.org/wiki/Lyndon_word">Lyndon word</a>
%H A001037 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%H A001037 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A001037 For n >= 1:
%F A001037 a(n) = (1/n)*Sum_{d | n} mu(n/d)*2^d.
%F A001037 A000031(n) = Sum_{d | n} a(d).
%F A001037 2^n = Sum_{d | n} d*a(d).
%F A001037 a(n) = A027375(n)/n.
%F A001037 a(n) = A000048(n) + A051841(n).
%F A001037 For n > 1, a(n) = A059966(n) = A060477(n).
%F A001037 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
%F A001037 From _Richard L. Ollerton_, May 10 2021: (Start)
%F A001037 For n >= 1:
%F A001037 a(n) = (1/n)*Sum_{k=1..n} mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).
%F A001037 a(n) = (1/n)*Sum_{k=1..n} mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)
%F A001037 a(n) ~ 2^n / n. - _Vaclav Kotesovec_, Aug 11 2021
%e A001037 Binary strings (Lyndon words, cf. A102659):
%e A001037 a(0) = 1 = #{ "" },
%e A001037 a(1) = 2 = #{ "0", "1" },
%e A001037 a(2) = 1 = #{ "01" },
%e A001037 a(3) = 2 = #{ "001", "011" },
%e A001037 a(4) = 3 = #{ "0001", "0011", "0111" },
%e A001037 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 f[n_] := Block[{d = Divisors@ n}, Plus @@ (MoebiusMu[n/d]*2^d/n)]; Array[f, 32]
%o A001037 (PARI) A001037(n)=if(n>1,sumdiv(n,d,moebius(d)*2^(n/d))/n,n+1) \\ Edited by _M. F. Hasler_, Jan 11 2016
%o A001037 (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
%o A001037 (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
%o A001037 (Haskell)
%o A001037 a001037 0 = 1
%o A001037 a001037 n = (sum $ map (\d -> (a000079 d) * a008683 (n `div` d)) $
%o A001037 a027750_row n) `div` n
%o A001037 -- _Reinhard Zumkeller_, Feb 01 2013
%o A001037 (Python)
%o A001037 from sympy import divisors, mobius
%o A001037 def a(n): return sum(mobius(d) * 2**(n//d) for d in divisors(n))/n if n>1 else n + 1 # _Indranil Ghosh_, Apr 26 2017
%Y A001037 Column 2 of A074650.
%Y A001037 Row sums of A051168, which gives the number of Lyndon words with fixed number of zeros and ones.
%Y A001037 Euler transform is A000079.
%Y A001037 See A058943 and A102569 for initial terms. See also A058947, A011260, A059966.
%Y A001037 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.
%Y A001037 Cf. A000031 (n-bead necklaces but may have period dividing n), A014580, A046211, A046209, A006206-A006208, A038063, A060477, A103314.
%Y A001037 Cf. A027750, A008683, A254040.
%Y A001037 See also A102659 for the list of binary Lyndon words themselves.
%Y A001037 Cf. A000010, A008683.
%K A001037 nonn,core,easy,nice
%O A001037 0,2
%A A001037 _N. J. A. Sloane_
%E A001037 Revised by _N. J. A. Sloane_, Jun 10 2012