A045683 Number of 2n-bead balanced binary necklaces of fundamental period 2n which are equivalent to their reverse, complement and reversed complement.

1, 1, 1, 1, 2, 3, 3, 7, 8, 14, 15, 31, 30, 63, 63, 123, 128, 255, 252, 511, 510, 1015, 1023, 2047, 2040, 4092, 4095, 8176, 8190, 16383, 16365, 32767, 32768, 65503, 65535, 131061, 131040, 262143, 262143, 524223, 524280, 1048575, 1048509, 2097151

Offset: 0

Author

David W. Wilson

Keywords

• nonn
• easy

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• J. E. Iglesias, Enumeration of closest-packings by the space group: a simple approach, Z. Krist. 221 (2006) 237-245, Table 3.
• Index entries for sequences related to Lyndon words

Crossrefs

Cf. A045665, A045674, A045680, A011947 (bisection?).

Programs

Maple

A045683 := proc(p)
    option remember ;
    if p = 0 then
        return 1;
    end if;
    a := 2^(floor((p+1)/2)-1) ;
    for d in numtheory[divisors](p) do
        if d >1 and type(d,'odd') then
            a := a-procname(p/d) ;
        end if;
    end do:
    a ;
end proc:
seq(A045683(p),p=0..30) ; # [Iglesias eq 12] R. J. Mathar, Apr 15 2024

Mathematica

b[0] = 1; b[n_] := Module[{t = 0, r = n}, While[EvenQ[r], r = Quotient[r, 2]; t += 2^(r-1)]; t + 2^Quotient[r, 2]];
a[0] = 1; a[n_] :=  DivisorSum[n, MoebiusMu[n/#]*b[#]&];
Table[a[n], {n, 0, 43}] (* Jean-François Alcover, Sep 30 2017, after Andrew Howroyd *)

PARI

a(n)={if(n<1, n==0, sumdiv(n, d, if(d%2, moebius(d)*2^((n/d-1)\2))))} \\ Andrew Howroyd, Oct 01 2019

Formula

Moebius transform of A045674. - Andrew Howroyd, Sep 29 2017

From Andrew Howroyd, Oct 02 2019: (Start)

a(n) = Sum_{d|n, d odd} mu(d) * 2^floor((n/d-1)/2) for n > 0.

G.f.: 1 + Sum_{k>0} mu(2*k-1)*x^(2*k-1)*(1 + x^(2*k-1))/(1 - 2*x^(4*k-2)).

(End)