A115119 Number of imprimitive (periodic) n-bead necklaces with beads of 2 colors when turning over is allowed.

0, 0, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 16, 2, 19, 10, 30, 2, 55, 2, 81, 20, 127, 2, 248, 8, 381, 46, 690, 2, 1302, 2, 2250, 128, 4113, 24, 7896, 2, 14311, 382, 27036, 2, 51641, 2, 96912, 1266, 184411, 2, 354918, 18, 675258, 4114, 1296861, 2, 2501365, 132, 4806102, 14312

Offset: 0

Author

Valery A. Liskovets, Jan 17 2006

Keywords

• easy
• nonn

Comments

a(p)=2 for prime p.

Crossrefs

Cf. A000029, A001371.

Programs

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)/(2n), {d, Divisors[n]}]; s);
a1371[n_] := Sum[MoebiusMu[d] a29[n/d], {d, Divisors[n]}]; a1371[0] = 1;
a[0] = 0; a[n_] := a29[n] - a1371[n];
Array[a, 70, 0] (* Jean-François Alcover, Aug 28 2019 *)

Formula

a(n) = A000029(n) - A001371(n).

Extensions

More terms from Jean-François Alcover, Aug 28 2019