A046211 -id:A046211 - cp's OEIS frontend

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.

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

Offset: 0

N. J. A. Sloane

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, 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
From Jean-Christophe Hervé, Oct 26 2014: (Start)
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.
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)
Warning: A000031 and A001037 are easily confused, since they have similar formulas.
From Petros Hadjicostas, Jul 14 2020: (Start)
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.
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).
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.
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.
For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w.
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.)
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)).
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)

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

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.
P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam, 1990. See 1.925.
M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983, pp. 65, 79.
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
Guy Melançon, 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. [See A056391 for pdf file of Chap. 2]
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).

Seiichi Manyama, Table of n, a(n) for n = 0..3333 (terms 0..200 from T. D. Noe)
Per Alexandersson and Joakim Uhlin, Cyclic sieving, skew Macdonald polynomials and Schur positivity, arXiv:1908.00083 [math.CO], 2019.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 17.
Joerg Arndt, Matters Computational (The Fxtbook), pp.379-383, pp.843-845.
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See 3rd line of Table 1 (p. 6).
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.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Émilie Charlier, Manon Philibert, and Manon Stipulanti, Nyldon words, arXiv:1804.09735 [math.CO], 2018. Also J. Comb. Thy. A, 167 (2019), 60-90.
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, 2010 IEEE 24th Intl. Conf. Advan. Inf. Network. Appl. Workshops (WAINA), p 782-789.
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See p. 6.
Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem, arXiv:0706.2297 [math.DS], 2007; Bull. Austral. Math. Soc. 31(1985), 89-103. Corrigendum: 32 (1985), 159.
S. V. Duzhin and D. V. Pasechnik, Groups acting on necklaces and sandpile groups, 2014. See page 85. - _N. J. A. Sloane_, Jun 30 2014
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.
A. Knopfmacher and M. E. Mays, Graph Compositions I: Basic enumeration, Integers 1 (2001), A4, eq. (1).
T. Laarhoven and B de Weger, The Collatz conjecture and De Bruijn graphs, arXiv preprint arXiv:1209.3495 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 27 2012
J. C. Lagarias, The set of rational cycles for the 3x+1 problem, Acta Arithmetica, LVI (1990), pp. 33-53.
Piotr Laskawiec, Joint Spectral Radius with focus on pairs of 2 X 2 matrices, Ph. D. Dissertation, Penn. State Univ. (2025). See p. 55.
R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, sequence gamma_{2,j}^(T), arXiv:0903.2514 [math.NT], 2009-2011.
Ueli M. Maurer, Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs, Discrete applied mathematics 37 (1992): 421-436. See Table 1.
Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.
H. Meyn and W. Götz, Self-reciprocal polynomials over finite fields, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
J.-F. Michon and P. Ravache, On different families of invariant irreducible polynomials over F_2, Finite fields & Applications 16 (2010) 163-174.
Hans Z. Munthe-Kaas and Jonatan Stava, Lie Admissible Triple Algebras: The Connection Algebra of Symmetric Spaces, arXiv:2306.15582 [math.DG], 2023.
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 [cs.DM]. - _N. J. A. Sloane_, Jul 07 2012
Cormac O'Sullivan, Topographs for binary quadratic forms and class numbers, arXiv:2408.14405 [math.NT], 2024. See p. 30.
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
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
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, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
M. Waldschmidt, Lectures on Multiple Zeta Values, IMSC 2011.
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

Column 2 of A074650.
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, A254040.
See also A102659 for the list of binary Lyndon words themselves.
Cf. A000010, A008683.

a001037 0 = 1
a001037 n = (sum $ map (\d -> (a000079 d) * a008683 (n `div` d)) $
                       a027750_row n) `div` n
-- Reinhard Zumkeller, Feb 01 2013

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;

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

A001037(n)=if(n>1,sumdiv(n,d,moebius(d)*2^(n/d))/n,n+1) \\ Edited by M. F. Hasler, Jan 11 2016

{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

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

from sympy import divisors, mobius
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

For n >= 1:
a(n) = (1/n)*Sum_{d | n} mu(n/d)*2^d.
A000031(n) = Sum_{d | n} a(d).
2^n = Sum_{d | 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
From Richard L. Ollerton, May 10 2021: (Start)
For n >= 1:
a(n) = (1/n)*Sum_{k=1..n} mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)
a(n) ~ 2^n / n. - Vaclav Kotesovec, Aug 11 2021

Revised by N. J. A. Sloane, Jun 10 2012

A027376 Number of ternary irreducible monic polynomials of degree n; dimensions of free Lie algebras.

Original entry on oeis.org

1, 3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880, 16104, 44220, 122640, 341484, 956576, 2690010, 7596480, 21522228, 61171656, 174336264, 498111952, 1426403748, 4093181688, 11767874940, 33891544368, 97764009000, 282429535752, 817028131140, 2366564736720, 6863037256208, 19924948267224, 57906879556410

Offset: 0

N. J. A. Sloane

Number of Lyndon words of length n on {1,2,3}. A Lyndon word is primitive (not a power of another word) and is earlier in lexicographic order than any of its cyclic shifts. - John W. Layman, Jan 24 2006
Exponents in an expansion of the Hardy-Littlewood constant Product(1 - (3*p - 1)/(p - 1)^3, p prime >= 5), whose decimal expansion is in A065418: the constant equals Product_{n >= 2} (zeta(n)*(1 - 2^(-n))*(1 - 3^(-n)))^(-a(n)). - Michael Somos, Apr 05 2003
Number of aperiodic necklaces with n beads of 3 colors. - Herbert Kociemba, Nov 25 2016
Number of irreducible harmonic polylogarithms, see page 299 of Gehrmann and Remiddi reference and table 1 of Maître article. - F. Chapoton, Aug 09 2021
For n>=2, a(n) is the number of Hesse loops of length 2*n, see Theorem 22 of Dutta, Halbeisen, Hungerbühler link. - Sayan Dutta, Sep 22 2023
For n>=2, a(n) is the number of orbits of size n of isomorphism classes of elliptic curves under the Hesse derivative, see Theorem 2 of Kettinger link. - Jake Kettinger, Aug 07 2024

			For n = 2 the a(2)=3 polynomials are  x^2+1, x^2+x+2, x^2+2*x+2. - _Robert Israel_, Dec 16 2015

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Seiichi Manyama, Table of n, a(n) for n = 0..2102 (terms 0..200 from T. D. Noe)
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See 4th line of Table 1 (p. 6).
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See p. 6.
Sayan Dutta, Lorenz Halbeisen, and Norbert Hungerbühler, Properties of Hesse derivatives of cubic curves, arXiv:2309.05048 [math.AG], 2023.
T. Gehrmann and E. Remiddi, Numerical evaluation of harmonic polylogarithms. Comput. Phys. Comm. 141 (2001), no. 2, 296-312.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016. See Table A.2.
Jake Kettinger, The dynamics of the Hesse derivative on the j-invariant, arXiv:2408.04117 [math.AG], 2024.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
D. Maître, HPL, a Mathematica implementation of the harmonic polylogarithms, Computer Physics Communications, Volume 174, Issue 3, 1 February 2006, Pages 222-240.
G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag, 1978.
Index entries for sequences related to Lyndon words

Column 3 of A074650.

Cf. A000031, A001037, A001693, A001867, A027375, A027377, A054718, A102660.

with(numtheory): A027376 := n -> `if`(n = 0, 1,
add(mobius(d)*3^(n/d), d = divisors(n))/n):
seq(A027376(n), n = 0..32);

a[0]=1; a[n_] := Module[{ds=Divisors[n], i}, Sum[MoebiusMu[ds[[i]]]3^(n/ds[[i]]), {i, 1, Length[ds]}]/n]
a[0]=1; a[n_] := DivisorSum[n, MoebiusMu[n/#]*3^#&]/n; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Dec 01 2015 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,3],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

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

a(n) = (1/n)*Sum_{d|n} mu(d)*3^(n/d).
(1 - 3*x) = Product_{n>0} (1 - x^n)^a(n).
G.f.: k = 3, 1 - Sum_{i >= 1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016
a(n) ~ 3^n / n. - Vaclav Kotesovec, Jul 01 2018
a(n) = 2*A046211(n) + A046209(n). - R. J. Mathar, Oct 21 2021

A054660 Number of monic irreducible polynomials over GF(4) of degree n with fixed nonzero trace.

Original entry on oeis.org

1, 2, 5, 16, 51, 170, 585, 2048, 7280, 26214, 95325, 349520, 1290555, 4793490, 17895679, 67108864, 252645135, 954437120, 3616814565, 13743895344, 52357696365, 199911205050, 764877654105, 2932031006720, 11258999068416

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of Lyndon words of length n with trace 1 over GF(4).
Let x = RootOf( z^2+z+1 ) and y = 1+x. Also number of Lyndon words of length n with trace x over GF(4). Also number of Lyndon words of length n with trace y over GF(4).
Also number of 4-ary Lyndon words (i.e., Lyndon words over Z_4) of length n with trace 1 (mod 4). Also the same with trace 3 (mod 4). - Andrey Zabolotskiy, Dec 19 2020

			a(3; y)=5 since the five Lyndon words over GF(4) of trace y and length 3 are { 00y, 01x, 0x1, 11y, xxy }; the five Lyndon words over Z_4 of trace 1 (mod 4) and length 3 are { 001, 023, 032, 113, 122 }.

Seiichi Manyama, Table of n, a(n) for n = 1..1000
F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
F. Ruskey, Number of q-ary Lyndon words with given trace mod q
F. Ruskey, Number of Lyndon words over GF(q) with given trace

Cf. A000048, A051841, A046211, A046209, A054661, etc.
Cf. A008683, A054661, A027377, A300628, A074033, A074034, A074035, A074448, A074449, A074450.
Cf. A074406, A074407, A074408, A074409.

From Seiichi Manyama, Mar 11 2018: (Start)
a(n) = A000048(2*n) = (1/(4*n)) * Sum_{odd d divides n} mu(d)*4^(n/d), where mu is the Möbius function A008683.
a(n+1) = A300628(n,n) for n >= 0. (End)
From Andrey Zabolotskiy, Dec 19 2020: (Start)
a(n) = A074033(n) + A074034(n) + 2 * A074035(n).
a(n) = A074448(n) + A074449(n) + 2 * A074450(n).
a(n) = A074406(n) + A074407(n) + A074408(n) + A074409(n). (End)

More terms from James Sellers, Apr 19 2000

A046209 Number of ternary Lyndon words whose digits sum to 0 mod 3; also number of trace 0 irreducible polynomials over GF(3).

Original entry on oeis.org

1, 1, 2, 6, 16, 38, 104, 270, 726, 1960, 5368, 14736, 40880, 113828, 318848, 896670, 2532160, 7174050, 20390552, 58112088, 166037248, 475467916, 1364393896, 3922624800, 11297181456, 32588003000, 94143178098, 272342710380, 788854912240, 2287679084096, 6641649422408, 19302293185470

Offset: 1

Frank Ruskey, Dec 13 1999

nonn

Also number of ternary Lyndon words of trace 0 over GF(3).

			a(4) = 6 = |{ 0012, 0021, 0111, 0102, 0222, 1122 }|.

G. C. Greubel, Table of n, a(n) for n = 1..2000
F. Ruskey, Number of q-ary Lyndon words with given trace mod q
F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
F. Ruskey, Number of Lyndon words over GF(q) with given trace
Index entries for sequences related to Lyndon words

Cf. A046211.

a[n_] := 1/(3n) DivisorSum[n, GCD[#, 3]*MoebiusMu[#]*3^(n/#)&]; Array[a, 32] (* Jean-François Alcover, Dec 06 2015, adapted from PARI *)

a(n) = 1/(3*n) * sumdiv(n, d, gcd(d, 3)*moebius(d)*3^(n/d) ); /* Joerg Arndt, Aug 17 2012 */

a(n) = 1/(3*n) * sum(d divides n, gcd(d, 3)*mu(d)*3^(n/d) ).

a(n) = A053548(n) + A053560(n) + A053561(n). - R. J. Mathar, Oct 21 2021

A054661 Number of monic irreducible polynomials over GF(4) with zero trace.

Original entry on oeis.org

1, 0, 5, 12, 51, 160, 585, 2016, 7280, 26112, 95325, 349180, 1290555, 4792320, 17895679, 67104768, 252645135, 954422560, 3616814565, 13743842916, 52357696365, 199911014400, 764877654105, 2932030307680, 11258999068416

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of Lyndon words of length n with trace 0 over GF(4).

F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
F. Ruskey, Number of Lyndon words over GF(q) with given trace

Cf. A000048, A051841, A046211, A046209, A054660, A074031, A074032, A074446, A074447.

From Andrey Zabolotskiy, Dec 17 2020: (Start)
a(n) = A074031(n) + 3 * A074032(n).
a(n) = A074446(n) + 3 * A074447(n). (End)

More terms from James Sellers, Apr 19 2000

A054662 Number of monic irreducible polynomials over GF(5) with fixed nonzero trace.

Original entry on oeis.org

1, 2, 8, 30, 125, 516, 2232, 9750, 43400, 195250, 887784, 4068740, 18780048, 87191964, 406901000, 1907343750, 8975758272, 42385503300, 200773540296, 953674218750, 4541306267856, 21674415838068, 103660251783288

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of 5-ary Lyndon words with trace 1 mod 5; trace 2 mod 5; trace 3 mod 5; trace 4 mod 5; also number of 5-ary Lyndon words of trace 1 over GF(5), trace 2 over GF(5); trace 3 over GF(5); trace 4 over GF(5).

Frank Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
Frank Ruskey, Number of q-ary Lyndon words with given trace mod q
Frank Ruskey, Number of Lyndon words over GF(q) with given trace

Column 5 of A110540.

Cf. A000048, A051841, A046211, A046209, A054661, etc.

a(n) = sumdiv(n, d, (gcd(d, 5)==1)*(moebius(d)*5^(n/d)))/(5*n); \\ Seiichi Manyama, May 29 2024

a(n) = 1/(5*n) * Sum_{d|n, gcd(d,5)=1} mu(d) * 5^(n/d). - Seiichi Manyama, May 29 2024

More terms from James Sellers, Apr 19 2000

A146211 Fermat quotient of the n-th prime with base 3.

Original entry on oeis.org

16, 104, 5368, 40880, 2532160, 20390552, 1364393896, 788854912240, 6641649422408, 4056611764783760, 296528425830656800, 2544627654221217656, 188573151481968108424, 121907205457107043376080

Offset: 3

R. J. Mathar, Oct 28 2008

Takashi Agoh and Ladislav Skula, The fourth power of the Fermat quotient, J. Numb. Theory 128 (2008) 2865-2873.

Subsequence of A046211. Cf. A007663.

A146211:= n-> map (p-> (3^(p-1)-1)/p, ithprime(n)):
seq (A146211(n), n=3..16); # Jani Melik, Jan 24 2010

Table[(3^(p - 1) - 1)/p, {p, Prime[Range[3, 16]]}] (* Amiram Eldar, Oct 13 2023 *)

a(n) = my(p=prime(n)); (3^(p-1)-1)/p; \\ Michel Marcus, Oct 13 2023

a(n) = (3^(p-1)-1)/p, where p=A000040(n).

a(n) = A046211(A000040(n)), for n >= 3. - Amiram Eldar, Oct 13 2023

A110540 Invertible triangle: T(n,k) = number of k-ary Lyndon words of length n-k+1 with trace 1 modulo k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 3, 2, 1, 0, 3, 6, 5, 2, 1, 0, 5, 16, 16, 8, 3, 1, 0, 9, 39, 51, 30, 12, 3, 1, 0, 16, 104, 170, 125, 54, 16, 4, 1, 0, 28, 270, 585, 516, 259, 84, 21, 4, 1, 0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1, 0, 93, 1960, 7280, 9750, 6665, 2792, 819, 180, 33, 5, 1

Offset: 1

Paul Barry, Jul 25 2005

An invertible number triangle related to Lyndon words of trace 1.

			Rows begin
  1;
  0,  1;
  0,  1,   1;
  0,  1,   1,    1;
  0,  2,   3,    2,    1;
  0,  3,   6,    5,    2,    1;
  0,  5,  16,   16,    8,    3,   1;
  0,  9,  39,   51,   30,   12,   3,   1;
  0, 16, 104,  170,  125,   54,  16,   4,  1;
  0, 28, 270,  585,  516,  259,  84,  21,  4, 1;
  0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Frank Ruskey, Number of q-ary Lyndon words with given trace mod q
Frank Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
Frank Ruskey, Number of Lyndon words over GF(q) with given trace

Columns include A000048, A046211, A054660, A054662, A054666, A373277, A300674, A300675.

T[n_, k_]:=Sum[Boole[GCD[d, k] == 1]  MoebiusMu[d] k^((n - k + 1)/d), {d, Divisors[n - k + 1]}] /(k(n - k + 1)); Flatten[Table[T[n, k], {n, 12}, {k, n}]] (* Indranil Ghosh, Mar 27 2017 *)

for(n=1, 11, for(k=1, n, print1( sum(d=1,n-k+1, if(Mod(n-k+1, d)==0 && gcd(d, k)==1, moebius(d)*k^((n-k+1)/d), 0)/(k*(n-k+1)) ),", ");); print();) \\ Andrew Howroyd, Mar 26 2017

T(n, k) = (Sum_{d | n-k+1, gcd(d, k)=1} mu(d)*k^((n-k+1)/d))/(k*(n-k+1)).

Name clarified by Andrew Howroyd, Mar 26 2017

A271929 G.f. A(x) satisfies: A(x)^3 = A(x^3) / (1 - 3*x).

Original entry on oeis.org

1, 1, 2, 5, 12, 31, 83, 224, 615, 1708, 4777, 13455, 38110, 108428, 309714, 887666, 2551575, 7353423, 21240460, 61478489, 178269670, 517784717, 1506162369, 4387201004, 12795170784, 37359689295, 109199349181, 319493390481, 935616592227, 2742209152877, 8043500169958, 23610710680582, 69354125493930, 203852682699869, 599549063015417, 1764338532368820

Offset: 1

Paul D. Hanna, Apr 17 2016

nonn

Compare g.f. to: G(x)^2 = G(x^2)/(1 - 2*x) where G(x) is the g.f. of A123916, the EULER transform of A000048.

			G.f.: A(x) = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 31*x^6 + 83*x^7 + 224*x^8 + 615*x^9 + 1708*x^10 + 4777*x^11 + 13455*x^12 +...
where A(x)^3 = A(x^3) / (1 - 3*x).
Also, when expressed as the EULER transform of A046211,
A(x) = x/( (1-x) * (1-x^2) * (1-x^3)^3 * (1-x^4)^6 * (1-x^5)^16 * (1-x^6)^39 * (1-x^7)^104 * (1-x^8)^270 * (1-x^9)^729 *...* (1-x^n)^A046211(n) *...).
RELATED SERIES.
A(x)^3 = x^3 + 3*x^4 + 9*x^5 + 28*x^6 + 84*x^7 + 252*x^8 + 758*x^9 + 2274*x^10 + 6822*x^11 + 20471*x^12 + 61413*x^13 + 184239*x^14 +...

Vaclav Kotesovec, Table of n, a(n) for n = 1..400

Cf. A123916.

{a(n) = my(A=x); for(i=1, n, A = ( subst(A, x, x^3)/(1 - 3*x +x*O(x^n)))^(1/3)); polcoeff(G=A, n)}
for(n=1, 50, print1(a(n), ", "))

The EULER transform of A046211, where A046211(n) is the number of ternary Lyndon words whose digits sum to 1 (or 2) mod 3.

a(n) ~ c * 3^n / n^(2/3), where c = 0.1260671867244258410294918... . - Vaclav Kotesovec, Apr 18 2016

A373279 Expansion of Sum_{k>=0} x^(3^k) / (1 - 3*x^(3^k)).

Original entry on oeis.org

1, 3, 10, 27, 81, 246, 729, 2187, 6571, 19683, 59049, 177174, 531441, 1594323, 4783050, 14348907, 43046721, 129140409, 387420489, 1162261467, 3486785130, 10460353203, 31381059609, 94143181014, 282429536481, 847288609443, 2541865834900, 7625597484987

Offset: 1

Seiichi Manyama, May 30 2024

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1000

Cf. A187767, A373280, A373281, A373282, A373283.

Cf. A000244, A046211, A051064, A364222.

b(n, k) = sumdiv(n, d, (gcd(d, k)==1)*(moebius(d)*k^(n/d)))/(k*n);
a(n, k=3) = sumdiv(n, d, d*b(d, k));

G.f. A(x) satisfies A(x) = x/(1 - 3*x) + A(x^3).
If n == 0 (mod 3), a(n) = 3^n + a(n/3) otherwise a(n) = 3^n.
a(n) = Sum_{d|n} d * A046211(d).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A027376 Number of ternary irreducible monic polynomials of degree n; dimensions of free Lie algebras.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A054660 Number of monic irreducible polynomials over GF(4) of degree n with fixed nonzero trace.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A046209 Number of ternary Lyndon words whose digits sum to 0 mod 3; also number of trace 0 irreducible polynomials over GF(3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054661 Number of monic irreducible polynomials over GF(4) with zero trace.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A054662 Number of monic irreducible polynomials over GF(5) with fixed nonzero trace.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A146211 Fermat quotient of the n-th prime with base 3.

Views

Author

Keywords