A218035 Number of n-digit palindromes with squares that are also palindromes.

4, 2, 5, 3, 8, 5, 13, 9, 22, 16, 37, 27, 60, 43, 93, 65, 138, 94, 197, 131, 272, 177, 365, 233, 478, 300, 613, 379, 772, 471, 957, 577, 1170, 698, 1413, 835, 1688, 989, 1997, 1161, 2342, 1352, 2725, 1563, 3148, 1795, 3613, 2049, 4122, 2326, 4677, 2627, 5280, 2953

Offset: 1

Author

David Zvirbulis, Oct 19 2012

Keywords

• nonn
• easy
• base

Comments

Number of n-digit terms in A057135.

From Chai Wah Wu, Apr 03 2021: (Start)

The conjectures in the formula section are true.

Theorem: a(n) = (n^3-6*n^2+32*n+48)/48 if n is even.

a(n) = (n^3-9*n^2+59*n-3)/24 if n > 1 is odd.

Proof: For n < 9, this is true by inspection.

The set of palindromes whose square are palindromic are the numbers whose squares of the digits sums to less than 10 (see A057135). For n >= 9, the nonzero digits are from one of the following 12 sets:

(1, 1, 1, 1, 1, 1, 1, 1), (1, 2, 2), (1, 1, 1, 1), (1, 1, 2), (1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 1, 1, 1), (2, 2), (1, 1, 1), (1, 1, 1, 1, 1), (1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 1)

For odd n >= 9:

(1, 1, 1, 1, 1, 1, 1, 1): number of palindromes with 8 1's and n-8 0's is C((n-3)/2,3) = (n-3)(n-5)(n-7)/48. This is because all palindromes must start and end with a nonzero digit and the middle digit is necessarily 0, so only the (n-3) remaining digits are permuted with 6 1's and (n-9) 0's. By symmetry of the palindromes the number of combinations is C((n-3)/2,3).

(1, 2, 2): 1 palindrome of the form 20..010..2.

(1, 1, 1, 1): number of palindromes with 4 1's and n-4 0's is C((n-3)/2,1) = (n-3)/2.

(1, 1, 2): 1 palindrome of the form 10..020..1.

(1, 1, 1): 1 palindrome of the form 10..010..1.

(1, 1, 1, 1, 1): number of palindromes with 5 1's and n-5 0's is C((n-3)/2,1) = (n-3)/2.

(1, 1, 1, 1, 2): C((n-3)/2,1) = (n-3)/2.

(1, 1, 1, 1, 1, 1, 1): C((n-3)/2,2).

(1, 1, 1, 1, 1, 1, 1, 1, 1): C((n-3)/2,3).

(2,2): 1 palindrome of the form 200...002.

(1,1): 1 palindrome of the form 100...001.

(1,1,1,1,1,1): number of palindromes with 6 1's and n-6 0's is C((n-3)/2,2) = (n-3)(n-5)/8.

Thus A218035(n) = 2*(n-3)(n-5)(n-7)/48 +2*(n-3)(n-5)/8 +3*(n-3)/2 + 5 = (n^3-9n^2+59n-3)/24.

For even n >= 9:

(1, 2, 2), (1, 1, 2), (1, 1, 1), (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 1, 1, 1): no palindromes are possible.

(1, 1, 1, 1, 1, 1, 1, 1): number of palindromes 8 1's and n-8 0's = C((n-2)/2,3) = (n-2)(n-4)(n-6)/48.

(1, 1, 1, 1): number of palindromes with 4 1's and n-4 0's is C((n-2)/2,1) = (n-2)/2.

(2,2): 1 palindrome of the form 200...002.

(1,1): 1 palindrome of the form 100...001.

(1,1,1,1,1,1): number of palindromes with 6 1's and n-6 0's is C((n-2)/2,2) = (n-2)(n-4)/8.

Thus A218035(n) = (n-2)(n-4)(n-6)/48 + (n-2)(n-4)/8 + (n-2)/2 +2 = (n^3-6n^2+32n+48)/48. QED

(End)

Examples

			For n=4, the solutions are:
1001, 1001^2 = 1002001,
1111, 1111^2 = 1234321,
2002, 2002^2 = 4008004.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000
• Manuel Kauers and Christoph Koutschan, Guessing with Little Data, arXiv:2202.07966 [cs.SC], 2022.
• Index entries for linear recurrences with constant coefficients, signature (0,4,0,-6,0,4,0,-1).

Crossrefs

Cf. A050683, A070252, A307717.

Programs

Python

from itertools import product
def ispal(n): s = str(n); return s == s[::-1]
def pals(n):
  midrange = [[""], [str(i) for i in range(10)]]
  for p in product("0123456789", repeat=n//2):
    left = "".join(p)
    if len(left) and left[0] == '0': continue
    for middle in midrange[n%2]: yield left+middle+left[::-1]
def a(n): return sum(ispal(int(strpal)**2) for strpal in pals(n))
print([a(n) for n in range(1, 13)]) # Michael S. Branicky, Apr 02 2021

Python

def A218035(n): return 4 if n == 1 else (n**3-9*n**2+59*n-3)//24 if n % 2 else (n**3-6*n**2+32*n+48)//48 # Chai Wah Wu, Apr 03 2021

Formula

Conjecture: a(n) = n^3/48 - n^2/8 + 2n/3 + 1 if n even, see A011826.

Conjecture: a(n) = n^3/24 - 3n^2/8 + 59n/24 - 1/8 if n odd, n > 1.

From Chai Wah Wu, Apr 03 2021: (Start)

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

G.f.: x*(2*x^8 - x^7 - 5*x^6 + 5*x^5 + 12*x^4 - 5*x^3 - 11*x^2 + 2*x + 4)/((x - 1)^4*(x + 1)^4). (End)

Extensions

a(19)-a(20) from Michael S. Branicky, Apr 02 2021

More terms from Chai Wah Wu, Apr 03 2021