A115118 Number of imprimitive (periodic) n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed.

0, 0, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 10, 1, 11, 5, 20, 1, 36, 1, 58, 11, 95, 1, 196, 4, 317, 30, 598, 1, 1153, 1, 2068, 95, 3857, 13, 7488, 1, 13799, 317, 26288, 1, 50531, 1, 95422, 1124, 182363, 1, 351764, 10, 671144, 3857, 1290874, 1, 2492820, 97, 4794104, 13799, 9256397, 1, 17923218, 1, 34636835, 49968, 67110932, 319

Offset: 0

Author

Valery A. Liskovets, Jan 17 2006

Keywords

• easy
• nonn

Comments

a(p) = 1 for prime p. Presumably a(n) = A115121(n) = A066656(n)/2 for odd n.

Links

• Antti Karttunen, Table of n, a(n) for n = 0..1024

Crossrefs

Cf. A000013, A000048, A385665.

Cf. A115121, A066656.

Programs

Mathematica

a[n_] := If[n == 0, 0, Sum[EulerPhi[2d] 2^(n/d) - Boole[OddQ[d]] MoebiusMu[d] 2^(n/d), {d, Divisors[n]}]/(2n)];
Array[a, 66, 0] (* Jean-François Alcover, Aug 29 2019 *)

PARI

a(n) = if (n==0, 0, (sumdiv(n, d, eulerphi(2*d) * 2^(n/d)) - sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d))))/(2*n)); \\ Michel Marcus, Oct 21 2017

Formula

a(n) = A000013(n) - A000048(n).

a(n) = Sum_{k=2..n} A385665(n,k). - Tilman Piesk, Aug 03 2025

Extensions

More terms from Antti Karttunen, Oct 21 2017