8
$\begingroup$

Looking at an algorithm for minimizing $\sum_{k=1}^{m} \frac{1}{n_k}\ln n_k > 1$ subject to $\sum_{k=1}^{m}\frac{1}{n_k} = 1$ in which $n_k$ are positive and in general non-sequential integers, I wondered about the more general problem of finding the minimum of $\sum_{k=1}^{m} \frac{1}{n_k}\ln n_k > 1$ subject to $\sum_{k=1}^{m}\frac{1}{n_k} \simeq 1$.

For example: $\frac{1}{2}+ \frac{1}{3}+\frac{1}{6} = 1$, and $\frac{1}{2}\ln 2+ \frac{1}{3}\ln 3 + \frac{1}{6}\ln 6 \simeq 1.014$.

We also have $\frac{1}{2}+\frac{1}{3}+\frac{1}{8} + \frac{1}{200}+\frac{1}{5000} \simeq .96 $ with

$\frac{1}{2}\ln 2 +\frac{1}{3}\ln 3 + \frac{1}{8}\ln 8 + \frac{1}{200}\ln 200 +\frac{1}{5000}\ln 5000 \simeq 1.0009$.

Are there general ways of thinking about this? While I would think there are a finite number of solutions for $(\sum_{k=1}^{m} \frac{1}{n_k}\ln n_k - 1 )< \epsilon_1$ and $| \sum_{k=1}^{m}\frac{1}{n_k} - 1| \leq \epsilon_2$, and a countable number of solutions if m can be infinite, I don't see any systematic way of finding solutions even in the finite case.

Thanks for any suggestions.

Edit: typo corrected--sense of inequality in $\epsilon_1$ expression was backward. Should conform to question in title and first paragraph above.

  • 1
    It should be mentioned here that the sequence given by Greg Martin is A000058 in OEIS, where a lot of material about it can be found.2013-02-11

1 Answers 1

1

[EDITED: This answer isn't relevant to the updated version of the question.] Given any (large) integer $B$, if you let $n_1=B$, ..., $n_m = [eB]$, then $ \sum_{k=1}^m \frac1{n_k} = 1 + O(1/B) $ but $ \sum_{k=1}^m \frac{\ln n_k}{n_k} > \ln B \sum_{k=1}^m \frac1{n_k} > \ln B + O(1). $ So there are lots of solutions where the sum with ln is far larger than 1.

  • 0
    The first paragraph (and title) contains the question. I tried to restate the problem more succinctly below, and made a typo. In conformity with first part, the log sum should be (sum -1) < epsilon_1, not greater. Yes, there are lots of solutions in the other direction.2012-01-28