A181135 a(n) = ADP(n) is the total number of aperiodic k-double-palindromes of n, where 2 <= k <= n.

0, 0, 2, 4, 12, 16, 42, 60, 112, 168, 310, 432, 756, 1106, 1722, 2640, 4080, 6062, 9198, 13860, 20300, 31062, 45034, 68340, 98208, 149940, 212576, 325080, 458724, 700128, 983010, 1501440, 2096096, 3202800, 4456074, 6800976, 9437148, 14398958, 19920474

Offset: 1

Author

John P. McSorley, Oct 05 2010

Keywords

• nonn

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, i.e., if it is not the concatenation of at least two smaller compositions. A palindrome is a word which is the same when written backwards.

A k-double-palindrome of n is a k-composition of n which is the concatenation of two palindromes, PP'=P|P', where both |P|, |P'|>=1. For example 1123532=11|23532 is a 7-double-palindrome of 17 since both 11 and 23532 are palindromes. It is also aperiodic, so it is an aperiodic 7-double-palindrome of 17. See sequence A181111.

The n-th term of this sequence is ADP(n), the total number of aperiodic k-double-palindromes of n, where 2 <= k <= n.

For example ADP(6)=16 because there are 16 aperiodic k-double-palindromes of 6 for k=2,3,4,5, or 6. They are:

(with k=2) 15=1|5, 51=5|1, 24=2|4, 42=4|2,

(with k=3) 114=11|4, 411=4|11,

(with k=4) 1113=111|3, 3111=3|111, 1311=131|1, 1131=1|131, 1122=11|22, and 2211=22|11,

(with k=5) 11112=1111|2, 21111=2|1111, 12111=121|11, 11121=11|121.

References

• John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.

Links

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

Crossrefs

Row sums of A181111 (number of aperiodic k-double-palindromes of n).

Cf. A179781, A180322.

Programs

PARI

a(n) = { sumdiv(n, d, moebius(n/d) * (n * if(d%2, 1, 3/2) * 2^((d-1)\2) - 2^(d\2) )) } \\ Andrew Howroyd, Sep 27 2019

Formula

a(n) = A180322(n) - A179781(n). - Andrew Howroyd, Sep 27 2019

Extensions

a(8) corrected and a(11) and beyond from Andrew Howroyd, Sep 27 2019