A339555
Number of subsets of {2..n} such that the product of the elements is a perfect power.
Original entry on oeis.org
1, 1, 1, 1, 3, 3, 5, 5, 11, 25, 41, 41, 80, 80, 144, 284, 568, 568, 1147, 1147, 2339, 4667, 8763, 8763, 17548, 35196, 67964, 135918, 273806, 273806, 548956, 548956, 1097974, 2194294, 4291446, 8608698, 17216783, 17216783, 33993999, 67979983, 135956742
Offset: 0
a(8) = 11 subsets: {}, {4}, {8}, {2, 4}, {2, 8}, {4, 8}, {2, 3, 6}, {2, 4, 8}, {3, 6, 8}, {2, 3, 4, 6} and {3, 4, 6, 8}.
A377125
Number of subsets of the first n perfect powers whose sum is a perfect power.
Original entry on oeis.org
1, 2, 4, 5, 8, 10, 19, 28, 50, 77, 140, 232, 400, 682, 1234, 2153, 3714, 6825, 12125, 22308, 43065, 79407, 151201, 291945, 564267, 1088341, 2135410, 4119306, 7849329, 14826987, 27802222, 51646813, 95519435, 176054349, 327888258, 616082702, 1171710821, 2247355919
Offset: 1
a(6) = 10 subsets: {1}, {4}, {8}, {9}, {16}, {25}, {1, 8}, {9, 16}, {1, 8, 16} and {8, 16, 25}.
-
from itertools import count
from sympy import perfect_power
from functools import cache
def cond(s): return bool(s == 1 or perfect_power(s))
@cache
def u(n):
if n == 1: return 1
return next(k for k in count(u(n-1)+1) if perfect_power(k))
@cache
def b(n, s):
assert type(s) == int, (n, s)
if n == 0: return int(cond(s))
return b(n-1, s) + b(n-1, s+u(n))
a = lambda n: b(n, 0)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Oct 18 2024
Showing 1-2 of 2 results.