A001371 - OEIS

%I M0115 N0045 N0285 #65 Feb 03 2023 16:31:59

%S 1,2,1,2,3,6,8,16,24,42,69,124,208,378,668,1214,2220,4110,7630,14308,

%T 26931,50944,96782,184408,352450,675180,1296477,2493680,4805388,

%U 9272778,17919558,34669600,67156800,130215996,252741255,490984464,954629662,1857545298

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence, in two entries, N0045 and N0285).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A001371/b001371.txt">Table of n, a(n) for n = 0..400</a>

%H Jairo Bochi and Piotr Laskawiec, <a href="https://arxiv.org/abs/2301.12574">Spectrum maximizing products are not generically unique</a>, arXiv:2301.12574 [math.OC], 2023.

%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.

%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

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

%F From _Herbert Kociemba_, Nov 28 2016: (Start)

%F 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.

%F 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)

%p 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;

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

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

%o (Python)

%o from sympy import divisors, totient, mobius

%o def a000029(n):

%o     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

%o def a(n):

%o     return 1 if n<1 else sum(mobius(d)*a000029(n//d) for d in divisors(n))

%o print([a(n) for n in range(51)]) # _Indranil Ghosh_, Apr 23 2017

%Y Column 2 of A276550.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Christian G. Bower_

%E Entry revised by _N. J. A. Sloane_, Jun 10 2012