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.

  • 2
    If you replace the largest element $n_m$ with two new elements $n'_m=n_m+1$ and $n'_{m+1}=n_m(n_m+1)$ (thus increasing $m$ by 1), then the reciprocal sum is unchanged while the sum with the ln increases by about $1/(m+1)$. If you do this repeatedly, the increase in the ln-sum stops being visible, so you'll get a sequence (albeit with increasing $m$) where the sum is very small. I suspect that the minimum might well occur for the sequence $\{2, 3, 7, 43, 43*42+1, \dots\}$ resulting from iterating this process starting from $\{2,3,6\}$.2012-01-28
  • 0
    Yes. This is the sequence in Jitsuro Nagura's paper [query under name in Euclid]. I was wondering if it was optimal or just very convenient. That's the algorithm I was looking at.2012-01-28
  • 0
    @GregMartin: the reason I put in the second example is that it results in a smaller min, but the inverses don't quiet sum to 1, so I thought that we could find sums with a large number of terms to get something that works well (approximately) with both e_1 and e_2.2012-01-28
  • 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