cp's OEIS Frontend

A339453 Number of subsets of {1..n} whose harmonic mean is an integer.

%I A339453 #48 Mar 25 2025 13:29:09
%S A339453 1,2,3,4,5,12,13,14,15,18,19,26,27,30,53,54,55,100,101,180,203,210,
%T A339453 211,378,379,382,383,1092,1093,2020,2021,2022,3933,3956,6473,10226,
%U A339453 10227,10266,10561,20948,20949
%N A339453 Number of subsets of {1..n} whose harmonic mean is an integer.
%C A339453 For terms listed in the Data section: a(p^k) = a(p^k-1) + 1, where p prime (empirical observation). - _Ilya Gutkovskiy_, Dec 06 2020
%C A339453 From _Chai Wah Wu_, Dec 14 2020: (Start)
%C A339453 The above empirical observation is true.
%C A339453 Theorem: For prime p, a(p^k) = a(p^k-1)+1.
%C A339453 Proof: Since the singleton set {x} has harmonic mean x, a(n) >= a(n-1)+1.
%C A339453 Let S = {s_1,s_2,..,s_n} be a subset of {1,2,..,p^k} with n>1 elements such that s_n = p^k and let H be the harmonic mean of S. Let M = A003418(p^k) be the least common multiple of {1,2,..,p^k}. Then M = Wp^k where p does not divide W = A002944(p^k).
%C A339453 Let Q_i = M/s_i and Q = sum_i Q_i. This implies that Q_n = W and p divides Q_i for i < n.
%C A339453 H can be written as nM/Q. Since p does not divide W, this implies that p does not divide Q. Suppose H is an integer. Then this implies that Q divides nM/p^k = nW.
%C A339453 Note that s_i < s_n for i < n. This implies that Q_i > W for i < n, i.e. Q > nW, and this contradicts the fact that Q divides nW and thus H is not an integer.
%C A339453 Thus {p^k} is the only subset of {1,2,..,p^k} that includes p^k and have an integral Harmonic mean.
%C A339453 This concludes the proof.
%C A339453 (End)
%H A339453 Eric W. Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HarmonicMean.html">Harmonic Mean</a>
%F A339453 a(n) >= a(n-1)+1. For prime p, a(p^k) = a(p^k-1)+1. - _Chai Wah Wu_, Dec 14 2020
%F A339453 a(n) = A357411(n) + A357412(n). - _Max Alekseyev_, Feb 26 2025
%e A339453 a(6) = 12 subsets: {1}, {2}, {3}, {4}, {5}, {6}, {2, 6}, {3, 6}, {1, 3, 6}, {2, 3, 6}, {3, 4, 6} and {1, 2, 3, 6}.
%o A339453 (Python)
%o A339453 from itertools import chain, combinations
%o A339453 from fractions import Fraction
%o A339453 def powerset(s): # skip empty set
%o A339453     return chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1))
%o A339453 def hm(s):
%o A339453     ss = sum(Fraction(1, i) for i in s)
%o A339453     return Fraction(len(s)*ss.denominator, ss.numerator)
%o A339453 def a(n):
%o A339453     return sum(hm(s).denominator==1 for s in powerset(range(1,n+1)))
%o A339453 print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Dec 06 2020
%o A339453 (Python)
%o A339453 from math import lcm
%o A339453 from itertools import combinations
%o A339453 def A339453(n):
%o A339453     m = lcm(*range(2,n+1))
%o A339453     return sum(1 for i in range(1,n+1) for d in combinations((m//i for i in range(1,n+1)),i) if m*i % sum(d) == 0) # _Chai Wah Wu_, Dec 02 2021
%Y A339453 Cf. A002944, A003418, A051293, A067540, A246655, A326027, A339454.
%K A339453 nonn,more
%O A339453 1,2
%A A339453 _Ilya Gutkovskiy_, Dec 05 2020
%E A339453 a(23)-a(29) from _Michael S. Branicky_, Dec 06 2020
%E A339453 a(30)-a(35) from _Chai Wah Wu_, Dec 08 2020
%E A339453 a(36)-a(39) from _Chai Wah Wu_, Dec 11 2020
%E A339453 a(40)-a(41) from _Chai Wah Wu_, Dec 19 2020