|
|
A319586
|
|
Number of n-digit base-10 palindromes (A002113) that cannot be written as the sum of two positive base-10 palindromes.
|
|
1
|
|
|
2, 0, 8, 7, 95, 94, 975, 971, 9810, 9805, 98288, 98272
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
LINKS
|
|
|
EXAMPLE
|
a(1) = 2, because 0 and 1 are not sums of two positive 1-digit integers, all of which are palindromes. a(3) = 8, because the 8 3-digit palindromes 111, 131, 141, 151, 161, 171, 181, and 191 (A213879(2) ... A213879(9)) cannot be written as sum of two nonzero palindromes.
|
|
PROG
|
A002113(n)={my(L=logint(n, 10)); (n-=L=10^max(L-(n<11*10^(L-1)), 0))*L+fromdigits(Vecrev(digits(if(n<L, n, n\10))))}
is_A002113(n)={Vecrev(n=digits(n))==n}
inv_A002113(P)={P\(P=10^(logint(P+!P, 10)\/2))+P}
for(i=1, 8, j=0; for(m=inv_A002113(10^i+1), inv_A002113(2*(10^i+1)), P=A002113(m); issum=0; for(k=2, m, PP=A002113(k); if(PP>P/2, break); if(is_A002113(P-PP), issum=1; break)); if(issum==0, j++)); print1(j, ", ", ))
(Python)
from sympy import isprime
from itertools import product
def pals(d, base=10): # all d-digit palindromes
digits = "".join(str(i) for i in range(base))
for p in product(digits, repeat=d//2):
if d > 1 and p[0] == "0": continue
left = "".join(p); right = left[::-1]
for mid in [[""], digits][d%2]: yield int(left + mid + right)
def a(n):
palslst = [p for d in range(1, n+1) for p in pals(d)][1:]
palsset = set(palslst)
cs = ctot = 0
for p in pals(n):
ctot += 1
for p1 in palslst:
if p - p1 in palsset: cs += 1; break
if p1 > p//2: break
return ctot - cs
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|