A364468 Number of primitive n-bead necklaces (turning over is allowed) comprising elements of two flavors where complements and scalings are equivalent.
1, 1, 1, 1, 1, 3, 3, 8, 12, 20, 35, 62, 106, 189, 343, 603, 1130, 2055, 3860, 7154, 13562, 25463, 48607, 92204, 176646, 337587, 649151, 1246819, 2404519, 4636389, 8963497, 17334800, 33585928, 65107935, 126385919, 245492221, 477345359, 928772649, 1808662015, 3524337599, 6872457828, 13409202675, 26179870365
Offset: 0
Keywords
Examples
For a(4) = 1, there is one solution: "1110". The other primitive sequence "1100" can be reduced to "10", which no longer uses 4 elements. For a(6) = 3, there are three solutions: "111110", "111010", and "110010". The other primitive sequences "111100" and "111000" can be reduced to "110" and "10", respectively, which no longer use 6 elements.
Programs
-
PARI
a11(n) = if( n<1, n==0, 2^(n\2) / 2 + sumdiv(n, k, eulerphi(2*k) * 2^(n/k)) / (4*n)); a46(n) = { my(s=0); fordiv (n, d, s+=moebius(d)*a11(n/d)); s}; a364468(n) = { my(s=a46(n)); fordiv (n, k, s-=if(k!=1&&k!=n, a364468(k), 0)); s}; for (k=1,42, print1(a364468(k),", ")) \\ Hugo Pfoertner, Jul 26 2023
Formula
a(n) = A000046(n) - Sum_{k = nontrivial divisors of n} a(k). (nontrivial divisors, d: 1 < d < n.)
Comments