|
|
A179781
|
|
a(n) = AP(n) is the total number of aperiodic k-palindromes of n, 1 <= k <= n.
|
|
6
|
|
|
1, 1, 1, 2, 3, 5, 7, 12, 14, 27, 31, 54, 63, 119, 123, 240, 255, 490, 511, 990, 1015, 2015, 2047, 4020, 4092, 8127, 8176, 16254, 16383, 32607, 32767, 65280, 65503, 130815, 131061, 261576, 262143, 523775, 524223, 1047540, 1048575, 2096003, 2097151, 4192254
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
A k-composition is aperiodic (primitive) if its period is k, or if it is not the concatenation of a smaller composition.
A k-palindrome of n is a k-composition of n which is a palindrome.
This sequence is AP(n), the total number of aperiodic k-palindromes of n, 1 <= k <= n.
For example AP(6)=5 because the number n=6
has 1 aperiodic 1-palindrome, namely 6 itself;
has 1 aperiodic 3-palindrome, namely 141;
has 2 aperiodic 4-palindromes, namely 2112 and 1221;
has 1 aperiodic 5-palindrome, namely 11211.
This gives a total of 1+1+2+1=5 aperiodic palindromes of 6.
Number of achiral set partitions of a primitive cycle of n elements having up to two different elements. - Robert A. Russell, Jun 19 2019
|
|
REFERENCES
|
John P. McSorley, Counting k-compositions of n with palindromic and related structures. Preprint, 2010.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{d | n} moebius(n/d)*2^(floor(d/2)) (see Baek et al. page 9). - Michel Marcus, Dec 09 2014
G.f.: Sum_{k>=1} mu(k)*x^k*(1 + 2*x^k)/(1 - x^(2*k)). - Andrew Howroyd, Sep 27 2019
|
|
EXAMPLE
|
For a(7)=7, the achiral set partitions are 0000001, 0000011, 0000101, 0000111, 0001001, 0010011, and 0010101. - Robert A. Russell, Jun 19 2019
|
|
MATHEMATICA
|
a[n_] := DivisorSum[n, MoebiusMu[n/#] * 2^Floor[#/2]&];
|
|
PROG
|
(PARI) a(n) = sumdiv(n, d, moebius(n/d) * 2^(d\2)); \\ Michel Marcus, Dec 09 2014
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|