|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
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
|
|
CROSSREFS
|
Subsets whose mean is an integer are A051293.
Partitions whose geometric mean is an integer are A067539.
Strict partitions whose geometric mean is an integer are A326625.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|