A007058 - OEIS

%I M3936 #28 Feb 19 2024 11:51:48

%S 1,5,25,65,265,605,2125,4345,14665,27965,93025,171825,559645,1015565,

%T 3276725,5857865,18734665,33203045,105436225,185546785,585842065,

%U 1025381485,3222484125,5615234265,17577530845,30517575605,95213827825,164794865465,512692025285,885009765485,2746575977125

%N 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.

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

%H R. Kemp, <a href="http://dx.doi.org/10.1016/0012-365X(82)90123-6">On the number of words in the language {w in Sigma* | w = w^R }^2</a>, Discrete Math., 40 (1982), 225-234.

%F a(n) = A187275(n) - Sum_{d|n,d<n} phi(n/d)*a(d). - _Sean A. Irvine_, Sep 27 2017

%p See A007055.

%o (Python)

%o from functools import lru_cache

%o from sympy import totient, proper_divisors

%o @lru_cache(maxsize=None)

%o 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

%Y Column 5 of A284873.

%Y Cf. A007055, A007056, A007057.

%K nonn

%O 0,2

%A _N. J. A. Sloane_, _Mira Bernstein_, R. Kemp

%E Entry revised by _N. J. A. Sloane_, Mar 07 2011