The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000048 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is not allowed but the two colors can be interchanged.
(Formerly M0711 N0262)
1, 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, 2048, 3855, 7280, 13797, 26214, 49929, 95325, 182361, 349520, 671088, 1290555, 2485504, 4793490, 9256395, 17895679, 34636833, 67108864, 130150493, 252645135, 490853403, 954437120, 1857283155 (list; graph; refs; listen; history; text; internal format)



Also 2n-bead balanced binary necklaces of fundamental period 2n that are equivalent to their complements.

Also binary Lyndon words of length n with an odd number of 1's (for n>=1).

Also number of binary irreducible polynomials of degree n having trace 1.

Also number of binary irreducible polynomials of degree n having linear coefficient 1 (this is the same as the trace-1 condition, as the reciprocal of an irreducible polynomial is again irreducible).

Also number of binary irreducible self-reciprocal polynomials of degree 2*n; there is no such polynomial for odd degree except for x+1.

Also number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} i*x_i = 1 (mod n+1) = size of Varshamov-Tenengolts code VT_1(n).

Also the number of dynamical cycles of period 2n of a threshold Boolean automata network which is a quasi-minimal negative circuit of size nq where q is odd and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009

Also the number of 3-elements orbits of the symmetric group S3 action on irreducible polynomials of degree 2n, n>1, over GF(2). - Jean Francis Michon, Philippe Ravache (philippe.ravache(AT)univ-rouen.fr), Oct 04 2009

Conjecture: Also the number of caliber-n cycles of Zagier-reduced indefinite binary quadratic forms with sum invariant equal to s, where (s-1)/n is an odd integer. - Barry R. Smith, Dec 14 2014

The Metropolis, Stein, Stein (1973) reference on page 31 Table II lists a(k) for k = 2 to 15 and is actually for sequence A056303 since there a(k) = 0 for k<2. - Michael Somos, Dec 20 2014


B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.

H. Kawakami, Table of rotation sequences of x_{n+1} = x_n^2 - lambda, pp. 73-92 of G. Ikegami, Editor, Dynamical Systems and Nonlinear Oscillations, Vol. 1, World Scientific, 1986.

May, Robert M. "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

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


G. C. Greubel, Table of n, a(n) for n = 0..3320 (terms 0..200 from T. D. Noe)

Joerg Arndt, Matters Computational (The Fxtbook), p.408 and p.848.

L. Carlitz, A theorem of Dickson on irreducible polynomials, Proc. Amer. Math. Soc. 3, (1952). 693-700.

CombOS - Combinatorial Object Server, Generate necklaces, Lyndon words, chord diagrams, and relatives

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

N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.

H. L. Fisher, Letter to N. J. A. Sloane, Mar 16 1989

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

R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. Math. Monthly, 113 (2006), 887-896.

J. E. Iglesias, Enumeration of polytypes MX and MX_2 through the use of the symmetry of the Zhadanov symbol, Acta Cryst. A 62 (3) (2006) 178-194, Table 1.

Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.

A. A. Kulkarni, N. Kiyavash and R. Sreenivas, On the Varshamov-Tenengolts Construction on Binary Strings, 2013.

R. P. Loh, A. G. Shannon, A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, Preprint, 1980.

R. M. May, Simple mathematical models with very complicated dynamics, Nature, 261 (Jun 10, 1976), 459-467.

N. Metropolis, M. L. Stein and P. R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44; reprinted in P. Cvitanovic, ed., Universality in Chaos, Hilger, Bristol, 1986, pp. 187-206.

H. Meyn and W. Götz, Self-reciprocal polynomials over finite fields, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.

Simon Michalowsky, Bahman Gharesifard, Christian Ebenbauer, A Lie bracket approximation approach to distributed optimization over directed graphs, arXiv:1711.05486 [math.OC], 2017.

R. Pries and C. Weir, The Ekedahl-Oort type of Jacobians of Hermitian curves, arXiv preprint arXiv:1302.6261 [math.NT], 2013.

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

N. J. A. Sloane, On single-deletion-correcting codes, arXiv:math/0207197 [math.CO], 2002; in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

N. J. A. Sloane, On single-deletion-correcting codes

B. R. Smith, Reducing quadratic forms by kneading sequences, Journal of Integer Sequences, 17 (2014), article 14.11.8.

P. R. Stein, Letter to N. J. A. Sloane, Jun 02 1971

J.-Y. Thibon, The cycle enumerator of unimodal permutations, arXiv:math/0102051 [math.CO], 2001.

Index entries for "core" sequences

Index entries for sequences related to Lyndon words

Index entries for sequences related to subset sums modulo m


a(n) = (1/(2*n)) * Sum_{odd d divides n} mu(d)*2^(n/d), where mu is the Mobius function A008683.

a(n) = A056303(n) for all integer n>=2. - Michael Somos, Dec 20 2014

Sum_{k dividing m for which m/k is odd} k*a(k) = 2^(m-1). (This explains the observation that the sequence is very close to A006788. Unless m has some nontrivial odd divisors that are small relative to m, the term m*a(m) will dominate the sum. Thus, we see for instance that a(n) = A006788(n) when n has one of the forms 2^m or 2^m*p where p is an odd prime with a(2^m) < p.) - Barry R. Smith, Oct 24 2015

A000013(n) = Sum_{d|n} a(d). - Robert A. Russell, Jun 09 2019

G.f.: 1 + Sum_{k>=1} mu(2*k)*log(1 - 2*x^k)/(2*k). - Ilya Gutkovskiy, Nov 11 2019


a(5) = 3 corresponding to the necklaces 00001, 00111, 01011.

a(6) = 5 from 000001, 000011, 000101, 000111, 001011.


with(numtheory); A000048 := proc(n) local d, t1; if n = 0 then RETURN(1) else t1 := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t1 := t1+mobius(d)*2^(n/d)/(2*n); fi; od; RETURN(t1); fi; end;


a[n_] := Total[ MoebiusMu[#]*2^(n/#)& /@ Select[ Divisors[n], OddQ]]/(2n); a[0] = 1; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jul 21 2011 *)

a[ n_] := If[ n < 1, Boole[n == 0], DivisorSum[ n, MoebiusMu[#] 2^(n/#) &, OddQ] / (2 n)]; (* Michael Somos, Dec 20 2014 *)


(PARI) A000048(n) = sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n) \\ Michael B. Porter, Nov 09 2009

(PARI) L(n, k) = sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d) );

a(n) = sum(k=0, n, if( (n+k)%2==1, L(n, k), 0 ) ) / n;

vector(55, n, a(n)) \\ Joerg Arndt, Jun 28 2012


from sympy import divisors, mobius

def a(n): return 1 if n<1 else sum(mobius(d)*2**(n//d) for d in divisors(n) if d%2)//(2*n) # Indranil Ghosh, Apr 28 2017


Like A000013, but primitive necklaces. Half of A064355.

Equals A042981 + A042982.

Cf. A002823, A000016, A053633, A051841, A001037, A002075, A002076, A008683.

Cf. also A001037, A056303.

Very close to A006788 [Fisher, 1989].

Sequence in context: A114834 A143961 A128023 * A056303 A074099 A006788

Adjacent sequences:  A000045 A000046 A000047 * A000049 A000050 A000051




N. J. A. Sloane


Additional comments from Frank Ruskey, Dec 13 1999



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 4 11:10 EDT 2022. Contains 357239 sequences. (Running on oeis4.)