login
A357413
Number of nonempty subsets of {1..n} whose elements have an odd geometric mean.
3
1, 1, 2, 2, 3, 3, 4, 4, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 19, 19, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 39, 39, 40, 40, 49, 49, 50, 50, 51, 51, 52, 52, 53, 53, 54, 54, 55, 55, 62, 62, 63, 63, 64, 64, 65, 65
OFFSET
1,3
COMMENTS
The geometric mean of a subset such as in name must be an odd number in {1..n} which might ease the search for terms. - David A. Corneth, Sep 29 2022
FORMULA
a(2*n-1) = a(2*n) for n >= 1. - David A. Corneth, Sep 29 2022
EXAMPLE
a(9) = 7 subsets: {1}, {3}, {5}, {7}, {9}, {1, 9} and {1, 3, 9}.
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
@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) if n&1 else b(n-1, p, c)
@lru_cache(maxsize=None)
def a(n): return b(n, 1, 0) if n&1 else b(n-1, 1, 0)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Sep 29 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Sep 27 2022
EXTENSIONS
a(24)-a(34) from Michael S. Branicky, Sep 29 2022
More terms from David A. Corneth, Sep 29 2022
STATUS
approved