A343098 Number of palindromes < 10^n whose squares are also palindromes.

1, 4, 6, 11, 14, 22, 27, 40, 49, 71, 87, 124, 151, 211, 254, 347, 412, 550, 644, 841, 972, 1244, 1421, 1786, 2019, 2497, 2797, 3410, 3789, 4561, 5032, 5989, 6566, 7736, 8434, 9847, 10682, 12370, 13359, 15356, 16517, 18859, 20211, 22936, 24499, 27647, 29442, 33055

Offset: 0

Author

Chai Wah Wu, Apr 04 2021

Keywords

• nonn
• base

Comments

Partial sum of A218035. Number of terms in A057135 < 10^n.

Examples

			a(2) = 6 since the only palindromes < 100 whose square are palindromes are 0,1,2,3,11,22.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 0..10000
• Index entries for linear recurrences with constant coefficients, signature (1,4,-4,-6,6,4,-4,-1,1).

Crossrefs

Cf. A000290, A002113, A002779, A057136, A057135, A218035.

Programs

Python

A343098_list = [1, 4, 6, 11, 14, 22, 27, 40, 49, 71]
for i in range(10**3): A343098_list.append(A343098_list[-1] + 4*A343098_list[-2] - 4*A343098_list[-3] - 6*A343098_list[-4] + 6*A343098_list[-5] + 4*A343098_list[-6] - 4*A343098_list[-7] - A343098_list[-8] + A343098_list[-9])

Formula

a(n) = #{i:A057135(i)<10^n}.

For n > 0, a(n) = Sum_{i=1..n} A218035(i).

a(n) = a(n-1) + 4*a(n-2) - 4*a(n-3) - 6*a(n-4) + 6*a(n-5) + 4*a(n-6) - 4*a(n-7) - a(n-8) + a(n-9) for n > 9.

G.f.: (-x^9 + x^7 - x^6 - 6*x^5 - x^4 + 7*x^3 + 2*x^2 - 3*x - 1)/((x - 1)^5*(x + 1)^4).

a(n) = 1491 + 904*n + 510*n^2 - 52*n^3 + 6*n^4 + (-1)^n * (45 - 296*n + 42*n^2 - 4*n^3) for n>0. - Greg Dresden, Jun 20 2021