A045674 -id:A045674 - cp's OEIS frontend

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

David W. Wilson

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

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

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

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

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

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)

A056503 Number of periodic palindromic structures of length n using a maximum of two different symbols.

Original entry on oeis.org

1, 2, 2, 4, 4, 7, 8, 14, 16, 26, 32, 51, 64, 100, 128, 198, 256, 392, 512, 778, 1024, 1552, 2048, 3091, 4096, 6176, 8192, 12324, 16384, 24640, 32768, 49222, 65536, 98432, 131072, 196744, 262144, 393472, 524288, 786698, 1048576, 1573376, 2097152, 3146256, 4194304

Offset: 1

Marks R. Nester

nonn

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.
A periodic palindrome is just a necklace that is equivalent to its reverse. The number of binary periodic palindromes of length n is given by A164090(n). A binary periodic palindrome can only be equivalent to its complement when there are an equal number of 0's and 1's. - Andrew Howroyd, Sep 29 2017
Number of cyclic compositions (necklaces of positive integers) summing to n that can be rotated to form a palindrome. - Gus Wiseman, Sep 16 2018

			From _Gus Wiseman_, Sep 16 2018: (Start)
The sequence of palindromic cyclic compositions begins:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (111)  (22)    (113)    (33)      (115)
                    (112)   (122)    (114)     (133)
                    (1111)  (11111)  (222)     (223)
                                     (1122)    (11113)
                                     (11112)   (11212)
                                     (111111)  (11122)
                                               (1111111)
(End)

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row sums of A179181.
Cf. A016116, A045674, A056508, A164090, A285012.
Cf. A000740, A000837, A008965, A025065, A059966, A242414, A296302, A317085, A317086, A317087, A318731.

(* b = A164090, c = A045674 *)
b[n_] := (1/4)*(7 - (-1)^n)*2^((1/4)*(2*n + (-1)^n - 1));
c[0] = 1; c[n_] := c[n] = If[EvenQ[n], 2^(n/2-1) + c[n/2], 2^((n-1)/2)];
a[n_?OddQ] := b[n]/2; a[n_?EvenQ] := (1/2)*(b[n] + c[n/2]);
Array[a, 45] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Function[q,And[Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And],Array[SameQ[RotateRight[q,#],Reverse[RotateRight[q,#]]]&,Length[q],1,Or]]]]],{n,15}] (* Gus Wiseman, Sep 16 2018 *)

a(2n+1) = A164090(2n+1)/2 = 2^n, a(2n) = (A164090(2n) + A045674(n))/2. - Andrew Howroyd, Sep 29 2017

a(17)-a(45) from Andrew Howroyd, Apr 07 2017

A045656 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse, complement and reversed complement.

Original entry on oeis.org

1, 2, 6, 8, 22, 32, 48, 100, 150, 260, 336, 684, 784, 1640, 1868, 3728, 4246, 8672, 9372, 19420, 20752, 42736, 45700, 94164, 98832, 204632, 214584, 441764, 460524, 950216, 985968, 2031556, 2101398, 4323888, 4465056, 9174400, 9444988

Offset: 0

David W. Wilson

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A000984, A023900, A045665, A045653, A045654, A045655, A045674.

b[n_] := Module[{t = 0, r = n}, If[n == 0, 1,  While[Mod[r, 2] == 0, r = r/2; t += 2^(r - 1)]; t + 2^Quotient[r, 2]]];
c[n_] := Sum[MoebiusMu[d]*d, {d, Divisors[n]}];
a[n_] := If[n == 0, 1, 2*Sum[c[n/d]*d*b[d], {d, Divisors[n]}]];
a /@ Range[0, 36] (* Jean-François Alcover, Sep 23 2019, from PARI *)

\\ here b(n) is A045674,  c(n) is A023900.
b(n) = if(n<1, n==0, my(t=0, r=n); while(r%2==0, r=r/2; t+=2^(r-1)); t + 2^(r\2));
c(n) = {sumdiv(n,d, moebius(d)*d)}
a(n) = if(n<1, n==0, 2*sumdiv(n, d, c(n/d)*d*b(d))); \\ Andrew Howroyd, Sep 15 2019

From Andrew Howroyd, Sep 15 2019: (Start)
Inverse Moebius transform of A045665.
a(n) = 2*Sum_{d|n} A023900(n/d)*d*A045674(d) for n > 0. (End)

A045665 Number of 2n-bead balanced binary strings of fundamental period 2n, rotationally equivalent to reverse, complement and reversed complement.

Original entry on oeis.org

1, 2, 4, 6, 16, 30, 36, 98, 128, 252, 300, 682, 720, 1638, 1764, 3690, 4096, 8670, 9072, 19418, 20400, 42630, 45012, 94162, 97920, 204600, 212940, 441504, 458640, 950214, 981900, 2031554, 2097152, 4323198, 4456380, 9174270, 9434880

Offset: 0

David W. Wilson

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A007727, A045662, A045663, A045664, A045674, A045683.

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

a(n) = 2*n*A045683(n) for n > 0.

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

A056513 Number of primitive (period n) periodic palindromic structures using a maximum of two different symbols.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 7, 10, 14, 21, 31, 42, 63, 91, 123, 184, 255, 371, 511, 750, 1015, 1519, 2047, 3030, 4092, 6111, 8176, 12222, 16383, 24486, 32767, 49024, 65503, 98175, 131061, 196308, 262143, 392959, 524223, 785910, 1048575, 1572256, 2097151, 3144702, 4194162

Offset: 0

Marks R. Nester

nonn

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.

Number of Lyndon compositions (aperiodic necklaces of positive integers) summing to n that can be rotated to form a palindrome. - Gus Wiseman, Sep 16 2018

			From _Gus Wiseman_, Sep 16 2018: (Start)
The sequence of palindromic Lyndon compositions begins:
  (1)  (2)  (3)  (4)    (5)    (6)      (7)
                 (112)  (113)  (114)    (115)
                        (122)  (1122)   (133)
                               (11112)  (223)
                                        (11113)
                                        (11212)
                                        (11122)
(End)

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Row sums of A179317.

Cf. A008965, A025065, A056476, A059966, A242414, A285037, A317085, A317086, A317087, A318731.

(* b = A164090, c = A045674 *)
b[n_] := (1/4)*(7 - (-1)^n)*2^((1/4)*(2*n + (-1)^n - 1));
c[0] = 1;
c[n_] := c[n] = If[EvenQ[n], 2^(n/2 - 1) + c[n/2], 2^((n - 1)/2)];
a56503[n_] := If[OddQ[n], b[n]/2, (1/2)*(b[n] + c[n/2])];
a[n_] := DivisorSum[n, MoebiusMu[#] a56503[n/#]&];
Array[a, 45] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

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

seq(n) = Vec(1 + (1/2)*sum(k=1, n, moebius(k)*x^k*(2 + 3*x^k)/(1 - 2*x^(2*k)) - moebius(2*k)*x^(2*k)*(1 + x^(2*k))/(1 - 2*x^(4*k)) + O(x*x^n))) \\ Andrew Howroyd, Sep 27 2019

a(n) = Sum_{d|n} mu(d)*A056503(n/d) for n > 0.
a(n) = Sum_{k=1..2} A285037(n, k). - Andrew Howroyd, Apr 08 2017
G.f.: 1 + (1/2)*Sum_{k>=1} mu(k)*x^k*(2 + 3*x^k)/(1 - 2*x^(2*k)) - mu(2*k)*x^(2*k)*(1 + x^(2*k))/(1 - 2*x^(4*k)). - Andrew Howroyd, Sep 27 2019

a(17)-a(45) from Andrew Howroyd, Apr 08 2017

a(0)=1 prepended by Andrew Howroyd, Sep 27 2019

A045675 Number of 2n-bead balanced binary necklaces which are not equivalent to their reverse, complement or reversed complement.

Original entry on oeis.org

0, 0, 0, 0, 0, 8, 32, 168, 616, 2380, 8472, 30760, 109644, 394816, 1420784, 5149948, 18736744, 68553728, 251902032, 929814984, 3445433608, 12814382620, 47817551136, 178982546512, 671813695340, 2528191984504, 9536849826816

Offset: 0

David W. Wilson

nonn

The number of 2n-bead balanced binary necklaces is A003239(n). The number which are equivalent to their reverse, complement and reversed complement are respectively A128014(n), A000013(n) and A011782(n). - Andrew Howroyd, Sep 28 2017

Jean-François Alcover, Table of n, a(n) for n = 0..100
Index entries for sequences related to necklaces

Cf. A000013, A003239, A011782, A045674, A128014.

a3239[n_] := If[n==0, 1, Sum[EulerPhi[n/k]*Binomial[2k, k]/(2n), {k, Divisors[n]}]];
a128014[n_] := SeriesCoefficient[(1 + x)/Sqrt[1 - 4 x^2], {x, 0, n}];
a11782[n_] := SeriesCoefficient[(1 - x)/(1 - 2x), {x, 0, n}];
a13[n_] := If[n==0, 1, Sum[(EulerPhi[2d]*2^(n/d)), {d, Divisors[n]}]/(2n)];
a45674[n_] := a45674[n] = If[n==0, 1, If[EvenQ[n], 2^(n/2-1) + a45674[n/2], 2^((n-1)/2)]];
a[n_] := a3239[n] - a128014[n] - a13[n] - a11782[n] + 2 a45674[n];
a /@ Range[0, 100] (* Jean-François Alcover, Sep 23 2019 *)

a(n) = A003239(n) - A128014(n) - A000013(n) - A011782(n) + 2*A045674(n). - Andrew Howroyd, Sep 28 2017

A045678 Number of 2n-bead balanced binary necklaces which are equivalent to their reversed complement, but not equivalent to their reverse and complement.

Original entry on oeis.org

0, 0, 0, 2, 4, 12, 26, 56, 116, 240, 492, 992, 2010, 4032, 8120, 16256, 32628, 65280, 130800, 261632, 523756, 1047552, 2096096, 4192256, 8386522, 16773120, 33550272, 67100672, 134209464, 268419072, 536854400, 1073709056, 2147450740

Offset: 0

David W. Wilson

nonn

The number of 2n-bead balanced binary necklaces which are equivalent to their reversed complement is A011782(n) and those which are equivalent to their reverse, complement and reversed complement is A045674(n). - Andrew Howroyd, Sep 28 2017

Index entries for sequences related to necklaces

Cf. A011782, A045674.

(* b = A011782, c = A045674 *)
b[0] = 1; b[n_] := 2^(n - 1);
c[0] = 1; c[n_] := c[n] = If[EvenQ[n], 2^(n/2-1) + c[n/2], 2^((n-1)/2)];
a[n_] := b[n] - c[n];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

a(2n+1) = A020522(n) = 4^n - 2^n. - Max Alekseyev, Jan 13 2006

a(n) = A011782(n) - A045674(n). - Andrew Howroyd, Sep 28 2017

A056508 Number of periodic palindromic structures of length n using exactly two different symbols.

Original entry on oeis.org

0, 1, 1, 3, 3, 6, 7, 13, 15, 25, 31, 50, 63, 99, 127, 197, 255, 391, 511, 777, 1023, 1551, 2047, 3090, 4095, 6175, 8191, 12323, 16383, 24639, 32767, 49221, 65535, 98431, 131071, 196743, 262143, 393471, 524287, 786697, 1048575, 1573375, 2097151, 3146255, 4194303

Offset: 1

Marks R. Nester

nonn

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.

For odd n, a palindrome cannot be the complement of itself, so a(n) is given by A284855(n,2)/2 - 1. - Andrew Howroyd, Apr 08 2017

			From _Andrew Howroyd_, Apr 07 2017: (Start)
Example for n=6:
Periodic symmetry means results are either in the form abccba or abcdcb.
There are 3 binary words in the form abccba that start with 0 and contain a 1 which are 001100, 010010, 011110. Of these, 011110 is equivalent to 001100 after rotation.
There are 7 binary words in the form abcdcb that start with 0 and contain a 1 which are 000100, 001010, 001110, 010001, 010101, 011011, 011111. Of these, 011111 is equivalent to 000100, 010001 is equivalent to 001010 and 011011 is equivalent to 010010 from the first set.
There are therefore a total of 7 + 3 - 4 = 6 equivalence classes so a(6) = 6.
(End)

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Giovanni Resta, Table of n, a(n) for n = 1..1000

Column 2 of A285012.

Cf. A052551.

(* b = A164090, c = A045674 *)
b[n_] := (1/4)*(7 - (-1)^n)*2^((1/4)*(2*n + (-1)^n - 1));
c[0] = 1;
c[n_] := c[n] = If[EvenQ[n], 2^(n/2 - 1) + c[n/2], 2^((n - 1)/2)];
a[n_] := If[OddQ[n], b[n]/2, (1/2)*(b[n] + c[n/2])] - 1;
Array[a, 45] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

a(n) = A056503(n) - 1.

a(2n + 1) = 2^n - 1. - Andrew Howroyd, Apr 07 2017

a(17)-a(45) from Andrew Howroyd, Apr 07 2017

A045676 Number of 2n-bead balanced binary necklaces which are equivalent to their reverse, but not equivalent to their complement and reversed complement.

Original entry on oeis.org

0, 0, 0, 0, 2, 2, 14, 12, 58, 54, 232, 220, 886, 860, 3360, 3304, 12730, 12614, 48348, 48108, 184224, 183732, 704376, 703384, 2702070, 2700060, 10396440, 10392408, 40108336, 40100216, 155101008, 155084752, 601047482, 601014854, 2333540428

Offset: 0

David W. Wilson

nonn

The number of 2n-bead balanced binary necklaces equivalent to their reverse is A128014(n) and those equivalent to their reverse, complement and reversed complement is A045674(n). - Andrew Howroyd, Sep 28 2017

Index entries for sequences related to necklaces

Cf. A045674, A045675, A045677, A045678, A128014.

A045674[n_] := A045674[n] = If[n == 0, 1, If[EvenQ[n], 2^(n/2 - 1) + A045674[n/2], 2^((n-1)/2)]];
a[n_] := SeriesCoefficient[(1+x)/Sqrt[1 - 4 x^2], {x, 0, n}] - A045674[n];
a /@ Range[0, 34] (* Jean-François Alcover, Sep 13 2019 *)

a(n) = A128014(n) - A045674(n). - Andrew Howroyd, Sep 28 2017

A045677 Number of 2n-bead balanced binary necklaces which are equivalent to their complement, but not equivalent to their reverse and their reversed complement.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 2, 2, 8, 14, 36, 62, 142, 252, 524, 968, 1928, 3600, 7044, 13286, 25740, 48916, 94364, 180314, 347630, 666996, 1286712, 2477342, 4785824, 9240012, 17880320, 34604066, 67078024, 130085052, 252583200, 490722344, 954313264

Offset: 0

David W. Wilson

nonn

The number of 2n-bead balanced binary necklaces which are equivalent to their complement is A000013(n) and those which are equivalent to their reverse, complement and reversed complement is A045674(n). - Andrew Howroyd, Sep 28 2017

Index entries for sequences related to necklaces

Cf. A000013, A045674, A045675, A045676, A045678.

A045674[n_] := A045674[n] = If[n == 0, 1, If[EvenQ[n], 2^(n/2 - 1) + A045674[n/2], 2^((n - 1)/2)]];
a[n_] := If[n == 0, 1, Sum[EulerPhi[2 d] 2^(n/d), {d, Divisors[n]}]/(2 n)] - A045674[n];
a /@ Range[0, 36] (* Jean-François Alcover, Sep 13 2019 *)

a(n) = A000013(n) - A045674(n). - Andrew Howroyd, Sep 28 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A056503 Number of periodic palindromic structures of length n using a maximum of two different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A045656 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse, complement and reversed complement.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A045665 Number of 2n-bead balanced binary strings of fundamental period 2n, rotationally equivalent to reverse, complement and reversed complement.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A056513 Number of primitive (period n) periodic palindromic structures using a maximum of two different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A045675 Number of 2n-bead balanced binary necklaces which are not equivalent to their reverse, complement or reversed complement.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A045678 Number of 2n-bead balanced binary necklaces which are equivalent to their reversed complement, but not equivalent to their reverse and complement.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A056508 Number of periodic palindromic structures of length n using exactly two different symbols.