login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

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.

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

(Python)

from sympy import divisors, totient, mobius

def a000029(n): return 1 if n<1 else (n%2 + 3)/4*2**int(n/2) + sum([totient(n/d)*2**d for d in divisors(n)])/(2*n)

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 xrange(51)] # Indranil Ghosh, Apr 23 2017

CROSSREFS

Column 2 of A276550.

Sequence in context: A056493 A289352 A277619 * A277629 A277631 A277633

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 12:00 EDT 2018. Contains 316263 sequences. (Running on oeis4.)