|
%I #43 Aug 21 2021 15:51:43
%S 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,
%T 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,
%U 1,215,1,1,27,1557,1,1,1,3,1,1,1,2617,1,1,3125,3,1,1
%N Number of sets of distinct positive integers whose geometric mean is an integer, the largest integer of a set is n.
%C 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
%C If n has a prime divisor p > sqrt(n), then a(n) = a(n/p). - _Max Alekseyev_, Aug 27 2013
%H Jinyuan Wang, <a href="/A082553/b082553.txt">Table of n, a(n) for n = 1..134</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Geometric_mean">Geometric mean</a>
%e a(4) = 3: the three sets are {4}, {1, 4}, {1, 2, 4}.
%t Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&IntegerQ[GeometricMean[#]]&]],{n,15}] (* _Gus Wiseman_, Jul 19 2019 *)
%o (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
%o (Python)
%o from sympy import factorint, factorial
%o def make_product(p, n, k):
%o '''
%o Find all k-element subsets of {1, ..., n} whose product is p.
%o Returns: list of lists
%o '''
%o if n**k < p:
%o return []
%o if k == 1:
%o return [[p]]
%o if p%n == 0:
%o l = [s + [n] for s in make_product(p//n, n - 1, k - 1)]
%o else:
%o l = []
%o return l + make_product(p, n - 1, k)
%o def integral_geometric_mean(n):
%o '''
%o Find all subsets of {1, ..., n} that contain n and whose
%o geometric mean is an integer.
%o '''
%o f = factorial(n)
%o l = [[n]]
%o #Find product of distinct prime factors of n
%o c = 1
%o for p in factorint(n):
%o c *= p
%o #geometric mean must be a multiple of c
%o for gm in range(c, n, c):
%o k = 2
%o while not (gm**k%n == 0):
%o k += 1
%o while gm**k <= f:
%o l += [s + [n] for s in make_product(gm**k//n, n - 1, k - 1)]
%o k += 1
%o return l
%o def A082553(n):
%o return len(integral_geometric_mean(n)) # _David Wasserman_, Aug 02 2019
%Y Subsets whose mean is an integer are A051293.
%Y Partitions whose geometric mean is an integer are A067539.
%Y Partial sums are A326027.
%Y Strict partitions whose geometric mean is an integer are A326625.
%Y Cf. A005117, A102627, A316413, A326623.
%K nonn
%O 1,4
%A _Naohiro Nomoto_, May 03 2003
%E a(24)-a(62) from _Max Alekseyev_, Aug 31 2013
%E a(63)-a(99) from _David Wasserman_, Aug 02 2019
|
