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

1, 2, 3, 4, 5, 12, 13, 14, 15, 18, 19, 26, 27, 30, 53, 54, 55, 100, 101, 180, 203, 210, 211, 378, 379, 382, 383, 1092, 1093, 2020, 2021, 2022, 3933, 3956, 6473, 10226, 10227, 10266, 10561, 20948, 20949

Offset

1,2

Comments

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

From Chai Wah Wu, Dec 14 2020: (Start)

The above empirical observation is true.

Theorem: For prime p, a(p^k) = a(p^k-1)+1.

Proof: Since the singleton set {x} has harmonic mean x, a(n) >= a(n-1)+1.

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).

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.

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.

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.

Thus {p^k} is the only subset of {1,2,..,p^k} that includes p^k and have an integral Harmonic mean.

This concludes the proof.

(End)

Links

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

Eric W. Weisstein's World of Mathematics, Harmonic Mean

Formula

a(n) >= a(n-1)+1. For prime p, a(p^k) = a(p^k-1)+1. - Chai Wah Wu, Dec 14 2020

Example

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}.

Prog

(Python)
from itertools import chain, combinations
from fractions import Fraction
def powerset(s): # skip empty set
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))
def hm(s):
    ss = sum(Fraction(1, i) for i in s)
    return Fraction(len(s)*ss.denominator, ss.numerator)
def a(n):
    return sum(hm(s).denominator==1 for s in powerset(range(1, n+1)))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Dec 06 2020
(Python)
from math import lcm
from itertools import combinations
def A339453(n):
    m = lcm(*range(2, n+1))
    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

Crossrefs

Cf. A002944, A003418, A051293, A067540, A246655, A326027, A339454.

Sequence in context: A066574 A240304 A325684 * A281597 A039007 A050745

Adjacent sequences: A339450 A339451 A339452 * A339454 A339455 A339456

Keyword

nonn,more

Author

Ilya Gutkovskiy, Dec 05 2020

Extensions

a(23)-a(29) from Michael S. Branicky, Dec 06 2020

a(30)-a(35) from Chai Wah Wu, Dec 08 2020

a(36)-a(39) from Chai Wah Wu, Dec 11 2020

a(40)-a(41) from Chai Wah Wu, Dec 19 2020

Status

approved