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

1, 3, 9, 21, 57, 123, 279, 549, 1209, 2127, 4689, 7989, 17031, 28395, 60615, 98061, 208569, 334563, 705789, 1121877, 2356737, 3718827, 7786359, 12223077, 25488903, 39857523, 82876257, 129135729, 267784119, 416118219, 860825439, 1334448261, 2754778809, 4261609131, 8781196329, 13559714109, 27893530029

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

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

Crossrefs

Column 3 of A284873.

Sequence in context: A367111 A372375 A345108 * A026551 A296719 A060578

Adjacent sequences: A007053 A007054 A007055 * A007057 A007058 A007059

Keyword

nonn

Author

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

Extensions

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

Status

approved