A001371 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is allowed.

1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 4110, 7630, 14308, 26931, 50944, 96782, 184408, 352450, 675180, 1296477, 2493680, 4805388, 9272778, 17919558, 34669600, 67156800, 130215996, 252741255, 490984464, 954629662, 1857545298

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• changed

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence, in two entries, N0045 and N0285).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 0..400
• Jairo Bochi and Piotr Laskawiec, Spectrum maximizing products are not generically unique, arXiv:2301.12574 [math.OC], 2023.
• Edgar N. Gilbert and John Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• Piotr Laskawiec, Joint Spectral Radius with focus on pairs of 2 X 2 matrices, Ph. D. Dissertation, Penn. State Univ. (2025). See p. 55.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• Frany Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Index entries for sequences related to necklaces

Crossrefs

Column 2 of A276550.

Programs

Maple

with(numtheory); A001371 := proc(n) local s,d; if n = 0 then RETURN(1) else s := 0; for d in divisors(n) do s := s+mobius(d)*A000029(n/d); od; RETURN(s); fi; end;

Mathematica

a29[n_] := a29[n] = (s = If[OddQ[n], 2^((n-1)/2) , 2^(n/2 - 2) + 2^(n/2 - 1)]; a29[0] = 1; Do[s = s + EulerPhi[d]*2^(n/d)/(2*n), {d, Divisors[n]}]; s); a[n_] := Sum[ MoebiusMu[d]*a29[n/d], {d, Divisors[n]}]; a[0] = 1; Table[ a[n], {n, 0, 34}] (* Jean-François Alcover, Oct 04 2011 *)
mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; ReplacePart[CoefficientList[Series[gf[x,2],{x,0,mx}],x],1->1] (* Herbert Kociemba, Nov 28 2016 *)

Python

from sympy import divisors, totient, mobius
def a000029(n):
    return 1 if n<1 else ((2**(n//2+1) if n%2 else 3*2**(n//2-1)) + sum(totient(n//d)*2**d for d in divisors(n))//n)//2
def a(n):
    return 1 if n<1 else sum(mobius(d)*a000029(n//d) for d in divisors(n))
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 23 2017

Formula

a(n) = Sum_{ d divides n } mu(d)*A000029(n/d).

From Herbert Kociemba, Nov 28 2016: (Start)

More generally, for n>0, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.

gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

Extensions

More terms from Christian G. Bower

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