A339508 Number of subsets of {2..n} such that the product of the elements is a decimal palindrome.

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

Links

Table of n, a(n) for n=0..51.

David A. Corneth, List of factorizations of the a(n) products for n = 1..51.

David A. Corneth, Lower bounds on a(n) for n = 0..100.

Eric Weisstein's World of Mathematics, Palindromic Number

Index entries for sequences related to palindromes

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

Cf. A002113, A093888, A339507.

Sequence in context: A187228 A187905 A121538 * A275844 A158025 A216345

Adjacent sequences: A339505 A339506 A339507 * A339509 A339510 A339511

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