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