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

1, 4, 16, 40, 136, 304, 880, 1768, 4936, 9112, 25216, 45016, 121600, 212944, 571552, 982240, 2616136, 4456384, 11785408, 19922872, 52402336, 88076560, 230641504, 385875880, 1006499200, 1677720304, 4361862976, 7247738776, 18789905872, 31138512784, 80529599680, 133143986056, 343594756936

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..32.

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) = A187274(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 A007057(n): return (n<<n+1 if n&1 else 5*(n>>1)<<n)-sum(totient(n//d)*A007057(d) for d in proper_divisors(n, generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024

Crossrefs

Column 4 of A284873.

Sequence in context: A220499 A331574 A110477 * A206918 A056373 A018828

Adjacent sequences: A007054 A007055 A007056 * A007058 A007059 A007060

Keyword

nonn

Author

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

Extensions

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

Status

approved