A082553 - OEIS

%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