A357413 Number of nonempty subsets of {1..n} whose elements have an odd geometric mean.

0, 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, 66, 66, 67, 67, 90, 90, 91, 91, 92, 92

Offset: 0

Author

Ilya Gutkovskiy, Sep 27 2022

Keywords

• nonn

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

Examples

			a(9) = 7 subsets: {1}, {3}, {5}, {7}, {9}, {1, 9} and {1, 3, 9}.
		

Links

• Max Alekseyev, Table of n, a(n) for n = 0..256

Crossrefs

Cf. A001055, A326027, A357355, A357411, A357414, A357415.

Programs

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) if n else 0
print([a(n) for n in range(41)]) # Michael S. Branicky, Sep 29 2022

Formula

a(2*n-1) = a(2*n) for n >= 1. - David A. Corneth, Sep 29 2022

a(n) = A326027(n) - A357414(n). - Max Alekseyev, Mar 01 2025

Extensions

a(24)-a(34) from Michael S. Branicky, Sep 29 2022

a(35)-a(70) from David A. Corneth, Sep 29 2022

a(0) prepended and terms a(71) onward added by Max Alekseyev, Mar 06 2025