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. (Formerly M3936)

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,2

References

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

Links

Table of n, a(n) for n=0..30.

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

Formula

a(n) = A187275(n) - Sum_{d|n,d<n} phi(n/d)*a(d). - Sean A. Irvine, Sep 27 2017

Maple

See A007055.

Prog

(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

Crossrefs

Column 5 of A284873.

Cf. A007055, A007056, A007057.

Sequence in context: A179131 A054994 A108403 * A071383 A088959 A018782

Adjacent sequences: A007055 A007056 A007057 * A007059 A007060 A007061

Keyword

nonn

Author

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

Extensions

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

Status

approved