login
A339508
Number of subsets of {2..n} such that the product of the elements is a decimal palindrome.
2
1, 1, 2, 4, 6, 7, 8, 10, 11, 13, 13, 33, 43, 56, 70, 73, 99, 114, 134, 151, 151, 185, 333, 372, 445, 456, 558, 565, 672, 1031, 1031, 1220, 1518, 1967, 2161, 2176, 2238, 5399, 5543, 6720, 6720, 8857, 10019, 11819, 16882, 16896, 18072, 19299, 21267, 23405, 23405, 24686
OFFSET
0,3
COMMENTS
a(k*10) = a(k*10-1) because all new products end in 0, thus not palindromes. - Michael S. Branicky, Dec 08 2020
EXAMPLE
a(9) = 13 subsets: {}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {2, 3}, {2, 4}, {4, 7, 9} and {2, 3, 6, 7}.
PROG
(Python)
from numpy import prod
from itertools import combinations
def a(n):
ans = 1 # empty set
for r in range(1, n):
for s in combinations(range(2, n+1), r):
strsp = str(prod(s))
ans += strsp==strsp[::-1]
return ans
print([a(n) for n in range(20)]) # Michael S. Branicky, Dec 08 2020
(Python)
from functools import lru_cache, reduce
from operator import mul
from itertools import combinations
@lru_cache(maxsize=None)
def A339508(n):
nlist = [i for i in range(2, n) if i % 10 != 0]
if n == 0 or n == 1:
return 1
c = A339508(n-1)
if n % 10 != 0:
if str(n) == str(n)[::-1]:
c += 1
for i in range(1, len(nlist)+1):
for d in combinations(nlist, i):
s = str(reduce(mul, d)*n)
if s == s[::-1]:
c += 1
return c # Chai Wah Wu, Dec 08 2020
(Python)
from functools import lru_cache
def cond(p): sp = str(p); return sp == sp[::-1]
@lru_cache(maxsize=None)
def b(n, p):
if n == 1: return int(cond(p))
return b(n-1, p) + b(n-1, p*n) if p*n%10 else b(n-1, p)
def a(n): return 1 if n < 2 else b(n, 1)
print([a(n) for n in range(36)]) # Michael S. Branicky, Oct 05 2022
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Ilya Gutkovskiy, Dec 07 2020
EXTENSIONS
a(23)-a(32) from Michael S. Branicky, Dec 08 2020
a(33)-a(42) from Chai Wah Wu, Dec 08 2020
a(43)-a(48) from Chai Wah Wu, Dec 11 2020
a(49)-a(51) from Michael S. Branicky, Oct 05 2022
STATUS
approved