A082553 Number of sets of distinct positive integers whose geometric mean is an integer, the largest integer of a set is n.

1, 1, 1, 3, 1, 1, 1, 3, 7, 1, 1, 7, 1, 1, 1, 9, 1, 29, 1, 3, 1, 1, 1, 31, 15, 1, 87, 3, 1, 1, 1, 115, 1, 1, 1, 257, 1, 1, 1, 17, 1, 1, 1, 3, 21, 1, 1, 519, 23, 141, 1, 3, 1, 847, 1, 19, 1, 1, 1, 215, 1, 1, 27, 1557, 1, 1, 1, 3, 1, 1, 1, 2617, 1, 1, 3125, 3, 1, 1

Offset

1,4

Comments

a(n) = 1 if and only if n is squarefree (i.e., if and only if n is in A005117). - Nathaniel Johnston, Apr 28 2011

If n has a prime divisor p > sqrt(n), then a(n) = a(n/p). - Max Alekseyev, Aug 27 2013

Links

Jinyuan Wang, Table of n, a(n) for n = 1..134

Wikipedia, Geometric mean

Example

a(4) = 3: the three sets are {4}, {1, 4}, {1, 2, 4}.

Mathematica

Table[Length[Select[Subsets[Range[n]], MemberQ[#, n]&&IntegerQ[GeometricMean[#]]&]], {n, 15}] (* Gus Wiseman, Jul 19 2019 *)

Prog

(PARI) { A082553(n) = my(m, c=0); if(issquarefree(n), return(1)); m = Set(vector(n-1, i, i)); forprime(p=sqrtint(n)+1, n, m = setminus(m, vector(n\p, i, p*i)); if(Mod(n, p)==0, return(A082553(n\p)) ); ); forvec(v=vector(#m, i, [0, 1]), c += ispower(n*factorback(m, v), 1+vecsum(v)) ); c; } \\ Max Alekseyev, Aug 31 2013
(Python)
from sympy import factorint, factorial
def make_product(p, n, k):
    '''
    Find all k-element subsets of {1, ..., n} whose product is p.
    Returns: list of lists
    '''
    if n**k < p:
        return []
    if k == 1:
        return [[p]]
    if p%n == 0:
        l = [s + [n] for s in make_product(p//n, n - 1, k - 1)]
    else:
        l = []
    return l + make_product(p, n - 1, k)
def integral_geometric_mean(n):
    '''
    Find all subsets of {1, ..., n} that contain n and whose
    geometric mean is an integer.
    '''
    f = factorial(n)
    l = [[n]]
    #Find product of distinct prime factors of n
    c = 1
    for p in factorint(n):
        c *= p
    #geometric mean must be a multiple of c
    for gm in range(c, n, c):
        k = 2
        while not (gm**k%n == 0):
            k += 1
        while gm**k <= f:
            l += [s + [n] for s in make_product(gm**k//n, n - 1, k - 1)]
            k += 1
    return l
def A082553(n):
    return len(integral_geometric_mean(n)) # David Wasserman, Aug 02 2019

Crossrefs

Subsets whose mean is an integer are A051293.

Partitions whose geometric mean is an integer are A067539.

Partial sums are A326027.

Strict partitions whose geometric mean is an integer are A326625.

Cf. A005117, A102627, A316413, A326623.

Sequence in context: A016466 A293669 A055210 * A331736 A344300 A323840

Adjacent sequences: A082550 A082551 A082552 * A082554 A082555 A082556

Keyword

nonn

Author

Naohiro Nomoto, May 03 2003

Extensions

a(24)-a(62) from Max Alekseyev, Aug 31 2013

a(63)-a(99) from David Wasserman, Aug 02 2019

Status

approved