OFFSET
1,1
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)
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).
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)
EXAMPLE
For n=4, the solutions are:
1001, 1001^2 = 1002001,
1111, 1111^2 = 1234321,
2002, 2002^2 = 4008004.
PROG
(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
CROSSREFS
KEYWORD
nonn,easy,base
AUTHOR
David Zvirbulis, Oct 19 2012
EXTENSIONS
a(19)-a(20) from Michael S. Branicky, Apr 02 2021
More terms from Chai Wah Wu, Apr 03 2021
STATUS
approved