OFFSET
0,3
COMMENTS
Papaya words are concatenations of two palindromes or palindromes themselves. A165136 is the number of papaya patterns for n-digit numbers. Thus a(n) coincides with A165136 for small n, and is greater than A165136 for larger n. The actual number of n-digit papaya numbers is A165135.
The first 19 terms of this sequence are the same as in A165136. A165137(20) = A165136(20)+10. - Tanya Khovanova, Oct 01 2009, corrected by Franklin T. Adams-Watters, Apr 10 2011
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..100
Chuan Guo, J. Shallit, and A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
Tanya Khovanova, Papaya Words and Numbers
FORMULA
a(n) = R(n) - Sum_{d|n,d<n} phi(n/d)*a(d) where R(2*k)=k*(bell(k)+bell(k+1)), R(2*k+1)=(2*k+1)*bell(k+1), bell(k)=A000110(k). - Andrew Howroyd, Mar 29 2016
EXAMPLE
There are two types of two-digit papaya numbers: aa, or ab. Hence a(2) = 2. There are four types of three-digit papaya numbers: aaa, aab, aba, abb. Hence a(3) = 4.
MATHEMATICA
R[k_?EvenQ] := (1/2)*k*(BellB[1 + k/2] + BellB[k/2]);
R[k_?OddQ] := k*BellB[1 + (k - 1)/2];
a[0] = 1; a[n_] := a[n] = R[n] - Sum[EulerPhi[n/d]*a[d], {d, Most[Divisors[ n]]}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)
PROG
(Python)
from functools import lru_cache
from sympy import bell, totient, proper_divisors
@lru_cache(maxsize=None)
def A165137(n): return (n*bell((n>>1)+1) if n&1 else (a:=n>>1)*(bell(a)+bell(a+1)))-sum(totient(n//d)*A165137(d) for d in proper_divisors(n, generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Sergei Bernstein and Tanya Khovanova, Sep 04 2009
EXTENSIONS
a(0) and a(7)-a(14) from Franklin T. Adams-Watters, Apr 10 2011
a(15)-a(30) from Andrew Howroyd, Mar 29 2016
STATUS
approved