login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A001371
Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is allowed.
(Formerly M0115 N0045 N0285)
9
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
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. [Cached copy, with permission, pdf format only]
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
KEYWORD
nonn,easy,nice
EXTENSIONS
More terms from Christian G. Bower
Entry revised by N. J. A. Sloane, Jun 10 2012
STATUS
approved