login
A082553
Number of sets of distinct positive integers whose geometric mean is an integer, the largest integer of a set is n.
8
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
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.
Sequence in context: A016466 A293669 A055210 * A331736 A344300 A323840
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