A007058 Let S denote the palindromes in the language {0,1,2,3,4}*; a(n) = number of words of length n in the language SS.

1, 5, 25, 65, 265, 605, 2125, 4345, 14665, 27965, 93025, 171825, 559645, 1015565, 3276725, 5857865, 18734665, 33203045, 105436225, 185546785, 585842065, 1025381485, 3222484125, 5615234265, 17577530845, 30517575605, 95213827825, 164794865465, 512692025285, 885009765485, 2746575977125

Offset: 0

Author

N. J. A. Sloane, Mira Bernstein, R. Kemp

Keywords

• nonn

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Crossrefs

Column 5 of A284873.

Cf. A007055, A007056, A007057.

Programs

Maple

See A007055.

Python

from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A007058(n): return (n*5**(1+(n>>1)) if n&1 else 3*n*5**(n>>1))-sum(totient(n//d)*A007058(d) for d in proper_divisors(n,generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024

Formula

a(n) = A187275(n) - Sum_{d|n,dSean A. Irvine, Sep 27 2017

Extensions

Entry revised by N. J. A. Sloane, Mar 07 2011