A001371 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is allowed. (Formerly M0115 N0045 N0285)

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,2

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.

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

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]

Index entries for sequences related to necklaces

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)

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

Prog

(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

Crossrefs

Column 2 of A276550.

Sequence in context: A056493 A289352 A277619 * A339408 A277629 A277631

Adjacent sequences: A001368 A001369 A001370 * A001372 A001373 A001374

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Christian G. Bower

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

Status

approved