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

Author

Naohiro Nomoto, May 03 2003

Keywords

• nonn

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

Examples

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

Links

• Jinyuan Wang, Table of n, a(n) for n = 1..134
• Wikipedia, Geometric mean

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.

Programs

Mathematica

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

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

Extensions

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

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