Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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\}$. –  Greg Martin Jan 28 '12 at 2:06
    
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. –  daniel Jan 28 '12 at 2:28
    
@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. –  daniel Jan 28 '12 at 11:37
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. –  Christian Blatter Feb 11 '13 at 14:49

1 Answer 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.

share|improve this answer
    
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. –  daniel Jan 28 '12 at 1:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.