cp's OEIS Frontend

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

%I A218035 #43 Mar 04 2022 18:57:44
%S A218035 4,2,5,3,8,5,13,9,22,16,37,27,60,43,93,65,138,94,197,131,272,177,365,
%T A218035 233,478,300,613,379,772,471,957,577,1170,698,1413,835,1688,989,1997,
%U A218035 1161,2342,1352,2725,1563,3148,1795,3613,2049,4122,2326,4677,2627,5280,2953
%N A218035 Number of n-digit palindromes with squares that are also palindromes.
%C A218035 Number of n-digit terms in A057135.
%C A218035 From _Chai Wah Wu_, Apr 03 2021: (Start)
%C A218035 The conjectures in the formula section are true.
%C A218035 Theorem: a(n) = (n^3-6*n^2+32*n+48)/48 if n is even.
%C A218035 a(n) = (n^3-9*n^2+59*n-3)/24 if n > 1 is odd.
%C A218035 Proof: For n < 9, this is true by inspection.
%C A218035 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:
%C A218035 (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)
%C A218035 For odd n >= 9:
%C A218035 (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).
%C A218035 (1, 2, 2): 1 palindrome of the form 20..010..2.
%C A218035 (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.
%C A218035 (1, 1, 2): 1 palindrome of the form 10..020..1.
%C A218035 (1, 1, 1): 1 palindrome of the form 10..010..1.
%C A218035 (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.
%C A218035 (1, 1, 1, 1, 2): C((n-3)/2,1) = (n-3)/2.
%C A218035 (1, 1, 1, 1, 1, 1, 1): C((n-3)/2,2).
%C A218035 (1, 1, 1, 1, 1, 1, 1, 1, 1): C((n-3)/2,3).
%C A218035 (2,2): 1 palindrome of the form 200...002.
%C A218035 (1,1): 1 palindrome of the form 100...001.
%C A218035 (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.
%C A218035 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.
%C A218035 For even n >= 9:
%C A218035 (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.
%C A218035 (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.
%C A218035 (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.
%C A218035 (2,2): 1 palindrome of the form 200...002.
%C A218035 (1,1): 1 palindrome of the form 100...001.
%C A218035 (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.
%C A218035 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
%C A218035 (End)
%H A218035 Chai Wah Wu, <a href="/A218035/b218035.txt">Table of n, a(n) for n = 1..10000</a>
%H A218035 Manuel Kauers and Christoph Koutschan, <a href="https://arxiv.org/abs/2202.07966">Guessing with Little Data</a>, arXiv:2202.07966 [cs.SC], 2022.
%H A218035 <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (0,4,0,-6,0,4,0,-1).
%F A218035 Conjecture: a(n) = n^3/48 - n^2/8 + 2n/3 + 1 if n even, see A011826.
%F A218035 Conjecture: a(n) = n^3/24 - 3n^2/8 + 59n/24 - 1/8 if n odd, n > 1.
%F A218035 From _Chai Wah Wu_, Apr 03 2021: (Start)
%F A218035 a(n) = 4*a(n-2) - 6*a(n-4) + 4*a(n-6) - a(n-8) for n > 9.
%F A218035 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)
%e A218035 For n=4, the solutions are:
%e A218035 1001, 1001^2 = 1002001,
%e A218035 1111, 1111^2 = 1234321,
%e A218035 2002, 2002^2 = 4008004.
%o A218035 (Python)
%o A218035 from itertools import product
%o A218035 def ispal(n): s = str(n); return s == s[::-1]
%o A218035 def pals(n):
%o A218035   midrange = [[""], [str(i) for i in range(10)]]
%o A218035   for p in product("0123456789", repeat=n//2):
%o A218035     left = "".join(p)
%o A218035     if len(left) and left[0] == '0': continue
%o A218035     for middle in midrange[n%2]: yield left+middle+left[::-1]
%o A218035 def a(n): return sum(ispal(int(strpal)**2) for strpal in pals(n))
%o A218035 print([a(n) for n in range(1, 13)]) # _Michael S. Branicky_, Apr 02 2021
%o A218035 (Python)
%o A218035 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
%Y A218035 Cf. A050683, A070252, A307717.
%K A218035 nonn,easy,base
%O A218035 1,1
%A A218035 _David Zvirbulis_, Oct 19 2012
%E A218035 a(19)-a(20) from _Michael S. Branicky_, Apr 02 2021
%E A218035 More terms from _Chai Wah Wu_, Apr 03 2021