cp's OEIS Frontend

A000046 Number of primitive n-bead necklaces (turning over is allowed) where complements are equivalent.

%I A000046 M0696 N0257 #51 May 28 2025 16:20:28
%S A000046 1,1,1,1,2,3,5,8,14,21,39,62,112,189,352,607,1144,2055,3885,7154,
%T A000046 13602,25472,48670,92204,176770,337590,649341,1246840,2404872,4636389,
%U A000046 8964143,17334800,33587072,65107998,126387975,245492232,477349348,928772649,1808669170,3524337789,6872471442
%N A000046 Number of primitive n-bead necklaces (turning over is allowed) where complements are equivalent.
%C A000046 Also, number of "twills" (Grünbaum and Shephard). - _N. J. A. Sloane_, Oct 21 2015
%D A000046 B. Grünbaum and G. C. Shephard, The geometry of fabrics, pp. 77-98 of F. C. Holroyd and R. J. Wilson, editors, Geometrical Combinatorics. Pitman, Boston, 1984.
%D A000046 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000046 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000046 Christian G. Bower, <a href="/A000046/b000046.txt">Table of n, a(n) for n = 0..1000</a>
%H A000046 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 A000046 J. E. Iglesias, <a href="https://doi.org/10.1524/zkri.1981.155.1-2.121">A formula for the number of closest packings of equal spheres having a given repeat period</a>, Z. Krist. 155 (1981) 121-127, Table 1.
%H A000046 Sara Jensen, <a href="https://doi.org/10.1080/17513472.2023.2199375">Sequence knitting</a>, J. Math. Arts (2023).
%H A000046 Karyn McLellan, <a href="https://doi.org/10.37236/3204">Periodic coefficients and random Fibonacci sequences</a>, Electronic Journal of Combinatorics, 20(4), 2013, #P32.
%H A000046 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A000046 a(n) = Sum_{ d divides n } mu(d)*A000011(n/d).
%F A000046 From _Robert A. Russell_, Jun 19 2019: (Start)
%F A000046 a(n) = ((1/(2n))Sum_{odd d|n} mu(d)*2^(n/d) + Sum_{d|n} mu(n/d)*2^floor(d/2)) / 2.
%F A000046 a(n) = A000048(n) - A308706(n) = (A000048(n) + A179781(n))/2 = A308706(n) + A179781(n).
%F A000046 A000011(n) =  Sum_{d|n} a(d). (End)
%e A000046 For a(7)=8, there are seven achiral set partitions (0000001, 0000011, 0000101, 0000111, 0001001, 0010011, 0010101) and one chiral pair (0001011-0001101). - _Robert A. Russell_, Jun 19 2019
%p A000046 with(numtheory); A000046 := proc(n) local s,d; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+mobius(d)*A000011(n/d); od; RETURN(s); fi; end;
%t A000046 a11[0] = 1; a11[n_] := 2^Floor[n/2]/2 + Sum[EulerPhi[2*d]*2^(n/d), {d, Divisors[n]}]/n/4; a[0] = 1; a[n_] := Sum[MoebiusMu[d]*a11[n/d], {d, Divisors[n]}]; Table[a[n], {n, 0, 36}] (* _Jean-François Alcover_, Jul 10 2012, from formula *)
%t A000046 Join[{1}, Table[(DivisorSum[NestWhile[#/2 &, n, EvenQ], MoebiusMu[#] 2^(n/#) &]/(2 n) + DivisorSum[n, MoebiusMu[n/#] 2^Floor[#/2] &])/2, {n, 1, 40}]] (* _Robert A. Russell_, Jun 19 2019 *)
%o A000046 (PARI) apply( {A000046(n)=if(n, sumdiv(n, d, moebius(d)*A000011(n/d)), 1)}, [0..40]) \\ _M. F. Hasler_, May 27 2025
%Y A000046 Similar to A000011, but counts primitive necklaces.
%Y A000046 A000048 (oriented), A308706 (chiral), A179781 (achiral).
%Y A000046 Cf. A054199.
%K A000046 nonn,easy,nice
%O A000046 0,5
%A A000046 _N. J. A. Sloane_