login
A357414
Number of nonempty subsets of {1..n} whose elements have an even geometric mean.
3
0, 1, 1, 4, 4, 5, 5, 8, 12, 13, 13, 20, 20, 21, 21, 30, 30, 59, 59, 62, 62, 63, 63, 94, 104, 105, 187, 190, 190, 191, 191, 306, 306, 307, 307, 564, 564, 565, 565, 582, 582, 583, 583, 586, 600, 601, 601, 1120, 1134, 1275, 1275, 1278, 1278, 2125, 2125, 2144, 2144, 2145, 2145, 2360, 2360, 2361, 2381, 3938, 3938, 3939, 3939, 3942, 3942, 3943, 3943, 6560, 6560, 6561, 9663, 9666
OFFSET
1,4
FORMULA
a(p) = a(p-1) for prime p > 2. - Michael S. Branicky, Sep 30 2022
EXAMPLE
a(8) = 8 subsets: {2}, {4}, {6}, {8}, {1, 4}, {2, 8}, {1, 2, 4} and {2, 4, 8}.
PROG
(Python)
from functools import lru_cache
from sympy import integer_nthroot
def cond(p, c): r, b = integer_nthroot(p, c); return b and r&1 == 0
@lru_cache(maxsize=None)
def b(n, p, c):
if n == 0: return int (c > 0 and cond(p, c))
return b(n-1, p, c) + b(n-1, p*n, c+1)
a = lambda n: b(n, 1, 0)
print([a(n) for n in range(1, 26)]) # Michael S. Branicky, Sep 29 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Sep 27 2022
EXTENSIONS
a(24)-a(41) from Michael S. Branicky, Sep 30 2022
Terms a(42) onward from Max Alekseyev, Oct 11 2023
STATUS
approved