A147752 Size of the largest subset of {1,2,3,...,n} whose geometric mean is an integer.

1, 1, 1, 3, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 8, 8, 8, 10, 10, 10, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16

Offset

1,4

Comments

a(n-1) <= a(n) <= max(a(n-1), nu_{A006530(n)}(n!)) where nu_p(n!) is the exponent of the largest power of p that divides n!. - Robert Israel, Jan 02 2018

Let k be the geometric mean of the subset. Then k is in A055932. - David A. Corneth, Jan 03 2018

Links

Table of n, a(n) for n=1..74.

David A. Corneth, Possible subsets of {1,2,3,...,n} giving a(n)

Example

For n=4, (1*4)^(1/2)=2 and (1*2*4)^(1/3)=2. No other subset of {1,2,3,4} has integer geometric mean, so a(4)=3.

Maple

ub:= proc(k, n) local p, i, v, t;
  p:= max(numtheory:-factorset(k));
  t:= 0;
  for i from 1 do
    v:= floor(n/p^i);
    if v = 0 then return t fi;
    t:= t+v;
  od
end proc:
f:= proc(n) option remember; local goodk, m, u, s, S;
  m:= f(n-1);
  u:= ub(n, n);
  if u <= m then return m fi;
  goodk:= {1} union select(t -> ub(t, n) > m, {$2..n-1});
  S:= combinat:-subsets(goodk);
  while not S[finished] do
    s:= S[nextvalue]() union {n};
    if nops(s) <= m then next fi;
    if type(simplify(convert(s, `*`)^(1/nops(s))), integer) then m:= nops(s); if m = u then return m fi fi;
  od:
  m
end proc:
f(1):= 1:
seq(f(n), n=1..74); # Robert Israel, Jan 02 2018

Mathematica

Array[Length@ Last@ Select[Subsets@ Range@ #, IntegerQ@ GeometricMean@ # &] &, 20] (* Michael De Vlieger, Jan 02 2018 *)

Crossrefs

Cf. A006530, A147751, A147753.

Sequence in context: A227727 A050499 A304431 * A236682 A114227 A187469

Adjacent sequences: A147749 A147750 A147751 * A147753 A147754 A147755

Keyword

nonn

Author

John W. Layman, Nov 11 2008

Extensions

a(1)-a(3) corrected and a(21)-a(74) from Robert Israel, Jan 02 2018

Status

approved